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

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 }

Generated on Mon Apr 18 03:27:27 2005 for rpm by  doxygen 1.4.1