isam/physical.c

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