if (ce->lock)                cel = &bc.locked;            else                cel = &bc.normal;                            /* now put this ent at the head of the appropriate list */            add_to_head(cel, ce);            if (data != NULL)                data = (void *)((char *)data + bsize);            bnum       += 1;            num_blocks -= 1;            continue;        } else {                                  /* it's not in the cache */            int        cur, cur_nblocks, num_dirty, real_nblocks, num_needed;            cache_ent *ents[NUM_FLUSH_BLOCKS];            /*               here we find out how many additional blocks in this request               are not in the cache.  the idea is that then we can do one               big i/o on that many blocks at once.            */               for(cur_nblocks=1;                cur_nblocks < num_blocks && cur_nblocks < NUM_FLUSH_BLOCKS;                cur_nblocks++) {                /* we can call hash_lookup() directly instead of                   block_lookup() because we don't care about the                    state of the busy bit of the block at this point                */                if (hash_lookup(&bc.ht, dev, bnum + cur_nblocks))                    break;            }            /*              here we try to figure out how many extra blocks we should read              for read-ahead.  we want to read as many as possible that are              not already in the cache and that don't cause us to try and               read beyond the end of the disk.            */            if ((op & CACHE_READ) && (op & CACHE_READ_AHEAD_OK) &&                (cur_nblocks * bsize) < read_ahead_size) {                for(num_needed=cur_nblocks;                    num_needed < (read_ahead_size / bsize);                    num_needed++) {                    if ((bnum + num_needed) >= max_device_blocks[dev])                        break;                    if (hash_lookup(&bc.ht, dev, bnum + num_needed))                        break;                }            } else {                num_needed = cur_nblocks;            }            /* this will get us pointers to a bunch of cache_ents we can use */            get_ents(ents, num_needed, NUM_FLUSH_BLOCKS, &real_nblocks, bsize);                        if (real_nblocks < num_needed) {                panic("don't have enough cache ents (need %d got %d %ld::%d)\n",                      num_needed, real_nblocks, bnum, num_blocks);            }            /*              There are now three variables used as limits within the ents              array.  This is how they are related:                 cur_nblocks <= num_needed <= real_nblocks              Ents from 0 to cur_nblocks-1 are going to be used to fulfill              this IO request.  Ents from cur_nblocks to num_needed-1 are              for read-ahead.  Ents from num_needed to real_nblocks are              extra blocks that get_ents() asked us to flush.  Often (and              always on writes) cur_nblocks == num_needed.              Below, we sort the list of ents so that when we flush them              they go out in order.             */                        qsort(ents, real_nblocks, sizeof(cache_ent **), cache_ent_cmp);            /*              delete each ent from its list because it will change.  also              count up how many dirty blocks there are and insert into the              hash table any new blocks so that no one else will try to               read them in when we release the cache semaphore to do our I/O.            */            for(cur=0,num_dirty=0; cur < real_nblocks; cur++) {                ce = ents[cur];                ce->flags |= CE_BUSY;                /*                   insert the new block into the hash table with its new block                   number. note that the block is still in the hash table for                    its old block number -- and it has to be until we are done                   flushing it from the cache (to prevent someone else from                   sneaking in in front of us and trying to read the same                   block that we're flushing).                */                if (cur < num_needed) {                    if (hash_insert(&bc.ht, dev, bnum + cur, ce) != 0)                        panic("could not insert cache ent for %d %ld (0x%lx)\n",                              dev, bnum + cur, (ulong)ents[cur]);                }                if (ce->dev == -1)                    continue;                                if ((ce->flags & CE_DIRTY) || ce->clone)                    num_dirty++;                if (ce->lock)                    panic("cbio: can't use locked blocks here ce @ 0x%x\n",ce);                else                    cel = &bc.normal;                                delete_from_list(cel, ce);            }            ce = NULL;            /*               we release the block cache semaphore here so that we can               go do all the i/o we need to do (flushing dirty blocks               that we're kicking out as well as reading any new data).               because all the blocks we're touching are marked busy               no one else should mess with them while we're doing this.            */            if (num_dirty || (op & CACHE_READ)) {                UNLOCK(bc.lock);                                /* this flushes any blocks we're kicking out that are dirty */                if (num_dirty && (err = flush_ents(ents, real_nblocks)) != 0) {                    printf("flush ents failed (ents @ 0x%lx, nblocks %d!\n",                           (ulong)ents, cur_nblocks);                    goto handle_err;                }                            }                        /*               now that everything is flushed to disk, go through and               make sure that the data blocks we're going to use are               the right block size for this current request (it's               possible we're kicking out some smaller blocks and need               to reallocate the data block pointer). We do this in two               steps, first free'ing everything and then going through               and doing the malloc's to try and be nice to the memory               system (i.e. allow it to coalesce stuff, etc).            */            err = 0;            for(cur=0; cur < num_needed; cur++) {                if (ents[cur]->bsize != bsize) {                    free(ents[cur]->data);                    ents[cur]->data = NULL;                    if (ents[cur]->clone) {                        free(ents[cur]->clone);                        ents[cur]->clone = NULL;                    }                }            }                            for(cur=0; cur < num_needed; cur++) {                if (ents[cur]->data == NULL) {                    ents[cur]->data  = (void *)malloc(bsize);                    ents[cur]->bsize = bsize;                }                                if (ents[cur]->data == NULL) {                    printf("cache: no memory for block (bsize %d)!\n",                           bsize);                    err = ENOMEM;                    break;                }            }            /*               if this condition is true it's a pretty serious error.               we'll try and back out gracefully but we're in pretty               deep at this point and it ain't going to be easy.            */  handle_err:            if (err) {                for(cur=0; cur < num_needed; cur++) {                    cache_ent *tmp_ce;                                        tmp_ce = (cache_ent *)hash_delete(&bc.ht,dev,bnum+cur);                    if (tmp_ce != ents[cur]) {                        panic("hash_del0: %d %ld got 0x%lx, not 0x%lx\n",                                dev, bnum+cur, (ulong)tmp_ce,                                (ulong)ents[cur]);                    }                    tmp_ce = (cache_ent *)hash_delete(&bc.ht,ents[cur]->dev,                                                        ents[cur]->block_num);                    if (tmp_ce != ents[cur]) {                        panic("hash_del1: %d %ld got 0x%lx, not 0x%lx\n",                                ents[cur]->dev, ents[cur]->block_num, (ulong)tmp_ce,                                (ulong)ents[cur]);                    }                                        ents[cur]->flags &= ~CE_BUSY;                    if (ents[cur]->data)                        free(ents[cur]->data);                    free(ents[cur]);                    ents[cur] = NULL;                    bc.cur_blocks--;                }                if (cur < real_nblocks) {                    LOCK(bc.lock);                    for(; cur < real_nblocks; cur++) {                        ents[cur]->flags &= ~CE_BUSY;                        /* we have to put them back here */                        add_to_tail(&bc.normal, ents[cur]);                    }                    UNLOCK(bc.lock);                }                return ENOMEM;            }                            /*               If we go into this if statement, the block cache lock               has *already been released* up above when we flushed the               dirty entries.  As always, since the blocks we're mucking               with are marked busy, they shouldn't get messed with.            */            err = 0;            if (num_dirty || (op & CACHE_READ)) {                /* this section performs the i/o that we need to do */                if (op & CACHE_READ) {                    err = read_into_ents(dev, bnum, ents, num_needed, bsize);                } else {                    err = 0;                }                if (err != 0) {                    printf("err %s on dev %d block %ld:%d (%d) "                           "data 0x%x, ents[0] 0x%x\n",                           strerror(errno), dev, bnum, cur_nblocks,                           bsize, data, ents[0]);                }                /*                   acquire the semaphore here so that we can go on mucking                    with the cache data structures.  We need to delete old                    block numbers from the hash table and set the new block                    number's for the blocks we just read in.  We also put the                    read-ahead blocks at the head of mru list.                */                   LOCK(bc.lock);            }            for(cur=0; cur < num_needed; cur++) {                cache_ent *tmp_ce;                                ce = ents[cur];                if (ce->dev != -1) {                    tmp_ce = hash_delete(&bc.ht, ce->dev, ce->block_num);                    if (tmp_ce == NULL || tmp_ce != ce) {                        panic("*** hash_delete failure (ce 0x%x tce 0x%x)\n",                              ce, tmp_ce);                    }                }                if (err == 0 && cur >= cur_nblocks) {                    ce->dev       = dev;                    ce->block_num = bnum + cur;                    ce->flags    &= ~CE_BUSY;                    add_to_head(&bc.normal, ce);                }            }            ce = NULL;            /*              clear the busy bit on the blocks we force-flushed and              put them on the normal list since they're now clean.            */            for(; cur < real_nblocks; cur++) {                ents[cur]->flags &= ~CE_BUSY;                                if (ents[cur]->lock)                    panic("should not have locked blocks here (ce 0x%x)\n",                          ents[cur]);                                add_to_tail(&bc.normal, ents[cur]);            }            if (err) {   /* then we have some cleanup to do */                for(cur=0; cur < num_needed; cur++) {                    cache_ent *tmp_ce;                                        /* we delete all blocks from the cache so we don't                       leave partially written blocks in the cache */                                        tmp_ce = (cache_ent *)hash_delete(&bc.ht,dev,bnum+cur);                    if (tmp_ce != ents[cur]) {                        panic("hash_del: %d %ld got 0x%lx, not 0x%lx\n",                                dev, bnum+cur, (ulong)tmp_ce,                                (ulong)ents[cur]);                    }                    ce = ents[cur];                    ce->flags &= ~CE_BUSY;                                    free(ce->data);                    ce->data = NULL;                    free(ce);                    ents[cur] = NULL;                    bc.cur_blocks--;                }                ce = NULL;                UNLOCK(bc.lock);                return err;            }            /*               last step: go through and make sure all the cache_ent               structures have the right data in them, delete old guys, etc.            */               for(cur=0; cur < cur_nblocks; cur++) {                ce = ents[cur];                                if (ce->dev != -1) {   /* then clean this guy up */                    if (ce->next || ce->prev)                        panic("ce @ 0x%x should not be in a list yet!\n", ce);                    if (ce->clone)                        free(ce->clone);                    if (ce->data == NULL)                        panic("ce @ 0x%lx has a null data ptr\n", (ulong)ce);                }                ce->dev        = dev;                ce->block_num  = bnum + cur;                ce->bsize      = bsize;                ce->flags      = CE_NORMAL;                ce->lock       = 0;                ce->clone      = NULL;                ce->func = ce->arg  = NULL;                ce->next = ce->prev = NULL;                if (op & CACHE_READ) {                    if (data)                        memcpy(data, ce->data, bsize);                } else if (op & CACHE_WRITE) {                    ce->flags  |= CE_DIRTY;                    memcpy(ce->data, data, bsize);                } else if (op & CACHE_NOOP) {                    memset(ce->data, 0, bsize);                    if (data)                        memset(data, 0, bsize);                    ce->flags |= CE_DIRTY;                }                if (op & CACHE_LOCKED) {                    ce->lock++;                    cel = &bc.locked;                } else {                    cel = &bc.normal;                }                /* now stick this puppy at the head of the mru list */                add_to_head(cel, ce);                if (dataptr) {                    *dataptr = ce->data;                }                                if (data != NULL)                    data = (void *)((char *)data + bsize);                else if (cur_nblocks != 1)                    panic("cache can't handle setting data_ptr twice!\n");            }  /* end of for(cur=0; cur < cur_nblocks; cur++) */                            bnum       += cur_nblocks;            num_blocks -= cur_nblocks;        }   /* end of else it's not in the cache */            }   /* end of while(num_blocks) */    UNLOCK(bc.lock);    return 0;}void *get_block(int dev, fs_off_t bnum, int bsize){    void *data;    if (cache_block_io(dev, bnum, NULL, 1, bsize, CACHE_READ|CACHE_LOCKED|CACHE_READ_AHEAD_OK,                       &data) != 0)        return NULL;    return data;}void *get_empty_block(int dev, fs_off_t bnum, int bsize){    void *data;    if (cache_block_io(dev, bnum, NULL, 1, bsize, CACHE_NOOP|CACHE_LOCKED,                       &data) != 0)        return NULL;    return data;}intcached_read(int dev, fs_off_t bnum, void *data, fs_off_t num_blocks, int bsize){    return cache_block_io(dev, bnum, data, num_blocks, bsize,                          CACHE_READ | CACHE_READ_AHEAD_OK, NULL);}intcached_write(int dev, fs_off_t bnum, const void *data, fs_off_t num_blocks,int bsize){    return cache_block_io(dev, bnum, (void *)data, num_blocks, bsize,                          CACHE_WRITE, NULL);}intcached_write_locked(int dev, fs_off_t bnum, const void *data,                    fs_off_t num_blocks, int bsize){    return cache_block_io(dev, bnum, (void *)data, num_blocks, bsize,                          CACHE_WRITE | CACHE_LOCKED, NULL);}voidforce_cache_flush(int dev, int prefer_log_blocks){    int        i, count = 0;    cache_ent *ce;    cache_ent *ents[NUM_FLUSH_BLOCKS];        LOCK(bc.lock);    for(ce=bc.normal.lru; ce; ce=ce->next) {        if ((ce->dev == dev) &&            (ce->flags & CE_BUSY) == 0 &&            ((ce->flags & CE_DIRTY) || ce->clone) &&             ((prefer_log_blocks && ce->func) || (prefer_log_blocks == 0))) {            ce->flags |= CE_BUSY;            ents[count++] = ce;                        if (count >= NUM_FLUSH_BLOCKS) {                break;            }