Main Page   Modules   Data Structures   File List   Data Fields   Globals   Related Pages  

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

Generated at Wed Mar 27 03:56:52 2002 for rpm by doxygen1.2.8.1 written by Dimitri van Heesch, © 1997-2001