isam/physical.c

   1 /*
   2  * Copyright (C) 1994, Index Data I/S
   3  * All rights reserved.
   4  * Sebastian Hammer, Adam Dickmeiss
   5  *
   6  * $Log: physical.c,v $
   7  * Revision 1.13  1996-10-29 13:56:57  adam
   8  * Include of zebrautl.h instead of alexutil.h.
   9  *
  10  * Revision 1.12  1996/03/20 16:17:11  quinn
  11  * Bug hunting
  12  *
  13  * Revision 1.11  1996/03/20  13:29:17  quinn
  14  * Bug-fix
  15  *
  16  * Revision 1.10  1996/03/19  19:22:44  quinn
  17  * Fixed update-bug
  18  *
  19  * Revision 1.9  1996/02/06  10:19:57  quinn
  20  * Attempt at fixing bug. Not all blocks were read before they were unlinked
  21  * prior to a remap operation.
  22  *
  23  * Revision 1.8  1996/01/29  09:47:11  quinn
  24  * Fixed mean little bug in the read-table code.
  25  *
  26  * Revision 1.7  1995/12/06  14:48:27  quinn
  27  * Fixed some strange bugs.
  28  *
  29  * Revision 1.6  1995/09/04  12:33:47  adam
  30  * Various cleanup. YAZ util used instead.
  31  *
  32  * Revision 1.5  1994/09/28  11:29:33  quinn
  33  * Added cmp parameter.
  34  *
  35  * Revision 1.4  1994/09/27  20:03:53  quinn
  36  * Seems relatively bug-free.
  37  *
  38  * Revision 1.3  1994/09/26  17:11:31  quinn
  39  * Trivial
  40  *
  41  * Revision 1.2  1994/09/26  17:06:36  quinn
  42  * Back again...
  43  *
  44  * Revision 1.1  1994/09/26  16:07:57  quinn
  45  * Most of the functionality in place.
  46  *
  47  */
  48
  49 /*
  50  * This module handles the representation of tables in the bfiles.
  51  */
  52
  53 #include <assert.h>
  54 #include <stdio.h>
  55
  56 #include <log.h>
  57 #include <isam.h>
  58
  59 static int is_freestore_alloc(ISAM is, int type)
  60 {
  61     int tmp;
  62
  63     if (is->types[type].freelist >= 0)
  64     {
  65         tmp = is->types[type].freelist;
  66         if (bf_read(is->types[type].bf, tmp, 0, sizeof(tmp),
  67             &is->types[type].freelist) <=0)
  68         {
  69             logf (LOG_FATAL, "Failed to allocate block");
  70             exit(1);
  71         }
  72     }
  73     else
  74         tmp = is->types[type].top++;
  75
  76     logf (LOG_DEBUG, "Allocating block #%d", tmp);
  77     return tmp;
  78 }
  79
  80 static void is_freestore_free(ISAM is, int type, int block)
  81 {
  82     int tmp;
  83
  84     logf (LOG_DEBUG, "Releasing block #%d", block);
  85     tmp = is->types[type].freelist;
  86     is->types[type].freelist = block;
  87     if (bf_write(is->types[type].bf, block, 0, sizeof(tmp), &tmp) < 0)
  88     {
  89         logf (LOG_FATAL, "Failed to deallocate block.");
  90         exit(1);
  91     }
  92 }
  93
  94 /* this code must be modified to handle an index */
  95 int is_p_read_partial(is_mtable *tab, is_mblock *block)
  96 {
  97     int toread;
  98     is_mbuf *buf;
  99
 100     assert(block->state == IS_MBSTATE_UNREAD);
 101     block->data = buf = xmalloc_mbuf(IS_MBUF_TYPE_LARGE);
 102     toread = tab->is->types[tab->pos_type].blocksize;
 103     if (toread > is_mbuf_size[buf->type])
 104     {
 105         toread = is_mbuf_size[buf->type];
 106         block->state = IS_MBSTATE_PARTIAL;
 107     }
 108     else
 109         block->state = IS_MBSTATE_CLEAN;
 110     if (bf_read(tab->is->types[tab->pos_type].bf, block->diskpos, 0, toread,
 111         buf->data) < 0)
 112     {
 113         logf (LOG_FATAL, "bfread failed.");
 114         return -1;
 115     }
 116     /* extract header info */
 117     buf->offset = 0;
 118     memcpy(&block->num_records, buf->data, sizeof(block->num_records));
 119     assert(block->num_records > 0);
 120     buf->offset += sizeof(block->num_records);
 121     memcpy(&block->nextpos, buf->data + buf->offset,
 122         sizeof(block->nextpos));
 123     buf->offset += sizeof(block->nextpos);
 124     if (block == tab->data) /* first block */
 125     {
 126         memcpy(&tab->num_records, buf->data + buf->offset,
 127             sizeof(tab->num_records));
 128         buf->offset +=sizeof(tab->num_records);
 129     }
 130     logf(LOG_DEBUG, "R: Block #%d: num %d nextpos %d total %d",
 131         block->diskpos, block->num_records, block->nextpos,
 132         block == tab->data ? tab->num_records : -1);
 133     buf->num = (toread - buf->offset) / is_keysize(tab->is);
 134     if (buf->num >= block->num_records)
 135     {
 136         buf->num = block->num_records;
 137         block->state = IS_MBSTATE_CLEAN;
 138     }
 139     else
 140         block->bread = buf->offset + buf->num * is_keysize(tab->is);
 141     return 0;
 142 }
 143
 144 int is_p_read_full(is_mtable *tab, is_mblock *block)
 145 {
 146     is_mbuf *buf;
 147     int dread, toread;
 148
 149     if (block->state == IS_MBSTATE_UNREAD && is_p_read_partial(tab, block) < 0)
 150     {
 151         logf (LOG_FATAL, "partial read failed.");
 152         return -1;
 153     }
 154     if (block->state == IS_MBSTATE_PARTIAL)
 155     {
 156         buf = block->data;
 157         dread = block->data->num;
 158         while (dread < block->num_records)
 159         {
 160             buf->next = xmalloc_mbuf(IS_MBUF_TYPE_LARGE);
 161             buf = buf->next;
 162
 163             toread = is_mbuf_size[buf->type] / is_keysize(tab->is);
 164             if (toread > block->num_records - dread)
 165                 toread = block->num_records - dread;
 166
 167             if (bf_read(tab->is->types[tab->pos_type].bf, block->diskpos, block->bread, toread *
 168                 is_keysize(tab->is), buf->data) < 0)
 169             {
 170                 logf (LOG_FATAL, "bfread failed.");
 171                 return -1;
 172             }
 173             buf->offset = 0;
 174             buf->num = toread;
 175             dread += toread;
 176             block->bread += toread * is_keysize(tab->is);
 177         }
 178         block->state = IS_MBSTATE_CLEAN;
 179     }
 180     logf (LOG_DEBUG, "R: Block #%d contains %d records.", block->diskpos, block->num_records);
 181     return 0;
 182 }
 183
 184 /*
 185  * write dirty blocks to bfile.
 186  * Allocate blocks as necessary.
 187  */
 188 void is_p_sync(is_mtable *tab)
 189 {
 190     is_mblock *p;
 191     is_mbuf *b;
 192     int sum, v;
 193     isam_blocktype *type;
 194
 195     type = &tab->is->types[tab->pos_type];
 196     for (p = tab->data; p; p = p->next)
 197     {
 198         if (p->state < IS_MBSTATE_DIRTY)
 199             continue;
 200         /* make sure that blocks are allocated. */
 201         if (p->diskpos < 0)
 202             p->diskpos = is_freestore_alloc(tab->is, tab->pos_type);
 203         if (p->next)
 204         {
 205             if (p->next->diskpos < 0)
 206                 p->nextpos = p->next->diskpos = is_freestore_alloc(tab->is,
 207                     tab->pos_type);
 208             else
 209                 p->nextpos = p->next->diskpos;
 210         }
 211         else
 212             p->nextpos = 0;
 213         sum = 0;
 214         memcpy(type->dbuf, &p->num_records, sizeof(p->num_records));
 215         sum += sizeof(p->num_records);
 216         memcpy(type->dbuf + sum, &p->nextpos, sizeof(p->nextpos));
 217         sum += sizeof(p->nextpos);
 218         if (p == tab->data)  /* first block */
 219         {
 220             memcpy(type->dbuf + sum, &tab->num_records,
 221                 sizeof(tab->num_records));
 222             sum += sizeof(tab->num_records);
 223         }
 224         logf (LOG_DEBUG, "W: Block #%d contains %d records.", p->diskpos,
 225             p->num_records);
 226         assert(p->num_records > 0);
 227         for (b = p->data; b; b = b->next)
 228         {
 229             logf(LOG_DEBUG, "   buf: offset %d, keys %d, type %d, ref %d",
 230                 b->offset, b->num, b->type, b->refcount);
 231             if ((v = b->num * is_keysize(tab->is)) > 0)
 232                 memcpy(type->dbuf + sum, b->data + b->offset, v);
 233
 234             sum += v;
 235             assert(sum <= type->blocksize);
 236         }
 237         if (bf_write(type->bf, p->diskpos, 0, sum, type->dbuf) < 0)
 238         {
 239             logf (LOG_FATAL, "Failed to write block.");
 240             exit(1);
 241         }
 242     }
 243 }
 244
 245 /*
 246  * Free all disk blocks associated with table.
 247  */
 248 void is_p_unmap(is_mtable *tab)
 249 {
 250     is_mblock *p;
 251
 252     for (p = tab->data; p; p = p->next)
 253     {
 254         if (p->diskpos >= 0)
 255         {
 256             is_freestore_free(tab->is, tab->pos_type, p->diskpos);
 257             p->diskpos = -1;
 258         }
 259     }
 260 }
 261
 262 static is_mbuf *mbuf_takehead(is_mbuf **mb, int *num, int keysize)
 263 {
 264     is_mbuf *p = 0, **pp = &p, *new;
 265     int toget = *num;
 266
 267     if (!toget)
 268         return 0;
 269     while (*mb && toget >= (*mb)->num)
 270     {
 271         toget -= (*mb)->num;
 272         *pp = *mb;
 273         *mb = (*mb)->next;
 274         (*pp)->next = 0;
 275         pp = &(*pp)->next;
 276     }
 277     if (toget > 0 && *mb)
 278     {
 279         new = xmalloc_mbuf(IS_MBUF_TYPE_SMALL);
 280         new->next = (*mb)->next;
 281         (*mb)->next = new;
 282         new->data = (*mb)->data;
 283         (*mb)->refcount++;
 284         new->offset = (*mb)->offset + toget * keysize;
 285         new->num = (*mb)->num - toget;
 286         (*mb)->num = toget;
 287         *pp = *mb;
 288         *mb = (*mb)->next;
 289         (*pp)->next = 0;
 290         toget = 0;
 291     }
 292     *num -= toget;
 293     return p;
 294 }
 295
 296 /*
 297  * Split up individual blocks which have grown too large.
 298  * is_p_align and is_p_remap are alternative functions which trade off
 299  * speed in updating versus optimum usage of disk blocks.
 300  */
 301 void is_p_align(is_mtable *tab)
 302 {
 303     is_mblock *mblock, *new, *last = 0, *next;
 304     is_mbuf *mbufs, *mbp;
 305     int blocks, recsblock;
 306
 307     logf (LOG_DEBUG, "Realigning table.");
 308     for (mblock = tab->data; mblock; mblock = next)
 309     {
 310         next = mblock->next;
 311         if (mblock->state == IS_MBSTATE_DIRTY && mblock->num_records == 0)
 312         {
 313             if (last)
 314             {
 315                 last->next = mblock->next;
 316                 last->state = IS_MBSTATE_DIRTY;
 317                 next = mblock->next;
 318             }
 319             else
 320             {
 321                 next = tab->data->next;
 322                 if (next)
 323                 {
 324                     if (next->state < IS_MBSTATE_CLEAN)
 325                     {
 326                         if (is_p_read_full(tab, next) < 0)
 327                         {
 328                             logf(LOG_FATAL, "Error during re-alignment");
 329                             abort();
 330                         }
 331                         if (next->nextpos && !next->next)
 332                         {
 333                             next->next = xmalloc_mblock();
 334                             next->next->diskpos = next->nextpos;
 335                             next->next->state = IS_MBSTATE_UNREAD;
 336                             next->next->data = 0;
 337                         }
 338                     }
 339                     next->state = IS_MBSTATE_DIRTY; /* force re-process */
 340                     tab->data = next;
 341                 }
 342             }
 343             if (mblock->diskpos >= 0)
 344                 is_freestore_free(tab->is, tab->pos_type, mblock->diskpos);
 345             xrelease_mblock(mblock);
 346         }
 347         else if (mblock->state == IS_MBSTATE_DIRTY && mblock->num_records >
 348             (mblock == tab->data ?
 349             tab->is->types[tab->pos_type].max_keys_block0 :
 350             tab->is->types[tab->pos_type].max_keys_block))
 351         {
 352             blocks = tab->num_records /
 353             tab->is->types[tab->pos_type].nice_keys_block;
 354             if (tab->num_records %
 355                 tab->is->types[tab->pos_type].nice_keys_block)
 356                 blocks++;
 357             recsblock = tab->num_records / blocks;
 358             if (recsblock < 1)
 359                 recsblock = 1;
 360             mbufs = mblock->data;
 361             while ((mbp = mbuf_takehead(&mbufs, &recsblock,
 362                 is_keysize(tab->is))) && recsblock)
 363             {
 364                 if (mbufs)
 365                 {
 366                     new = xmalloc_mblock();
 367                     new->diskpos = -1;
 368                     new->state = IS_MBSTATE_DIRTY;
 369                     new->next = mblock->next;
 370                     mblock->next = new;
 371                 }
 372                 mblock->data = mbp;
 373                 mblock->num_records = recsblock;
 374                 last = mblock;
 375                 mblock = mblock->next;
 376             }
 377             next = mblock;
 378         }
 379         else
 380             last = mblock;
 381     }
 382 }
 383
 384 /*
 385  * Reorganize data in blocks for minimum block usage and quick access.
 386  * Free surplus blocks.
 387  * is_p_align and is_p_remap are alternative functions which trade off
 388  * speed in updating versus optimum usage of disk blocks.
 389  */
 390 void is_p_remap(is_mtable *tab)
 391 {
 392     is_mbuf *mbufs, **bufpp, *mbp;
 393     is_mblock *blockp, **blockpp;
 394     int recsblock, blocks;
 395
 396     logf (LOG_DEBUG, "Remapping table.");
 397     /* collect all data */
 398     bufpp = &mbufs;
 399     for (blockp = tab->data; blockp; blockp = blockp->next)
 400     {
 401         if (blockp->state < IS_MBSTATE_CLEAN && is_m_read_full(tab, blockp) < 0)
 402         {
 403             logf (LOG_FATAL, "Read-full failed in remap.");
 404             exit(1);
 405         }
 406         *bufpp = blockp->data;
 407         while (*bufpp)
 408             bufpp = &(*bufpp)->next;
 409         blockp->data = 0;
 410     }
 411     blocks = tab->num_records / tab->is->types[tab->pos_type].nice_keys_block;
 412     if (tab->num_records % tab->is->types[tab->pos_type].nice_keys_block)
 413         blocks++;
 414     if (blocks == 0)
 415         blocks = 1;
 416     recsblock = tab->num_records / blocks + 1;
 417     if (recsblock > tab->is->types[tab->pos_type].nice_keys_block)
 418         recsblock--;
 419     blockpp = &tab->data;
 420     while ((mbp = mbuf_takehead(&mbufs, &recsblock, is_keysize(tab->is))) &&
 421         recsblock)
 422     {
 423         if (!*blockpp)
 424         {
 425             *blockpp = xmalloc_mblock();
 426             (*blockpp)->diskpos = -1;
 427         }
 428         (*blockpp)->data = mbp;
 429         (*blockpp)->num_records = recsblock;
 430         (*blockpp)->state = IS_MBSTATE_DIRTY;
 431         blockpp = &(*blockpp)->next;
 432     }
 433     if (mbp)
 434         xfree_mbufs(mbp);
 435     if (*blockpp)
 436     {
 437         for (blockp = *blockpp; blockp; blockp = blockp->next)
 438             if (blockp->diskpos >= 0)
 439                 is_freestore_free(tab->is, tab->pos_type, blockp->diskpos);
 440         xfree_mblocks(*blockpp);
 441         *blockpp = 0;
 442     }
 443 }