# rpmdb/falloc.c

Go to the documentation of this file.

    00001
    00014 #include "system.h"
    00015 #include <rpmio_internal.h>
    00016 #include <rpmmessages.h>
    00017 #include <rpmerr.h>
    00018 #include "falloc.h"
    00019 #include "debug.h"
    00020
    00023 #define FA_MAGIC      0x02050920
    00024
    00025 struct faFileHeader {
    00026     unsigned int magic;
    00027     unsigned int firstFree;
    00028 };
    00029
    00030 struct faHeader {
    00031     unsigned int size;
    00032     unsigned int freeNext; /* offset of the next free block, 0 if none */
    00033     unsigned int freePrev;
    00034     unsigned int isFree;
    00035
    00036     /* note that the u16's appear last for alignment/space reasons */
    00037 };
    00038
    00039 struct faFooter {
    00040     unsigned int size;
    00041     unsigned int isFree;
    00042 } ;
    00043
    00044 /* =============================================================== */
    00045 /*@-nullassign@*/
    00046 static struct FDIO_s fadio_s = {
    00047   NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,
    00048   fadOpen, NULL, NULL,  NULL, NULL, NULL, NULL, NULL, NULL
    00049 };
    00050 /*@=nullassign@*/
    00051 FDIO_t fadio = /*@-compmempass@*/ &fadio_s /*@=compmempass@*/ ;
    00052 /* =============================================================== */
    00053
    00057 static
    00058 ssize_t Pread(FD_t fd, void * buf, size_t count, _libio_off_t offset)
    00059         /*@globals fileSystem @*/
    00060         /*@modifies fd, *buf, fileSystem @*/
    00061 {
    00062     if (Fseek(fd, offset, SEEK_SET) < 0)
    00063         return -1;
    00064     /*@-sizeoftype@*/
    00065     return Fread(buf, sizeof(char), count, fd);
    00066     /*@=sizeoftype@*/
    00067 }
    00068
    00072 static
    00073 ssize_t Pwrite(FD_t fd, const void * buf, size_t count, _libio_off_t offset)
    00074         /*@globals fileSystem @*/
    00075         /*@modifies fd, fileSystem @*/
    00076 {
    00077     if (Fseek(fd, offset, SEEK_SET) < 0)
    00078         return -1;
    00079     /*@-sizeoftype@*/
    00080     return Fwrite(buf, sizeof(char), count, fd);
    00081     /*@=sizeoftype@*/
    00082 }
    00083
    00084 /* flags are the same as for open(2) - NULL returned on error */
    00085 FD_t fadOpen(const char * path, int flags, mode_t perms)
    00086 {
    00087     struct faFileHeader newHdr;
    00088     FD_t fd;
    00089
    00090     if (flags & O_WRONLY)
    00091         return NULL;
    00092
    00093     /*@-type@*/ /* FIX: cast? */
    00094     fd = ufdio->_open(path, flags, perms);
    00095     /*@=type@*/
    00096     if (Ferror(fd))
    00097         /* XXX Fstrerror */
    00098         return NULL;
    00099
    00100     /*@-modobserver -observertrans -mods @*/
    00101     memcpy(fadio, fdio, sizeof(*fadio));
    00102     fadio->_open = fadOpen;
    00103     /*@=modobserver =observertrans =mods @*/
    00104
    00105     fdSetIo(fd, fadio);
    00106     fadSetFirstFree(fd, 0);
    00107     fadSetFileSize(fd, Fseek(fd, 0, SEEK_END));
    00108
    00109     /* is this file brand new? */
    00110     if (fadGetFileSize(fd) == 0) {
    00111         newHdr.magic = FA_MAGIC;
    00112         newHdr.firstFree = 0;
    00113         /*@-sizeoftype@*/
    00114         if (Fwrite(&newHdr, sizeof(char), sizeof(newHdr), fd) != sizeof(newHdr)) {
    00115             (void) Fclose(fd);
    00116             return NULL;
    00117         }
    00118         /*@=sizeoftype@*/
    00119         fadSetFirstFree(fd, 0);
    00120         fadSetFileSize(fd, sizeof(newHdr));
    00121     } else {
    00122         memset(&newHdr, 0, sizeof(newHdr));
    00123         if (Pread(fd, &newHdr, sizeof(newHdr), 0) != sizeof(newHdr)) {
    00124             (void) Fclose(fd);
    00125             return NULL;
    00126         }
    00127         if (newHdr.magic != FA_MAGIC) {
    00128             (void) Fclose(fd);
    00129             return NULL;
    00130         }
    00131         fadSetFirstFree(fd, newHdr.firstFree);
    00132         fadSetFileSize(fd, Fseek(fd, 0, SEEK_END));
    00133
    00134         if (fadGetFileSize(fd) < 0) {
    00135             (void) Fclose(fd);
    00136             return NULL;
    00137         }
    00138     }
    00139
    00140     /*@-refcounttrans@*/ return fd /*@=refcounttrans@*/ ;
    00141 }
    00142
    00143 /* returns 0 on failure */
    00144 unsigned int fadAlloc(FD_t fd, unsigned int size)
    00145 {
    00146     unsigned int nextFreeBlock;
    00147     unsigned int newBlockOffset;
    00148     unsigned int footerOffset;
    00149     int failed = 0;
    00150     struct faFileHeader faHeader;
    00151     struct faHeader header, origHeader;
    00152     struct faHeader * restoreHeader = NULL;
    00153     struct faHeader nextFreeHeader, origNextFreeHeader;
    00154     struct faHeader * restoreNextHeader = NULL;
    00155     struct faHeader prevFreeHeader, origPrevFreeHeader;
    00156     struct faHeader * restorePrevHeader = NULL;
    00157     struct faFooter footer, origFooter;
    00158     struct faFooter * restoreFooter = NULL;
    00159     int updateHeader = 0;
    00160
    00161     memset(&header, 0, sizeof(header));
    00162
    00163     /* our internal idea of size includes overhead */
    00164     /*@-sizeoftype@*/
    00165     size += sizeof(struct faHeader) + sizeof(struct faFooter);
    00166     /*@=sizeoftype@*/
    00167
    00168     /* Make sure they are allocing multiples of 64 bytes. It'll keep
    00169        things less fragmented that way */
    00170     (size % 64) ? size += (64 - (size % 64)) : 0;
    00171
    00172     /* find a block via first fit - see Knuth vol 1 for why */
    00173     /* XXX this could be optimized a bit still */
    00174
    00175     nextFreeBlock = fadGetFirstFree(fd);
    00176     newBlockOffset = 0;
    00177
    00178     while (nextFreeBlock && !newBlockOffset) {
    00179         if (Pread(fd, &header, sizeof(header), nextFreeBlock) != sizeof(header)) return 0;
    00180
    00181 /* XXX W2DO? exit(EXIT_FAILURE) forces the user to discover rpm --rebuilddb */
    00182         if (!header.isFree) {
    00183             rpmError(RPMERR_FREELIST, _("free list corrupt (%u)- please run\n"
    00184                         "\t\"rpm --rebuilddb\"\n"
    00185                         "More information is available from http://www.rpm.org "
    00186                         "or the rpm-list@redhat.com mailing list\n"
    00187                         "if \"rpm --rebuilddb\" fails to correct the problem.\n"),
    00188                         nextFreeBlock);
    00189
    00190             exit(EXIT_FAILURE);
    00191             /*@notreached@*/
    00192         }
    00193
    00194         if (header.size >= size) {
    00195             newBlockOffset = nextFreeBlock;
    00196         } else {
    00197             nextFreeBlock = header.freeNext;
    00198         }
    00199     }
    00200
    00201     if (newBlockOffset) {
    00202         /* header should still be good from the search */
    00203         origHeader = header;
    00204
    00205         footerOffset = newBlockOffset + header.size - sizeof(footer);
    00206
    00207         if (Pread(fd, &footer, sizeof(footer), footerOffset) != sizeof(footer))
    00208             return 0;
    00209         origFooter = footer;
    00210
    00211         /* should we split this block into two? */
    00212         /* XXX implement fragment creation here */
    00213
    00214         footer.isFree = header.isFree = 0;
    00215
    00216         /* remove it from the free list before */
    00217         if (newBlockOffset == fadGetFirstFree(fd)) {
    00218             faHeader.magic = FA_MAGIC;
    00219             faHeader.firstFree = header.freeNext;
    00220             fadSetFirstFree(fd, header.freeNext);
    00221             updateHeader = 1;
    00222         } else {
    00223             if (Pread(fd, &prevFreeHeader, sizeof(prevFreeHeader),
    00224                         header.freePrev) != sizeof(prevFreeHeader))
    00225                 return 0;
    00226             origPrevFreeHeader = prevFreeHeader;
    00227
    00228             prevFreeHeader.freeNext = header.freeNext;
    00229         }
    00230
    00231         /* and after */
    00232         if (header.freeNext) {
    00233             if (Pread(fd, &nextFreeHeader, sizeof(nextFreeHeader),
    00234                         header.freeNext) != sizeof(nextFreeHeader))
    00235                 return 0;
    00236             origNextFreeHeader = nextFreeHeader;
    00237
    00238             nextFreeHeader.freePrev = header.freePrev;
    00239         }
    00240
    00241         /* if any of these fail, try and restore everything before leaving */
    00242         if (updateHeader) {
    00243             if (Pwrite(fd, &faHeader, sizeof(faHeader), 0) !=
    00244                              sizeof(faHeader))
    00245                 return 0;
    00246         } else {
    00247             if (Pwrite(fd, &prevFreeHeader, sizeof(prevFreeHeader),
    00248                         header.freePrev) != sizeof(prevFreeHeader))
    00249                 return 0;
    00250             restorePrevHeader = &origPrevFreeHeader;
    00251         }
    00252
    00253         if (header.freeNext) {
    00254             if (Pwrite(fd, &nextFreeHeader, sizeof(nextFreeHeader),
    00255                         header.freeNext) != sizeof(nextFreeHeader))
    00256                 return 0;
    00257
    00258             restoreNextHeader = &origNextFreeHeader;
    00259         }
    00260
    00261         if (!failed) {
    00262             if (Pwrite(fd, &header, sizeof(header), newBlockOffset) !=
    00263                          sizeof(header)) {
    00264                 failed = 1;
    00265                 restoreHeader = &origHeader;
    00266             }
    00267         }
    00268
    00269         if (!failed) {
    00270             if (Pwrite(fd, &footer, sizeof(footer),
    00271                         footerOffset) != sizeof(footer)) {
    00272                 failed = 1;
    00273                 restoreFooter = &origFooter;
    00274             }
    00275         }
    00276
    00277         if (failed) {
    00278             if (updateHeader) {
    00279                 faHeader.firstFree = newBlockOffset;
    00280                 fadSetFirstFree(fd, newBlockOffset);
    00281                 (void)Pwrite(fd, &faHeader, sizeof(faHeader), 0);
    00282             }
    00283
    00284             if (restorePrevHeader)
    00285                 (void)Pwrite(fd, restorePrevHeader, sizeof(*restorePrevHeader),
    00286                                 header.freePrev);
    00287
    00288             if (restoreNextHeader)
    00289                 (void)Pwrite(fd, restoreNextHeader, sizeof(*restoreNextHeader),
    00290                                 header.freeNext);
    00291
    00292             if (restoreHeader)
    00293                 (void)Pwrite(fd, restoreHeader, sizeof(header),
    00294                                 newBlockOffset);
    00295
    00296             if (restoreFooter)
    00297                 (void)Pwrite(fd, restoreFooter, sizeof(footer),
    00298                                 footerOffset);
    00299
    00300             return 0;
    00301         }
    00302     } else {
    00303         char * space;
    00304
    00305         /* make a new block */
    00306         newBlockOffset = fadGetFileSize(fd);
    00307         footerOffset = newBlockOffset + size - sizeof(footer);
    00308
    00309         space = alloca(size);
    00310         if (space == NULL) return 0;
    00311         memset(space, 0, size);
    00312
    00313         footer.isFree = header.isFree = 0;
    00314         footer.size = header.size = size;
    00315         header.freePrev = header.freeNext = 0;
    00316
    00317         /* reserve all space up front */
    00318         /* XXX TODO: check max. no. of bytes to write */
    00319         if (Pwrite(fd, space, size, newBlockOffset) != size)
    00320             return 0;
    00321
    00322         if (Pwrite(fd, &header, sizeof(header), newBlockOffset) != sizeof(header))
    00323             return 0;
    00324
    00325         if (Pwrite(fd, &footer, sizeof(footer), footerOffset) != sizeof(footer))
    00326             return 0;
    00327
    00328         fadSetFileSize(fd, fadGetFileSize(fd) + size);
    00329     }
    00330
    00331     return newBlockOffset + sizeof(header);
    00332 }
    00333
    00334 void fadFree(FD_t fd, unsigned int offset)
    00335 {
    00336     struct faHeader header;
    00337     struct faFooter footer;
    00338     int footerOffset;
    00339     int prevFreeOffset, nextFreeOffset;
    00340     struct faHeader prevFreeHeader, nextFreeHeader;
    00341     struct faFileHeader faHeader;
    00342
    00343     /* any errors cause this to die, and thus result in lost space in the
    00344        database. which is at least better then corruption */
    00345
    00346     offset -= sizeof(header);
    00347
    00348     /* find out where in the (sorted) free list to put this */
    00349     prevFreeOffset = fadGetFirstFree(fd);
    00350
    00351     if (!prevFreeOffset || (prevFreeOffset > offset)) {
    00352         nextFreeOffset = fadGetFirstFree(fd);
    00353         prevFreeOffset = 0;
    00354     } else {
    00355         memset(&prevFreeHeader, 0, sizeof(prevFreeHeader));
    00356         if (Pread(fd, &prevFreeHeader, sizeof(prevFreeHeader),
    00357                         prevFreeOffset) != sizeof(prevFreeHeader))
    00358             return;
    00359
    00360         while (prevFreeHeader.freeNext && prevFreeHeader.freeNext < offset) {
    00361             prevFreeOffset = prevFreeHeader.freeNext;
    00362             if (Pread(fd, &prevFreeHeader, sizeof(prevFreeHeader),
    00363                         prevFreeOffset) != sizeof(prevFreeHeader))
    00364                 return;
    00365         }
    00366
    00367         nextFreeOffset = prevFreeHeader.freeNext;
    00368     }
    00369
    00370     if (nextFreeOffset) {
    00371         memset(&nextFreeHeader, 0, sizeof(nextFreeHeader));
    00372         if (Pread(fd, &nextFreeHeader, sizeof(nextFreeHeader),
    00373                         nextFreeOffset) != sizeof(nextFreeHeader))
    00374             return;
    00375     }
    00376
    00377     memset(&header, 0, sizeof(header));
    00378     if (Pread(fd, &header, sizeof(header), offset) != sizeof(header))
    00379         return;
    00380
    00381     footerOffset = offset + header.size - sizeof(footer);
    00382
    00383     memset(&footer, 0, sizeof(footer));
    00384     if (Pread(fd, &footer, sizeof(footer), footerOffset) != sizeof(footer))
    00385         return;
    00386
    00387     header.isFree = 1;
    00388     header.freeNext = nextFreeOffset;
    00389     header.freePrev = prevFreeOffset;
    00390     footer.isFree = 1;
    00391
    00392     /* XXX TODO: set max. no. of bytes to write */
    00393     (void)Pwrite(fd, &header, sizeof(header), offset);
    00394
    00395     (void)Pwrite(fd, &footer, sizeof(footer), footerOffset);
    00396
    00397     if (nextFreeOffset) {
    00398         nextFreeHeader.freePrev = offset;
    00399         if (Pwrite(fd, &nextFreeHeader, sizeof(nextFreeHeader),
    00400                         nextFreeOffset) != sizeof(nextFreeHeader))
    00401             return;
    00402     }
    00403
    00404     if (prevFreeOffset) {
    00405         prevFreeHeader.freeNext = offset;
    00406         if (Pwrite(fd, &prevFreeHeader, sizeof(prevFreeHeader),
    00407                         prevFreeOffset) != sizeof(prevFreeHeader))
    00408             return;
    00409     } else {
    00410         fadSetFirstFree(fd, offset);
    00411
    00412         faHeader.magic = FA_MAGIC;
    00413         faHeader.firstFree = fadGetFirstFree(fd);
    00414
    00415         /* XXX TODO: set max. no. of bytes to write */
    00416         if (Pwrite(fd, &faHeader, sizeof(faHeader), 0) != sizeof(faHeader))
    00417             return;
    00418     }
    00419 }
    00420
    00421 static int fadSanity(FD_t fd, int offset, const struct faHeader * fh, int printit)
    00422         /*@*/
    00423 {
    00424     int rc = 0;
    00425
    00426     /*@-sizeoftype@*/
    00427     /* Check size range and alignment. */
    00428     if (!(fh->size > 0 && fh->size <= 0x00200000 && (fh->size & 0x3f) == 0))
    00429         rc |= 0x1;
    00430
    00431     /* Check forward link range, alignment and offset. */
    00432     if (fh->freeNext &&
    00433         !(      fh->freeNext > sizeof(struct faFileHeader) &&
    00434                 fh->freeNext < fadGetFileSize(fd) &&
    00435                 (fh->freeNext & 0x3f) == sizeof(struct faFileHeader)) )
    00436         rc |= 0x2;
    00437
    00438     /* Check backward link range, alignment and offset. */
    00439     if (fh->freePrev &&
    00440         !(      fh->freePrev > sizeof(struct faFileHeader) &&
    00441                 fh->freePrev < fadGetFileSize(fd) &&
    00442                 (fh->freePrev & 0x3f) == sizeof(struct faFileHeader)) )
    00443         rc |= 0x4;
    00444     /*@=sizeoftype@*/
    00445
    00446     /* Check that only the isFree bit is (possibly) set. */
    00447     if (fh->isFree & ~1)
    00448         rc |= 0x8;
    00449
    00450     if (printit && rc) {
    00451         rpmMessage(RPMMESS_DEBUG,
    00452     "offset %d(0x%08x) rc %d: size 0x%08x next %d(0x%08x) prev %d(0x%08x) isFree 0x%08x\n",
    00453                 offset, (unsigned) offset, rc,
    00454                 (unsigned) fh->size,
    00455                 (int) fh->freeNext, fh->freeNext,
    00456                 (int) fh->freePrev, fh->freePrev,
    00457                 (unsigned) fh->isFree);
    00458     }
    00459     return rc;
    00460 }
    00461
    00462 int fadFirstOffset(FD_t fd)
    00463 {
    00464     return fadNextOffset(fd, 0);
    00465 }
    00466
    00467 int fadNextOffset(FD_t fd, unsigned int lastoff)
    00468 {
    00469     struct faHeader header;
    00470     int offset;
    00471
    00472     /*@-sizeoftype@*/
    00473     offset = (lastoff)
    00474         ? (lastoff - sizeof(header))
    00475         : sizeof(struct faFileHeader);
    00476     /*@=sizeoftype@*/
    00477
    00478     if (offset >= fadGetFileSize(fd))
    00479         return 0;
    00480
    00481     memset(&header, 0, sizeof(header));
    00482     if (Pread(fd, &header, sizeof(header), offset) != sizeof(header))
    00483         return 0;
    00484
    00485     if (!lastoff && header.isFree == 0)
    00486         return (offset + sizeof(header));
    00487
    00488     /*
    00489      * XXX Try to reconnect at next record found. This isn't perfect
    00490      * XXX but handles many common db1 corruption problems.
    00491      */
    00492     if (fadSanity(fd, offset, &header, 0)) {
    00493         struct faHeader myheader;
    00494         int o = offset;
    00495
    00496         memset(&myheader, 0, sizeof(myheader));
    00497         do {
    00498             o += 0x40;  /* XXX allocation chunks are padded to 64b */
    00499             if (o >= fadGetFileSize(fd))
    00500                 return 0;
    00501             if (Pread(fd, &myheader, sizeof(myheader), o) != sizeof(header))
    00502                 return 0;
    00503         } while (fadSanity(fd, o, &myheader, 0));
    00504         return (o + sizeof(header));
    00505     }
    00506
    00507     do {
    00508         offset += header.size;
    00509         if (offset >= fadGetFileSize(fd))
    00510             return 0;
    00511
    00512         if (Pread(fd, &header, sizeof(header), offset) != sizeof(header))
    00513             return 0;
    00514
    00515     } while (header.isFree == 1);
    00516
    00517     /* Sanity check this to make sure we're not going in loops */
    00518     offset += sizeof(header);
    00519     if (offset <= lastoff)
    00520         return 0;       /* XXX used to return -1 */
    00521
    00522     return offset;
    00523 }