bfile/cfile.c

   1 /* $Id: cfile.c,v 1.39 2006-11-14 08:12:06 adam Exp $
   2    Copyright (C) 1995-2006
   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 this program; if not, write to the Free Software
  19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  20
  21 */
  22
  23 #include <assert.h>
  24 #include <stdlib.h>
  25 #include <string.h>
  26
  27 #include <idzebra/util.h>
  28 #include <yaz/yaz-util.h>
  29 #include "mfile.h"
  30 #include "cfile.h"
  31
  32 static int write_head(CFile cf)
  33 {
  34     int left = cf->head.hash_size * sizeof(zint);
  35     int bno = 1;
  36     int r = 0;
  37     const char *tab = (char*) cf->array;
  38
  39     if (!tab)
  40         return 0;
  41     while (left >= (int) HASH_BSIZE)
  42     {
  43         r = mf_write(cf->hash_mf, bno++, 0, 0, tab);
  44         if (r)
  45             return r;
  46         tab += HASH_BSIZE;
  47         left -= HASH_BSIZE;
  48     }
  49     if (left > 0)
  50         r = mf_write(cf->hash_mf, bno, 0, left, tab);
  51     return r;
  52 }
  53
  54 static int read_head(CFile cf)
  55 {
  56     int left = cf->head.hash_size * sizeof(zint);
  57     int bno = 1;
  58     char *tab = (char*) cf->array;
  59
  60     if (!tab)
  61         return 0;
  62     while (left >= (int) HASH_BSIZE)
  63     {
  64         if (mf_read(cf->hash_mf, bno++, 0, 0, tab) == -1)
  65             return -1;
  66         tab += HASH_BSIZE;
  67         left -= HASH_BSIZE;
  68     }
  69     if (left > 0)
  70     {
  71         if (mf_read(cf->hash_mf, bno, 0, left, tab) == -1)
  72             return -1;
  73     }
  74     return 1;
  75 }
  76
  77
  78 CFile cf_open(MFile mf, MFile_area area, const char *fname,
  79               int block_size, int wflag, int *firstp)
  80 {
  81     char path[1024];
  82     int i, ret;
  83     CFile cf = (CFile) xmalloc(sizeof(*cf));
  84     int hash_bytes;
  85
  86     /* avoid valgrind warnings, but set to something nasty */
  87     memset(cf, 'Z', sizeof(*cf));
  88
  89     yaz_log(YLOG_DEBUG, "cf: open %s %s", cf->rmf->name,
  90             wflag ? "rdwr" : "rd");
  91
  92     cf->block_mf = 0;
  93     cf->hash_mf = 0;
  94     cf->rmf = mf;
  95
  96     assert(firstp);
  97
  98     cf->bucket_lru_front = cf->bucket_lru_back = NULL;
  99     cf->bucket_in_memory = 0;
 100     cf->max_bucket_in_memory = 100;
 101     cf->dirty = 0;
 102     cf->iobuf = (char *) xmalloc(block_size);
 103     memset(cf->iobuf, 0, block_size);
 104     cf->no_hits = 0;
 105     cf->no_miss = 0;
 106     cf->parray = 0;
 107     cf->array = 0;
 108     cf->block_mf = 0;
 109     cf->hash_mf = 0;
 110
 111     zebra_mutex_init(&cf->mutex);
 112
 113     sprintf(path, "%s-b", fname);
 114     if (!(cf->block_mf = mf_open(area, path, block_size, wflag)))
 115     {
 116         cf_close(cf);
 117         return 0;
 118     }
 119     sprintf(path, "%s-i", fname);
 120     if (!(cf->hash_mf = mf_open(area, path, HASH_BSIZE, wflag)))
 121     {
 122         cf_close(cf);
 123         return 0;
 124     }
 125     ret = mf_read(cf->hash_mf, 0, 0, sizeof(cf->head), &cf->head);
 126
 127     if (ret == -1)
 128     {
 129         cf_close(cf);
 130         return 0;
 131     }
 132     if (ret == 0 || !cf->head.state)
 133     {
 134         *firstp = 1;
 135         cf->head.state = 1;
 136         cf->head.block_size = block_size;
 137         cf->head.hash_size = 199;
 138         hash_bytes = cf->head.hash_size * sizeof(zint);
 139         cf->head.flat_bucket = cf->head.next_bucket = cf->head.first_bucket =
 140             (hash_bytes+sizeof(cf->head))/HASH_BSIZE + 2;
 141         cf->head.next_block = 1;
 142         cf->array = (zint *) xmalloc(hash_bytes);
 143         for (i = 0; i<cf->head.hash_size; i++)
 144             cf->array[i] = 0;
 145         if (wflag)
 146         {
 147             if (mf_write(cf->hash_mf, 0, 0, sizeof(cf->head), &cf->head))
 148             {
 149                 cf_close(cf);
 150                 return 0;
 151             }
 152             if (write_head(cf))
 153             {
 154                 cf_close(cf);
 155                 return 0;
 156             }
 157         }
 158     }
 159     else
 160     {
 161         *firstp = 0;
 162         assert(cf->head.block_size == block_size);
 163         assert(cf->head.hash_size > 2);
 164         hash_bytes = cf->head.hash_size * sizeof(zint);
 165         assert(cf->head.next_bucket > 0);
 166         assert(cf->head.next_block > 0);
 167         if (cf->head.state == 1)
 168             cf->array = (zint *) xmalloc(hash_bytes);
 169         else
 170             cf->array = NULL;
 171         if (read_head(cf) == -1)
 172         {
 173             cf_close(cf);
 174             return 0;
 175         }
 176     }
 177     if (cf->head.state == 1)
 178     {
 179         cf->parray = (struct CFile_hash_bucket **)
 180             xmalloc(cf->head.hash_size * sizeof(*cf->parray));
 181         for (i = 0; i<cf->head.hash_size; i++)
 182             cf->parray[i] = NULL;
 183     }
 184     return cf;
 185 }
 186
 187 static int cf_hash(CFile cf, zint no)
 188 {
 189     return (int) (((no >> 3) % cf->head.hash_size));
 190 }
 191
 192 static void release_bucket(CFile cf, struct CFile_hash_bucket *p)
 193 {
 194     if (p->lru_prev)
 195         p->lru_prev->lru_next = p->lru_next;
 196     else
 197         cf->bucket_lru_back = p->lru_next;
 198     if (p->lru_next)
 199         p->lru_next->lru_prev = p->lru_prev;
 200     else
 201         cf->bucket_lru_front = p->lru_prev;
 202
 203     *p->h_prev = p->h_next;
 204     if (p->h_next)
 205         p->h_next->h_prev = p->h_prev;
 206
 207     --(cf->bucket_in_memory);
 208     xfree(p);
 209 }
 210
 211 static int flush_bucket(CFile cf, int no_to_flush)
 212 {
 213     int i;
 214     int ret = 0;
 215     struct CFile_hash_bucket *p;
 216
 217     for (i = 0; i != no_to_flush; i++)
 218     {
 219         p = cf->bucket_lru_back;
 220         if (!p)
 221             break;
 222         if (p->dirty)
 223         {
 224             if (ret == 0)
 225             {
 226                 if (mf_write(cf->hash_mf, p->ph.this_bucket, 0, 0, &p->ph))
 227                     ret = -1;
 228             }
 229             cf->dirty = 1;
 230         }
 231         release_bucket(cf, p);
 232     }
 233     return ret;
 234 }
 235
 236 static struct CFile_hash_bucket *alloc_bucket(CFile cf, zint block_no, int hno)
 237 {
 238     struct CFile_hash_bucket *p, **pp;
 239
 240     if (cf->bucket_in_memory == cf->max_bucket_in_memory)
 241     {
 242         if (flush_bucket(cf, 1))
 243             return 0;
 244     }
 245     assert(cf->bucket_in_memory < cf->max_bucket_in_memory);
 246     ++(cf->bucket_in_memory);
 247     p = (struct CFile_hash_bucket *) xmalloc(sizeof(*p));
 248
 249     p->lru_next = NULL;
 250     p->lru_prev = cf->bucket_lru_front;
 251     if (cf->bucket_lru_front)
 252         cf->bucket_lru_front->lru_next = p;
 253     else
 254         cf->bucket_lru_back = p;
 255     cf->bucket_lru_front = p;
 256
 257     pp = cf->parray + hno;
 258     p->h_next = *pp;
 259     p->h_prev = pp;
 260     if (*pp)
 261         (*pp)->h_prev = &p->h_next;
 262     *pp = p;
 263     return p;
 264 }
 265
 266 static struct CFile_hash_bucket *get_bucket(CFile cf, zint block_no, int hno)
 267 {
 268     struct CFile_hash_bucket *p;
 269
 270     p = alloc_bucket(cf, block_no, hno);
 271     if (!p)
 272         return 0;
 273     p->dirty = 0;
 274     if (mf_read(cf->hash_mf, block_no, 0, 0, &p->ph) != 1)
 275     {
 276         yaz_log(YLOG_FATAL, "read get_bucket");
 277         release_bucket(cf, p);
 278         return 0;
 279     }
 280     assert(p->ph.this_bucket == block_no);
 281     return p;
 282 }
 283
 284 static struct CFile_hash_bucket *new_bucket(CFile cf, zint *block_nop, int hno)
 285 {
 286     struct CFile_hash_bucket *p;
 287     int i;
 288     zint block_no;
 289
 290     block_no = *block_nop = cf->head.next_bucket++;
 291     p = alloc_bucket(cf, block_no, hno);
 292     if (!p)
 293         return 0;
 294     p->dirty = 1;
 295
 296     for (i = 0; i<HASH_BUCKET; i++)
 297     {
 298         p->ph.vno[i] = 0;
 299         p->ph.no[i] = 0;
 300     }
 301     p->ph.next_bucket = 0;
 302     p->ph.this_bucket = block_no;
 303     return p;
 304 }
 305
 306 static int cf_lookup_flat(CFile cf, zint no, zint *vno)
 307 {
 308     zint hno = (no*sizeof(zint))/HASH_BSIZE;
 309     int off = (int) ((no*sizeof(zint)) - hno*HASH_BSIZE);
 310
 311     *vno = 0;
 312     if (mf_read(cf->hash_mf, hno+cf->head.next_bucket, off, sizeof(zint), vno)
 313         == -1)
 314         return -1;
 315     if (*vno)
 316         return 1;
 317     return 0;
 318 }
 319
 320 static int cf_lookup_hash(CFile cf, zint no, zint *vno)
 321 {
 322     int hno = cf_hash(cf, no);
 323     struct CFile_hash_bucket *hb;
 324     zint block_no;
 325     int i;
 326
 327     for (hb = cf->parray[hno]; hb; hb = hb->h_next)
 328     {
 329         for (i = 0; i<HASH_BUCKET && hb->ph.vno[i]; i++)
 330             if (hb->ph.no[i] == no)
 331             {
 332                 (cf->no_hits)++;
 333                 *vno = hb->ph.vno[i];
 334                 return 1;
 335             }
 336     }
 337     for (block_no = cf->array[hno]; block_no; block_no = hb->ph.next_bucket)
 338     {
 339         for (hb = cf->parray[hno]; hb; hb = hb->h_next)
 340         {
 341             if (hb->ph.this_bucket == block_no)
 342                 break;
 343         }
 344         if (hb)
 345             continue;
 346 #if 0
 347         /* extra check ... */
 348         for (hb = cf->bucket_lru_back; hb; hb = hb->lru_next)
 349         {
 350             if (hb->ph.this_bucket == block_no)
 351             {
 352                 yaz_log(YLOG_FATAL, "Found hash bucket on other chain(1)");
 353                 abort();
 354             }
 355             for (i = 0; i<HASH_BUCKET && hb->ph.vno[i]; i++)
 356                 if (hb->ph.no[i] == no)
 357                 {
 358                     yaz_log(YLOG_FATAL, "Found hash bucket on other chain (2)");
 359                     abort();
 360                 }
 361         }
 362 #endif
 363         (cf->no_miss)++;
 364         hb = get_bucket(cf, block_no, hno);
 365         if (!hb)
 366             return -1;
 367         for (i = 0; i<HASH_BUCKET && hb->ph.vno[i]; i++)
 368             if (hb->ph.no[i] == no)
 369             {
 370                 *vno = hb->ph.vno[i];
 371                 return 1;
 372             }
 373     }
 374     return 0;
 375 }
 376
 377 static int cf_write_flat(CFile cf, zint no, zint vno)
 378 {
 379     zint hno = (no*sizeof(zint))/HASH_BSIZE;
 380     int off = (int) ((no*sizeof(zint)) - hno*HASH_BSIZE);
 381
 382     hno += cf->head.next_bucket;
 383     if (hno >= cf->head.flat_bucket)
 384         cf->head.flat_bucket = hno+1;
 385     cf->dirty = 1;
 386     return mf_write(cf->hash_mf, hno, off, sizeof(zint), &vno);
 387 }
 388
 389 static int cf_moveto_flat(CFile cf)
 390 {
 391     struct CFile_hash_bucket *p;
 392     int j;
 393     zint i;
 394
 395     yaz_log(YLOG_DEBUG, "cf: Moving to flat shadow: %s", cf->rmf->name);
 396     yaz_log(YLOG_DEBUG, "cf: hits=%d miss=%d bucket_in_memory=" ZINT_FORMAT " total="
 397           ZINT_FORMAT,
 398         cf->no_hits, cf->no_miss, cf->bucket_in_memory,
 399         cf->head.next_bucket - cf->head.first_bucket);
 400     assert(cf->head.state == 1);
 401     if (flush_bucket(cf, -1))
 402         return -1;
 403     assert(cf->bucket_in_memory == 0);
 404     p = (struct CFile_hash_bucket *) xmalloc(sizeof(*p));
 405     for (i = cf->head.first_bucket; i < cf->head.next_bucket; i++)
 406     {
 407         if (mf_read(cf->hash_mf, i, 0, 0, &p->ph) != 1)
 408         {
 409             yaz_log(YLOG_FATAL|YLOG_ERRNO, "read bucket moveto flat");
 410             xfree(p);
 411             return -1;
 412         }
 413         for (j = 0; j < HASH_BUCKET && p->ph.vno[j]; j++)
 414         {
 415             if (cf_write_flat(cf, p->ph.no[j], p->ph.vno[j]))
 416             {
 417                 xfree(p);
 418                 return -1;
 419             }
 420         }
 421     }
 422     xfree(p);
 423     xfree(cf->array);
 424     cf->array = NULL;
 425     xfree(cf->parray);
 426     cf->parray = NULL;
 427     cf->head.state = 2;
 428     cf->dirty = 1;
 429     return 0;
 430 }
 431
 432 static int cf_lookup(CFile cf, zint no, zint *vno)
 433 {
 434     if (cf->head.state > 1)
 435         return cf_lookup_flat(cf, no, vno);
 436     return cf_lookup_hash(cf, no, vno);
 437 }
 438
 439 static zint cf_new_flat(CFile cf, zint no)
 440 {
 441     zint vno = (cf->head.next_block)++;
 442
 443     cf_write_flat(cf, no, vno);
 444     return vno;
 445 }
 446
 447 static zint cf_new_hash(CFile cf, zint no)
 448 {
 449     int hno = cf_hash(cf, no);
 450     struct CFile_hash_bucket *hbprev = NULL, *hb = cf->parray[hno];
 451     zint *bucketpp = &cf->array[hno];
 452     int i;
 453     zint vno = (cf->head.next_block)++;
 454
 455     for (hb = cf->parray[hno]; hb; hb = hb->h_next)
 456         if (!hb->ph.vno[HASH_BUCKET-1])
 457             for (i = 0; i<HASH_BUCKET; i++)
 458                 if (!hb->ph.vno[i])
 459                 {
 460                     (cf->no_hits)++;
 461                     hb->ph.no[i] = no;
 462                     hb->ph.vno[i] = vno;
 463                     hb->dirty = 1;
 464                     return vno;
 465                 }
 466
 467     while (*bucketpp)
 468     {
 469         for (hb = cf->parray[hno]; hb; hb = hb->h_next)
 470             if (hb->ph.this_bucket == *bucketpp)
 471             {
 472                 bucketpp = &hb->ph.next_bucket;
 473                 hbprev = hb;
 474                 break;
 475             }
 476         if (hb)
 477             continue;
 478
 479 #if 0
 480         /* extra check ... */
 481         for (hb = cf->bucket_lru_back; hb; hb = hb->lru_next)
 482         {
 483             if (hb->ph.this_bucket == *bucketpp)
 484             {
 485                 yaz_log(YLOG_FATAL, "Found hash bucket on other chain");
 486                 abort();
 487             }
 488         }
 489 #endif
 490         (cf->no_miss)++;
 491         hb = get_bucket(cf, *bucketpp, hno);
 492         if (!hb)
 493             return 0;
 494         for (i = 0; i<HASH_BUCKET; i++)
 495             if (!hb->ph.vno[i])
 496             {
 497                 hb->ph.no[i] = no;
 498                 hb->ph.vno[i] = vno;
 499                 hb->dirty = 1;
 500                 return vno;
 501             }
 502         bucketpp = &hb->ph.next_bucket;
 503         hbprev = hb;
 504     }
 505     if (hbprev)
 506         hbprev->dirty = 1;
 507     hb = new_bucket(cf, bucketpp, hno);
 508     if (!hb)
 509         return 0;
 510
 511     hb->ph.no[0] = no;
 512     hb->ph.vno[0] = vno;
 513     return vno;
 514 }
 515
 516 zint cf_new(CFile cf, zint no)
 517 {
 518     if (cf->head.state > 1)
 519         return cf_new_flat(cf, no);
 520     if (cf->no_miss*2 > cf->no_hits)
 521     {
 522         if (cf_moveto_flat(cf))
 523             return -1;
 524         assert(cf->head.state > 1);
 525         return cf_new_flat(cf, no);
 526     }
 527     return cf_new_hash(cf, no);
 528 }
 529
 530
 531 /** \brief reads block from commit area
 532     \param cf commit file
 533     \param no block number
 534     \param offset offset in block
 535     \param nbytes number of bytes to read
 536     \param buf buffer for content (if read was succesful)
 537     \retval 0 block could not be fully read
 538     \retval 1 block could be read
 539     \retval -1 error
 540 */
 541 int cf_read(CFile cf, zint no, int offset, int nbytes, void *buf)
 542 {
 543     zint block;
 544     int ret;
 545
 546     assert(cf);
 547     zebra_mutex_lock(&cf->mutex);
 548     ret = cf_lookup(cf, no, &block);
 549     zebra_mutex_unlock(&cf->mutex);
 550     if (ret == -1)
 551     {
 552         /* error */
 553         yaz_log(YLOG_FATAL, "cf_lookup failed");
 554         return -1;
 555     }
 556     else if (ret == 0)
 557     {
 558         /* block could not be read */
 559         return ret;
 560     }
 561     else if (mf_read(cf->block_mf, block, offset, nbytes, buf) != 1)
 562     {
 563         yaz_log(YLOG_FATAL|YLOG_ERRNO, "mf_read no=" ZINT_FORMAT " block=" ZINT_FORMAT, no, block);
 564         return -1;
 565     }
 566     return 1;
 567 }
 568
 569 /** \brief writes block to commit area
 570     \param cf commit file
 571     \param no block number
 572     \param offset offset in block
 573     \param nbytes number of bytes to be written
 574     \param buf buffer to be written
 575     \retval 0 block written
 576     \retval -1 error
 577 */
 578 int cf_write(CFile cf, zint no, int offset, int nbytes, const void *buf)
 579 {
 580     zint block;
 581     int ret;
 582
 583     assert(cf);
 584     zebra_mutex_lock(&cf->mutex);
 585
 586     ret = cf_lookup(cf, no, &block);
 587
 588     if (ret == -1)
 589     {
 590         zebra_mutex_unlock(&cf->mutex);
 591         return ret;
 592     }
 593     if (ret == 0)
 594     {
 595         block = cf_new(cf, no);
 596         if (!block)
 597         {
 598             zebra_mutex_unlock(&cf->mutex);
 599             return -1;
 600         }
 601         if (offset || nbytes)
 602         {
 603             if (mf_read(cf->rmf, no, 0, 0, cf->iobuf) == -1)
 604                 return -1;
 605             memcpy(cf->iobuf + offset, buf, nbytes);
 606             buf = cf->iobuf;
 607             offset = 0;
 608             nbytes = 0;
 609         }
 610     }
 611     zebra_mutex_unlock(&cf->mutex);
 612     return mf_write(cf->block_mf, block, offset, nbytes, buf);
 613 }
 614
 615 int cf_close(CFile cf)
 616 {
 617     int ret = 0;
 618     yaz_log(YLOG_DEBUG, "cf: close hits=%d miss=%d bucket_in_memory=" ZINT_FORMAT
 619           " total=" ZINT_FORMAT,
 620           cf->no_hits, cf->no_miss, cf->bucket_in_memory,
 621           cf->head.next_bucket - cf->head.first_bucket);
 622     if (flush_bucket(cf, -1))
 623         ret = -1;
 624     if (cf->hash_mf)
 625     {
 626         if (cf->dirty)
 627         {
 628             if (mf_write(cf->hash_mf, 0, 0, sizeof(cf->head), &cf->head))
 629                 ret = -1;
 630             if (write_head(cf))
 631                 ret = -1;
 632         }
 633         mf_close(cf->hash_mf);
 634     }
 635     if (cf->block_mf)
 636         mf_close(cf->block_mf);
 637     xfree(cf->array);
 638     xfree(cf->parray);
 639     xfree(cf->iobuf);
 640     zebra_mutex_destroy(&cf->mutex);
 641     xfree(cf);
 642     return ret;
 643 }
 644
 645 /*
 646  * Local variables:
 647  * c-basic-offset: 4
 648  * indent-tabs-mode: nil
 649  * End:
 650  * vim: shiftwidth=4 tabstop=8 expandtab
 651  */
 652