1: /* 2: * Copyright (c) 1982, 1986 Regents of the University of California. 3: * All rights reserved. The Berkeley software License Agreement 4: * specifies the terms and conditions for redistribution. 5: * 6: * @(#)quota_kern.c 7.1 (Berkeley) 6/5/86 7: */ 8: 9: #ifdef QUOTA 10: /* 11: * MELBOURNE QUOTAS 12: * 13: * Code pertaining to management of the in-core data structures. 14: */ 15: #include "param.h" 16: #include "systm.h" 17: #include "dir.h" 18: #include "user.h" 19: #include "proc.h" 20: #include "inode.h" 21: #include "quota.h" 22: #include "mount.h" 23: #include "fs.h" 24: #include "uio.h" 25: 26: /* 27: * Quota cache - hash chain headers. 28: */ 29: #define NQHASH 32 /* small power of two */ 30: #define QHASH(uid) ((unsigned)(uid) & (NQHASH-1)) 31: 32: struct qhash { 33: struct qhash *qh_forw; /* MUST be first */ 34: struct qhash *qh_back; /* MUST be second */ 35: }; 36: 37: struct qhash qhash[NQHASH]; 38: 39: /* 40: * Quota free list. 41: */ 42: struct quota *qfreelist, **qfreetail; 43: typedef struct quota *Qptr; 44: 45: /* 46: * Dquot cache - hash chain headers. 47: */ 48: #define NDQHASH 51 /* a smallish prime */ 49: #define DQHASH(uid, dev) \ 50: ((unsigned)(((int)(dev) * 4) + (uid)) % NDQHASH) 51: 52: struct dqhead { 53: struct dqhead *dqh_forw; /* MUST be first */ 54: struct dqhead *dqh_back; /* MUST be second */ 55: }; 56: 57: struct dqhead dqhead[NDQHASH]; 58: 59: /* 60: * Dquot free list. 61: */ 62: struct dquot *dqfreel, **dqback; 63: 64: typedef struct dquot *DQptr; 65: 66: /* 67: * Initialize quota caches. 68: */ 69: qtinit() 70: { 71: register i; 72: register struct quota *q = quota; 73: register struct qhash *qh = qhash; 74: register struct dquot *dq = dquot; 75: register struct dqhead *dh = dqhead; 76: 77: /* 78: * First the cache of structures assigned users. 79: */ 80: for (i = NQHASH; --i >= 0; qh++) 81: qh->qh_forw = qh->qh_back = qh; 82: qfreelist = q; 83: qfreetail = &q->q_freef; 84: q->q_freeb = &qfreelist; 85: q->q_forw = q; 86: q->q_back = q; 87: for (i = nquota; --i > 0; ) { 88: ++q; 89: q->q_forw = q; 90: q->q_back = q; 91: *qfreetail = q; 92: q->q_freeb = qfreetail; 93: qfreetail = &q->q_freef; 94: } 95: q->q_freef = NOQUOTA; 96: /* 97: * Next, the cache between the in-core structures 98: * and the per-filesystem quota files on disk. 99: */ 100: for (i = NDQHASH; --i >= 0; dh++) 101: dh->dqh_forw = dh->dqh_back = dh; 102: dqfreel = dq; 103: dqback = &dq->dq_freef; 104: dq->dq_freeb = &dqfreel; 105: dq->dq_forw = dq; 106: dq->dq_back = dq; 107: for (i = ndquot; --i > 0; ) { 108: ++dq; 109: dq->dq_forw = dq; 110: dq->dq_back = dq; 111: *dqback = dq; 112: dq->dq_freeb = dqback; 113: dqback = &dq->dq_freef; 114: } 115: dq->dq_freef = NODQUOT; 116: } 117: 118: /* 119: * Find an incore quota structure for a particular uid, 120: * or make one. If lookuponly is non-zero, just the lookup is performed. 121: * If nodq is non-zero, the dquot structures are left uninitialized. 122: */ 123: struct quota * 124: getquota(uid, lookuponly, nodq) 125: register uid_t uid; 126: int lookuponly, nodq; 127: { 128: register struct quota *q; 129: register struct qhash *qh; 130: register struct dquot **dqq; 131: register struct mount *mp; 132: register struct quota *qq; 133: 134: /* 135: * Fast check to see if an existing structure 136: * can be reused with just a reference count change. 137: */ 138: q = u.u_quota; 139: if (q != NOQUOTA && q->q_uid == uid) 140: goto quick; 141: /* 142: * Search the quota chache for a hit. 143: */ 144: qh = &qhash[QHASH(uid)]; 145: for (q = (Qptr)qh->qh_forw; q != (Qptr)qh; q = q->q_forw) { 146: if (q->q_uid == uid) { 147: if (q->q_cnt == 0) { 148: if (lookuponly) 149: return (NOQUOTA); 150: /* 151: * Take it off the free list. 152: */ 153: if ((qq = q->q_freef) != NOQUOTA) 154: qq->q_freeb = q->q_freeb; 155: else 156: qfreetail = q->q_freeb; 157: *q->q_freeb = qq; 158: 159: /* 160: * Recover any lost dquot structs. 161: */ 162: if (!nodq) 163: for (dqq = q->q_dq, mp = mount; 164: dqq < &q->q_dq[NMOUNT]; dqq++, mp++) 165: if (*dqq == LOSTDQUOT && mp->m_bufp) { 166: *dqq = discquota(uid, 167: mp->m_qinod); 168: if (*dqq != NODQUOT) 169: (*dqq)->dq_own = q; 170: } 171: } 172: quick: 173: q->q_cnt++; 174: while (q->q_flags & Q_LOCK) { 175: q->q_flags |= Q_WANT; 176: sleep((caddr_t) q, PINOD+1); 177: } 178: if (q->q_cnt == 1) 179: q->q_flags |= Q_NEW | nodq; 180: return (q); 181: } 182: } 183: if (lookuponly) 184: return (NOQUOTA); 185: /* 186: * Take the quota that is at the head of the free list 187: * (the longest unused quota). 188: */ 189: q = qfreelist; 190: if (q == NOQUOTA) { 191: tablefull("quota"); 192: u.u_error = EUSERS; 193: q = quota; /* the su's slot - we must have one */ 194: q->q_cnt++; 195: return (q); 196: } 197: /* 198: * There is one - it is free no longer. 199: */ 200: qq = q->q_freef; 201: if (qq != NOQUOTA) 202: qq->q_freeb = &qfreelist; 203: qfreelist = qq; 204: /* 205: * Now we are about to change this from one user to another 206: * Must take this off hash chain for old user immediately, in 207: * case some other process claims it before we are done. 208: * We must then put it on the hash chain for the new user, 209: * to make sure that we don't make two quota structs for one uid. 210: * (the quota struct will then be locked till we are done). 211: */ 212: remque(q); 213: insque(q, qh); 214: q->q_uid = uid; 215: q->q_flags = Q_LOCK; 216: q->q_cnt++; /* q->q_cnt = 1; */ 217: /* 218: * Next, before filling in info for the new owning user, 219: * we must get rid of any dquot structs that we own. 220: */ 221: for (mp = mount, dqq = q->q_dq; mp < &mount[NMOUNT]; mp++, dqq++) 222: if (*dqq != NODQUOT && *dqq != LOSTDQUOT) { 223: (*dqq)->dq_own = NOQUOTA; 224: putdq(mp, *dqq, 1); 225: } 226: for (mp = mount, dqq = q->q_dq; dqq < &q->q_dq[NMOUNT]; mp++, dqq++) 227: if (!nodq && mp->m_bufp) { 228: *dqq = discquota(uid, mp->m_qinod); 229: if (*dqq != NODQUOT) { 230: if ((*dqq)->dq_uid != uid) 231: panic("got bad quota uid"); 232: (*dqq)->dq_own = q; 233: } 234: } else 235: *dqq = NODQUOT; 236: if (q->q_flags & Q_WANT) 237: wakeup((caddr_t)q); 238: q->q_flags = Q_NEW | nodq; 239: return (q); 240: } 241: 242: /* 243: * Delete a quota, wakeup anyone waiting. 244: */ 245: delquota(q) 246: register struct quota *q; 247: { 248: register struct dquot **dqq; 249: register struct mount *mp; 250: 251: top: 252: if (q->q_cnt != 1) { 253: q->q_cnt--; 254: return; 255: } 256: if (q->q_flags & Q_LOCK) { 257: q->q_flags |= Q_WANT; 258: sleep((caddr_t)q, PINOD+2); 259: /* 260: * Just so we don't sync dquots if not needed; 261: * 'if' would be 'while' if this was deleted. 262: */ 263: goto top; 264: } 265: 266: /* 267: * If we own dquot structs, sync them to disc, but don't release 268: * them - we might be recalled from the LRU chain. 269: * As we will sit on the free list while we are waiting for that, 270: * if dquot structs run out, ours will be taken away. 271: */ 272: q->q_flags = Q_LOCK; 273: if ((q->q_flags & Q_NDQ) == 0) { 274: mp = mount; 275: for (dqq = q->q_dq; dqq < &q->q_dq[NMOUNT]; dqq++, mp++) 276: if (mp->m_bufp) 277: putdq(mp, *dqq, 0); 278: } 279: if (q->q_flags & Q_WANT) 280: wakeup((caddr_t)q); 281: 282: /* 283: * This test looks unnecessary, but someone might have claimed this 284: * quota while we have been getting rid of the dquot info 285: */ 286: if (--q->q_cnt == 0) { /* now able to be reallocated */ 287: if (qfreelist != NOQUOTA) { 288: *qfreetail = q; 289: q->q_freeb = qfreetail; 290: } else { 291: qfreelist = q; 292: q->q_freeb = &qfreelist; 293: } 294: q->q_freef = NOQUOTA; 295: qfreetail = &q->q_freef; 296: q->q_flags = 0; 297: } else 298: q->q_flags &= ~(Q_LOCK|Q_WANT); 299: } 300: 301: /* 302: * Obtain the user's on-disk quota limit 303: * from the file specified. 304: */ 305: struct dquot * 306: discquota(uid, ip) 307: uid_t uid; 308: register struct inode *ip; 309: { 310: register struct dquot *dq; 311: register struct dqhead *dh; 312: register struct dquot *dp; 313: int fail; 314: 315: if (ip == NULL) 316: return (NODQUOT); 317: /* 318: * Check the cache first. 319: */ 320: dh = &dqhead[DQHASH(uid, ip->i_dev)]; 321: for (dq = (DQptr)dh->dqh_forw; dq != (DQptr)dh; dq = dq->dq_forw) { 322: if (dq->dq_uid != uid || dq->dq_dev != ip->i_dev) 323: continue; 324: /* 325: * Cache hit with no references. Take 326: * the structure off the free list. 327: */ 328: if (dq->dq_cnt++ == 0) { 329: dp = dq->dq_freef; 330: if (dp != NODQUOT) 331: dp->dq_freeb = dq->dq_freeb; 332: else 333: dqback = dq->dq_freeb; 334: *dq->dq_freeb = dp; 335: dq->dq_own = NOQUOTA; 336: } 337: /* 338: * We do this test after the previous one so that 339: * the dquot will be moved to the end of the free 340: * list - frequently accessed ones ought to hang around. 341: */ 342: if (dq->dq_isoftlimit == 0 && dq->dq_bsoftlimit == 0) { 343: dqrele(dq); 344: return (NODQUOT); 345: } 346: return (dq); 347: } 348: /* 349: * Not in cache, allocate a new one and 350: * bring info in off disk. 351: */ 352: dq = dqalloc(uid, ip->i_dev); 353: if (dq == NODQUOT) 354: return (dq); 355: dq->dq_flags = DQ_LOCK; 356: ILOCK(ip); 357: fail = rdwri(UIO_READ, ip, (caddr_t)&dq->dq_dqb, sizeof (struct dqblk), 358: (off_t)uid * sizeof (struct dqblk), 1, (int *)0); 359: IUNLOCK(ip); 360: if (dq->dq_flags & DQ_WANT) 361: wakeup((caddr_t)dq); 362: dq->dq_flags = 0; 363: /* 364: * I/O error in reading quota file, release 365: * quota structure and reflect problem to caller. 366: */ 367: if (fail) { 368: remque(dq); 369: dq->dq_forw = dq; /* on a private, unfindable hash list */ 370: dq->dq_back = dq; 371: /* dqrele() (just below) will put dquot back on free list */ 372: } 373: /* no quota exists */ 374: if (fail || dq->dq_isoftlimit == 0 && dq->dq_bsoftlimit == 0) { 375: dqrele(dq); 376: return (NODQUOT); 377: } 378: return (dq); 379: } 380: 381: /* 382: * Allocate a dquot structure. If there are 383: * no free slots in the cache, flush LRU entry from 384: * the cache to the appropriate quota file on disk. 385: */ 386: struct dquot * 387: dqalloc(uid, dev) 388: uid_t uid; 389: dev_t dev; 390: { 391: register struct dquot *dq; 392: register struct dqhead *dh; 393: register struct dquot *dp; 394: register struct quota *q; 395: register struct mount *mp; 396: static struct dqblk zdqb = { 0 }; 397: 398: top: 399: /* 400: * Locate inode of quota file for 401: * indicated file system in case i/o 402: * is necessary in claiming an entry. 403: */ 404: for (mp = mount; mp < &mount[NMOUNT]; mp++) { 405: if (mp->m_dev == dev && mp->m_bufp) { 406: if (mp->m_qinod == NULL) { 407: u.u_error = EINVAL; 408: return (NODQUOT); 409: } 410: break; 411: } 412: } 413: if (mp >= &mount[NMOUNT]) { 414: u.u_error = EINVAL; 415: return (NODQUOT); 416: } 417: /* 418: * Check free list. If table is full, pull entries 419: * off the quota free list and flush any associated 420: * dquot references until something frees up on the 421: * dquot free list. 422: */ 423: if ((dq = dqfreel) == NODQUOT && (q = qfreelist) != NOQUOTA) { 424: 425: do { 426: register struct dquot **dqq; 427: register struct mount *mountp = mount; 428: 429: dqq = q->q_dq; 430: while (dqq < &q->q_dq[NMOUNT]) { 431: if ((dq = *dqq) != NODQUOT && 432: dq != LOSTDQUOT) { 433: /* 434: * Mark entry as "lost" due to 435: * scavenging operation. 436: */ 437: if (dq->dq_cnt == 1) { 438: *dqq = LOSTDQUOT; 439: putdq(mountp, dq, 1); 440: goto top; 441: } 442: } 443: mountp++; 444: dqq++; 445: } 446: q = q->q_freef; 447: } while ((dq = dqfreel) == NODQUOT && q != NOQUOTA); 448: } 449: if (dq == NODQUOT) { 450: tablefull("dquot"); 451: u.u_error = EUSERS; 452: return (dq); 453: } 454: /* 455: * This shouldn't happen, as we sync 456: * dquot before freeing it up. 457: */ 458: if (dq->dq_flags & DQ_MOD) 459: panic("discquota"); 460: 461: /* 462: * Now take the dquot off the free list, 463: */ 464: dp = dq->dq_freef; 465: if (dp != NODQUOT) 466: dp->dq_freeb = &dqfreel; 467: dqfreel = dp; 468: /* 469: * and off the hash chain it was on, & onto the new one. 470: */ 471: dh = &dqhead[DQHASH(uid, dev)]; 472: remque(dq); 473: insque(dq, dh); 474: dq->dq_cnt = 1; 475: dq->dq_flags = 0; 476: dq->dq_uid = uid; 477: dq->dq_dev = dev; 478: dq->dq_dqb = zdqb; 479: dq->dq_own = NOQUOTA; 480: return (dq); 481: } 482: 483: /* 484: * dqrele - layman's interface to putdq. 485: */ 486: dqrele(dq) 487: register struct dquot *dq; 488: { 489: register struct mount *mp; 490: 491: if (dq == NODQUOT || dq == LOSTDQUOT) 492: return; 493: if (dq->dq_cnt > 1) { 494: dq->dq_cnt--; 495: return; 496: } 497: /* 498: * I/O required, find appropriate file system 499: * to sync the quota information to. 500: */ 501: for (mp = mount; mp < &mount[NMOUNT]; mp++) 502: if (mp->m_bufp && mp->m_dev == dq->dq_dev) { 503: putdq(mp, dq, 1); 504: return; 505: } 506: panic("dqrele"); 507: } 508: 509: /* 510: * Update the disc quota in the quota file. 511: */ 512: putdq(mp, dq, free) 513: register struct mount *mp; 514: register struct dquot *dq; 515: { 516: register struct inode *ip; 517: 518: if (dq == NODQUOT || dq == LOSTDQUOT) 519: return; 520: if (free && dq->dq_cnt > 1) { 521: dq->dq_cnt--; 522: return; 523: } 524: /* 525: * Disk quota not modified, just discard 526: * or return (having adjusted the reference 527: * count), as indicated by the "free" param. 528: */ 529: if ((dq->dq_flags & DQ_MOD) == 0) { 530: if (free) { 531: dq->dq_cnt = 0; 532: release: 533: if (dqfreel != NODQUOT) { 534: *dqback = dq; 535: dq->dq_freeb = dqback; 536: } else { 537: dqfreel = dq; 538: dq->dq_freeb = &dqfreel; 539: } 540: dq->dq_freef = NODQUOT; 541: dqback = &dq->dq_freef; 542: } 543: return; 544: } 545: /* 546: * Quota modified, write back to disk. 547: */ 548: while (dq->dq_flags & DQ_LOCK) { 549: dq->dq_flags |= DQ_WANT; 550: sleep((caddr_t)dq, PINOD+2); 551: /* someone could sneak in and grab it */ 552: if (free && dq->dq_cnt > 1) { 553: dq->dq_cnt--; 554: return; 555: } 556: } 557: dq->dq_flags |= DQ_LOCK; 558: if ((ip = mp->m_qinod) == NULL) 559: panic("lost quota file"); 560: ILOCK(ip); 561: (void) rdwri(UIO_WRITE, ip, (caddr_t)&dq->dq_dqb, sizeof (struct dqblk), 562: (off_t)dq->dq_uid * sizeof (struct dqblk), 1, (int *)0); 563: IUNLOCK(ip); 564: if (dq->dq_flags & DQ_WANT) 565: wakeup((caddr_t)dq); 566: dq->dq_flags &= ~(DQ_MOD|DQ_LOCK|DQ_WANT); 567: if (free && --dq->dq_cnt == 0) 568: goto release; 569: } 570: 571: /* 572: * See if there is a quota struct in core for user 'uid'. 573: */ 574: struct quota * 575: qfind(uid) 576: register uid_t uid; 577: { 578: register struct quota *q; 579: register struct qhash *qh; 580: 581: /* 582: * Check common cases first: asking for own quota, 583: * or that of the super user (has reserved slot 0 584: * in the table). 585: */ 586: q = u.u_quota; 587: if (q != NOQUOTA && q->q_uid == uid) 588: return (q); 589: if (uid == 0) /* the second most likely case */ 590: return (quota); 591: /* 592: * Search cache. 593: */ 594: qh = &qhash[QHASH(uid)]; 595: for (q = (Qptr)qh->qh_forw; q != (Qptr)qh; q = q->q_forw) 596: if (q->q_uid == uid) 597: return (q); 598: return (NOQUOTA); 599: } 600: 601: /* 602: * Set the quota file up for a particular file system. 603: * Called as the result of a setquota system call. 604: */ 605: opendq(mp, fname) 606: register struct mount *mp; 607: caddr_t fname; 608: { 609: register struct inode *ip; 610: register struct quota *q; 611: struct dquot *dq; 612: register struct nameidata *ndp = &u.u_nd; 613: int i; 614: 615: if (mp->m_qinod) 616: closedq(mp); 617: ndp->ni_nameiop = LOOKUP | FOLLOW; 618: ndp->ni_segflg = UIO_USERSPACE; 619: ndp->ni_dirp = fname; 620: ip = namei(ndp); 621: if (ip == NULL) 622: return; 623: IUNLOCK(ip); 624: if (ip->i_dev != mp->m_dev) { 625: u.u_error = EACCES; 626: return; 627: } 628: if ((ip->i_mode & IFMT) != IFREG) { 629: u.u_error = EACCES; 630: return; 631: } 632: /* 633: * Flush in-core references to any previous 634: * quota file for this file system. 635: */ 636: mp->m_qinod = ip; 637: i = mp - mount; 638: for (q = quota; q < quotaNQUOTA; q++) 639: if ((q->q_flags & Q_NDQ) == 0) { 640: if (q->q_cnt == 0) 641: q->q_dq[i] = LOSTDQUOT; 642: else { 643: q->q_cnt++; /* cannot be released */ 644: dq = discquota(q->q_uid, ip); 645: q->q_dq[i] = dq; 646: if (dq != NODQUOT) 647: dq->dq_own = q; 648: delquota(q); 649: } 650: } 651: } 652: 653: /* 654: * Close off disc quotas for a file system. 655: */ 656: closedq(mp) 657: register struct mount *mp; 658: { 659: register struct dquot *dq; 660: register i = mp - mount; 661: register struct quota *q; 662: register struct inode *ip; 663: 664: if (mp->m_qinod == NULL) 665: return; 666: /* 667: * Search inode table, delete any references 668: * to quota file being closed. 669: */ 670: for (ip = inode; ip < inodeNINODE; ip++) 671: if (ip->i_dev == mp->m_dev) { 672: dq = ip->i_dquot; 673: ip->i_dquot = NODQUOT; 674: putdq(mp, dq, 1); 675: } 676: /* 677: * Search quota table, flush any pending 678: * quota info to disk and also delete 679: * references to closing quota file. 680: */ 681: for (q = quota; q < quotaNQUOTA; q++) { 682: if ((q->q_flags & Q_NDQ) == 0) { 683: if (q->q_cnt) { 684: q->q_cnt++; 685: putdq(mp, q->q_dq[i], 1); 686: delquota(q); 687: } else 688: putdq(mp, q->q_dq[i], 1); 689: } 690: q->q_dq[i] = NODQUOT; 691: } 692: 693: /* 694: * Move all dquot's that used to refer to this quota 695: * file of into the never-never (they will eventually 696: * fall off the head of the free list and be re-used). 697: */ 698: for (dq = dquot; dq < dquotNDQUOT; dq++) 699: if (dq->dq_dev == mp->m_dev) { 700: if (dq->dq_cnt) 701: panic("closedq: stray dquot"); 702: remque(dq); 703: dq->dq_forw = dq; 704: dq->dq_back = dq; 705: dq->dq_dev = NODEV; 706: } 707: irele(mp->m_qinod); 708: mp->m_qinod = NULL; 709: } 710: #endif