isam/physical.c

   1 /* $Id: physical.c,v 1.18 2002-08-02 19:26:56 adam Exp $
   2    Copyright (C) 1995,1996,1997,1998,1999,2000,2001,2002
   3    Index Data Aps
   4
   5 This file is part of the Zebra server.
   6
   7 Zebra is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 Zebra is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with Zebra; see the file LICENSE.zebra.  If not, write to the
  19 Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  20 02111-1307, USA.
  21 */
  22
  23
  24
  25 /*
  26  * This module handles the representation of tables in the bfiles.
  27  */
  28
  29 #include <assert.h>
  30 #include <stdio.h>
  31 #include <string.h>
  32
  33 #include <yaz/log.h>
  34 #include <isam.h>
  35
  36 static int is_freestore_alloc(ISAM is, int type)
  37 {
  38     int tmp;
  39
  40     if (is->types[type].freelist >= 0)
  41     {
  42         tmp = is->types[type].freelist;
  43         if (bf_read(is->types[type].bf, tmp, 0, sizeof(tmp),
  44             &is->types[type].freelist) <=0)
  45         {
  46             logf (LOG_FATAL, "Failed to allocate block");
  47             exit(1);
  48         }
  49     }
  50     else
  51         tmp = is->types[type].top++;
  52
  53     logf (LOG_DEBUG, "Allocating block #%d", tmp);
  54     return tmp;
  55 }
  56
  57 static void is_freestore_free(ISAM is, int type, int block)
  58 {
  59     int tmp;
  60
  61     logf (LOG_DEBUG, "Releasing block #%d", block);
  62     tmp = is->types[type].freelist;
  63     is->types[type].freelist = block;
  64     if (bf_write(is->types[type].bf, block, 0, sizeof(tmp), &tmp) < 0)
  65     {
  66         logf (LOG_FATAL, "Failed to deallocate block.");
  67         exit(1);
  68     }
  69 }
  70
  71 /* this code must be modified to handle an index */
  72 int is_p_read_partial(is_mtable *tab, is_mblock *block)
  73 {
  74     int toread;
  75     is_mbuf *buf;
  76
  77     assert(block->state == IS_MBSTATE_UNREAD);
  78     block->data = buf = xmalloc_mbuf(IS_MBUF_TYPE_LARGE);
  79     toread = tab->is->types[tab->pos_type].blocksize;
  80     if (toread > is_mbuf_size[buf->type])
  81     {
  82         toread = is_mbuf_size[buf->type];
  83         block->state = IS_MBSTATE_PARTIAL;
  84     }
  85     else
  86         block->state = IS_MBSTATE_CLEAN;
  87     if (bf_read(tab->is->types[tab->pos_type].bf, block->diskpos, 0, toread,
  88         buf->data) < 0)
  89     {
  90         logf (LOG_FATAL, "bfread failed.");
  91         return -1;
  92     }
  93     /* extract header info */
  94     buf->offset = 0;
  95     memcpy(&block->num_records, buf->data, sizeof(block->num_records));
  96     assert(block->num_records > 0);
  97     buf->offset += sizeof(block->num_records);
  98     memcpy(&block->nextpos, buf->data + buf->offset,
  99         sizeof(block->nextpos));
 100     buf->offset += sizeof(block->nextpos);
 101     if (block == tab->data) /* first block */
 102     {
 103         memcpy(&tab->num_records, buf->data + buf->offset,
 104             sizeof(tab->num_records));
 105         buf->offset +=sizeof(tab->num_records);
 106     }
 107     logf(LOG_DEBUG, "R: Block #%d: num %d nextpos %d total %d",
 108         block->diskpos, block->num_records, block->nextpos,
 109         block == tab->data ? tab->num_records : -1);
 110     buf->num = (toread - buf->offset) / is_keysize(tab->is);
 111     if (buf->num >= block->num_records)
 112     {
 113         buf->num = block->num_records;
 114         block->state = IS_MBSTATE_CLEAN;
 115     }
 116     else
 117         block->bread = buf->offset + buf->num * is_keysize(tab->is);
 118     return 0;
 119 }
 120
 121 int is_p_read_full(is_mtable *tab, is_mblock *block)
 122 {
 123     is_mbuf *buf;
 124     int dread, toread;
 125
 126     if (block->state == IS_MBSTATE_UNREAD && is_p_read_partial(tab, block) < 0)
 127     {
 128         logf (LOG_FATAL, "partial read failed.");
 129         return -1;
 130     }
 131     if (block->state == IS_MBSTATE_PARTIAL)
 132     {
 133         buf = block->data;
 134         dread = block->data->num;
 135         while (dread < block->num_records)
 136         {
 137             buf->next = xmalloc_mbuf(IS_MBUF_TYPE_LARGE);
 138             buf = buf->next;
 139
 140             toread = is_mbuf_size[buf->type] / is_keysize(tab->is);
 141             if (toread > block->num_records - dread)
 142                 toread = block->num_records - dread;
 143
 144             if (bf_read(tab->is->types[tab->pos_type].bf, block->diskpos, block->bread, toread *
 145                 is_keysize(tab->is), buf->data) < 0)
 146             {
 147                 logf (LOG_FATAL, "bfread failed.");
 148                 return -1;
 149             }
 150             buf->offset = 0;
 151             buf->num = toread;
 152             dread += toread;
 153             block->bread += toread * is_keysize(tab->is);
 154         }
 155         block->state = IS_MBSTATE_CLEAN;
 156     }
 157     logf (LOG_DEBUG, "R: Block #%d contains %d records.", block->diskpos, block->num_records);
 158     return 0;
 159 }
 160
 161 /*
 162  * write dirty blocks to bfile.
 163  * Allocate blocks as necessary.
 164  */
 165 void is_p_sync(is_mtable *tab)
 166 {
 167     is_mblock *p;
 168     is_mbuf *b;
 169     int sum, v;
 170     isam_blocktype *type;
 171
 172     type = &tab->is->types[tab->pos_type];
 173     for (p = tab->data; p; p = p->next)
 174     {
 175         if (p->state < IS_MBSTATE_DIRTY)
 176             continue;
 177         /* make sure that blocks are allocated. */
 178         if (p->diskpos < 0)
 179             p->diskpos = is_freestore_alloc(tab->is, tab->pos_type);
 180         if (p->next)
 181         {
 182             if (p->next->diskpos < 0)
 183                 p->nextpos = p->next->diskpos = is_freestore_alloc(tab->is,
 184                     tab->pos_type);
 185             else
 186                 p->nextpos = p->next->diskpos;
 187         }
 188         else
 189             p->nextpos = 0;
 190         sum = 0;
 191         memcpy(type->dbuf, &p->num_records, sizeof(p->num_records));
 192         sum += sizeof(p->num_records);
 193         memcpy(type->dbuf + sum, &p->nextpos, sizeof(p->nextpos));
 194         sum += sizeof(p->nextpos);
 195         if (p == tab->data)  /* first block */
 196         {
 197             memcpy(type->dbuf + sum, &tab->num_records,
 198                 sizeof(tab->num_records));
 199             sum += sizeof(tab->num_records);
 200         }
 201         logf (LOG_DEBUG, "W: Block #%d contains %d records.", p->diskpos,
 202             p->num_records);
 203         assert(p->num_records > 0);
 204         for (b = p->data; b; b = b->next)
 205         {
 206             logf(LOG_DEBUG, "   buf: offset %d, keys %d, type %d, ref %d",
 207                 b->offset, b->num, b->type, b->refcount);
 208             if ((v = b->num * is_keysize(tab->is)) > 0)
 209                 memcpy(type->dbuf + sum, b->data + b->offset, v);
 210
 211             sum += v;
 212             assert(sum <= type->blocksize);
 213         }
 214         if (bf_write(type->bf, p->diskpos, 0, sum, type->dbuf) < 0)
 215         {
 216             logf (LOG_FATAL, "Failed to write block.");
 217             exit(1);
 218         }
 219     }
 220 }
 221
 222 /*
 223  * Free all disk blocks associated with table.
 224  */
 225 void is_p_unmap(is_mtable *tab)
 226 {
 227     is_mblock *p;
 228
 229     for (p = tab->data; p; p = p->next)
 230     {
 231         if (p->diskpos >= 0)
 232         {
 233             is_freestore_free(tab->is, tab->pos_type, p->diskpos);
 234             p->diskpos = -1;
 235         }
 236     }
 237 }
 238
 239 static is_mbuf *mbuf_takehead(is_mbuf **mb, int *num, int keysize)
 240 {
 241     is_mbuf *p = 0, **pp = &p, *inew;
 242     int toget = *num;
 243
 244     if (!toget)
 245         return 0;
 246     while (*mb && toget >= (*mb)->num)
 247     {
 248         toget -= (*mb)->num;
 249         *pp = *mb;
 250         *mb = (*mb)->next;
 251         (*pp)->next = 0;
 252         pp = &(*pp)->next;
 253     }
 254     if (toget > 0 && *mb)
 255     {
 256         inew = xmalloc_mbuf(IS_MBUF_TYPE_SMALL);
 257         inew->next = (*mb)->next;
 258         (*mb)->next = inew;
 259         inew->data = (*mb)->data;
 260         (*mb)->refcount++;
 261         inew->offset = (*mb)->offset + toget * keysize;
 262         inew->num = (*mb)->num - toget;
 263         (*mb)->num = toget;
 264         *pp = *mb;
 265         *mb = (*mb)->next;
 266         (*pp)->next = 0;
 267         toget = 0;
 268     }
 269     *num -= toget;
 270     return p;
 271 }
 272
 273 /*
 274  * Split up individual blocks which have grown too large.
 275  * is_p_align and is_p_remap are alternative functions which trade off
 276  * speed in updating versus optimum usage of disk blocks.
 277  */
 278 void is_p_align(is_mtable *tab)
 279 {
 280     is_mblock *mblock, *inew, *last = 0, *next;
 281     is_mbuf *mbufs, *mbp;
 282     int blocks, recsblock;
 283
 284     logf (LOG_DEBUG, "Realigning table.");
 285     for (mblock = tab->data; mblock; mblock = next)
 286     {
 287         next = mblock->next;
 288         if (mblock->state == IS_MBSTATE_DIRTY && mblock->num_records == 0)
 289         {
 290             if (last)
 291             {
 292                 last->next = mblock->next;
 293                 last->state = IS_MBSTATE_DIRTY;
 294                 next = mblock->next;
 295             }
 296             else
 297             {
 298                 next = tab->data->next;
 299                 if (next)
 300                 {
 301                     if (next->state < IS_MBSTATE_CLEAN)
 302                     {
 303                         if (is_p_read_full(tab, next) < 0)
 304                         {
 305                             logf(LOG_FATAL, "Error during re-alignment");
 306                             abort();
 307                         }
 308                         if (next->nextpos && !next->next)
 309                         {
 310                             next->next = xmalloc_mblock();
 311                             next->next->diskpos = next->nextpos;
 312                             next->next->state = IS_MBSTATE_UNREAD;
 313                             next->next->data = 0;
 314                         }
 315                     }
 316                     next->state = IS_MBSTATE_DIRTY; /* force re-process */
 317                     tab->data = next;
 318                 }
 319             }
 320             if (mblock->diskpos >= 0)
 321                 is_freestore_free(tab->is, tab->pos_type, mblock->diskpos);
 322             xrelease_mblock(mblock);
 323         }
 324         else if (mblock->state == IS_MBSTATE_DIRTY && mblock->num_records >
 325             (mblock == tab->data ?
 326             tab->is->types[tab->pos_type].max_keys_block0 :
 327             tab->is->types[tab->pos_type].max_keys_block))
 328         {
 329             blocks = tab->num_records /
 330             tab->is->types[tab->pos_type].nice_keys_block;
 331             if (tab->num_records %
 332                 tab->is->types[tab->pos_type].nice_keys_block)
 333                 blocks++;
 334             recsblock = tab->num_records / blocks;
 335             if (recsblock < 1)
 336                 recsblock = 1;
 337             mbufs = mblock->data;
 338             while ((mbp = mbuf_takehead(&mbufs, &recsblock,
 339                 is_keysize(tab->is))) && recsblock)
 340             {
 341                 if (mbufs)
 342                 {
 343                     inew = xmalloc_mblock();
 344                     inew->diskpos = -1;
 345                     inew->state = IS_MBSTATE_DIRTY;
 346                     inew->next = mblock->next;
 347                     mblock->next = inew;
 348                 }
 349                 mblock->data = mbp;
 350                 mblock->num_records = recsblock;
 351                 last = mblock;
 352                 mblock = mblock->next;
 353             }
 354             next = mblock;
 355         }
 356         else
 357             last = mblock;
 358     }
 359 }
 360
 361 /*
 362  * Reorganize data in blocks for minimum block usage and quick access.
 363  * Free surplus blocks.
 364  * is_p_align and is_p_remap are alternative functions which trade off
 365  * speed in updating versus optimum usage of disk blocks.
 366  */
 367 void is_p_remap(is_mtable *tab)
 368 {
 369     is_mbuf *mbufs, **bufpp, *mbp;
 370     is_mblock *blockp, **blockpp;
 371     int recsblock, blocks;
 372
 373     logf (LOG_DEBUG, "Remapping table.");
 374     /* collect all data */
 375     bufpp = &mbufs;
 376     for (blockp = tab->data; blockp; blockp = blockp->next)
 377     {
 378         if (blockp->state < IS_MBSTATE_CLEAN && is_m_read_full(tab, blockp) < 0)
 379         {
 380             logf (LOG_FATAL, "Read-full failed in remap.");
 381             exit(1);
 382         }
 383         *bufpp = blockp->data;
 384         while (*bufpp)
 385             bufpp = &(*bufpp)->next;
 386         blockp->data = 0;
 387     }
 388     blocks = tab->num_records / tab->is->types[tab->pos_type].nice_keys_block;
 389     if (tab->num_records % tab->is->types[tab->pos_type].nice_keys_block)
 390         blocks++;
 391     if (blocks == 0)
 392         blocks = 1;
 393     recsblock = tab->num_records / blocks + 1;
 394     if (recsblock > tab->is->types[tab->pos_type].nice_keys_block)
 395         recsblock--;
 396     blockpp = &tab->data;
 397     while ((mbp = mbuf_takehead(&mbufs, &recsblock, is_keysize(tab->is))) &&
 398         recsblock)
 399     {
 400         if (!*blockpp)
 401         {
 402             *blockpp = xmalloc_mblock();
 403             (*blockpp)->diskpos = -1;
 404         }
 405         (*blockpp)->data = mbp;
 406         (*blockpp)->num_records = recsblock;
 407         (*blockpp)->state = IS_MBSTATE_DIRTY;
 408         blockpp = &(*blockpp)->next;
 409     }
 410     if (mbp)
 411         xfree_mbufs(mbp);
 412     if (*blockpp)
 413     {
 414         for (blockp = *blockpp; blockp; blockp = blockp->next)
 415             if (blockp->diskpos >= 0)
 416                 is_freestore_free(tab->is, tab->pos_type, blockp->diskpos);
 417         xfree_mblocks(*blockpp);
 418         *blockpp = 0;
 419     }
 420 }