bfile/cfile.c

   1 /* This file is part of the Zebra server.
   2    Copyright (C) 1994-2011 Index Data
   3
   4 Zebra is free software; you can redistribute it and/or modify it under
   5 the terms of the GNU General Public License as published by the Free
   6 Software Foundation; either version 2, or (at your option) any later
   7 version.
   8
   9 Zebra is distributed in the hope that it will be useful, but WITHOUT ANY
  10 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12 for more details.
  13
  14 You should have received a copy of the GNU General Public License
  15 along with this program; if not, write to the Free Software
  16 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  17
  18 */
  19
  20 #if HAVE_CONFIG_H
  21 #include <config.h>
  22 #endif
  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 /** \brief set to 1 if extra commit/shadow check is to be performed */
  33 #define EXTRA_CHECK 0
  34
  35 static int write_head(CFile cf)
  36 {
  37     int left = cf->head.hash_size * sizeof(zint);
  38     int bno = 1;
  39     int r = 0;
  40     const char *tab = (char*) cf->array;
  41
  42     if (!tab)
  43         return 0;
  44     while (left >= (int) HASH_BSIZE)
  45     {
  46         r = mf_write(cf->hash_mf, bno++, 0, 0, tab);
  47         if (r)
  48             return r;
  49         tab += HASH_BSIZE;
  50         left -= HASH_BSIZE;
  51     }
  52     if (left > 0)
  53         r = mf_write(cf->hash_mf, bno, 0, left, tab);
  54     return r;
  55 }
  56
  57 static int read_head(CFile cf)
  58 {
  59     int left = cf->head.hash_size * sizeof(zint);
  60     int bno = 1;
  61     char *tab = (char*) cf->array;
  62
  63     if (!tab)
  64         return 0;
  65     while (left >= (int) HASH_BSIZE)
  66     {
  67         if (mf_read(cf->hash_mf, bno++, 0, 0, tab) == -1)
  68             return -1;
  69         tab += HASH_BSIZE;
  70         left -= HASH_BSIZE;
  71     }
  72     if (left > 0)
  73     {
  74         if (mf_read(cf->hash_mf, bno, 0, left, tab) == -1)
  75             return -1;
  76     }
  77     return 1;
  78 }
  79
  80
  81 CFile cf_open(MFile mf, MFile_area area, const char *fname,
  82               int block_size, int wflag, int *firstp)
  83 {
  84     char path[1024];
  85     int i, ret;
  86     CFile cf = (CFile) xmalloc(sizeof(*cf));
  87     int hash_bytes;
  88
  89     /* avoid valgrind warnings, but set to something nasty */
  90     memset(cf, 'Z', sizeof(*cf));
  91
  92     yaz_log(YLOG_DEBUG, "cf: open %s %s", fname, wflag ? "rdwr" : "rd");
  93
  94     cf->block_mf = 0;
  95     cf->hash_mf = 0;
  96     cf->rmf = mf;
  97
  98     assert(firstp);
  99
 100     cf->bucket_lru_front = cf->bucket_lru_back = NULL;
 101     cf->bucket_in_memory = 0;
 102     cf->max_bucket_in_memory = 100;
 103     cf->dirty = 0;
 104     cf->iobuf = (char *) xmalloc(block_size);
 105     memset(cf->iobuf, 0, block_size);
 106     cf->no_hits = 0;
 107     cf->no_miss = 0;
 108     cf->parray = 0;
 109     cf->array = 0;
 110     cf->block_mf = 0;
 111     cf->hash_mf = 0;
 112
 113     zebra_mutex_init(&cf->mutex);
 114
 115     sprintf(path, "%s-b", fname);
 116     if (!(cf->block_mf = mf_open(area, path, block_size, wflag)))
 117     {
 118         cf_close(cf);
 119         return 0;
 120     }
 121     sprintf(path, "%s-i", fname);
 122     if (!(cf->hash_mf = mf_open(area, path, HASH_BSIZE, wflag)))
 123     {
 124         cf_close(cf);
 125         return 0;
 126     }
 127     ret = mf_read(cf->hash_mf, 0, 0, sizeof(cf->head), &cf->head);
 128
 129     if (ret == -1)
 130     {
 131         cf_close(cf);
 132         return 0;
 133     }
 134     if (ret == 0 || !cf->head.state)
 135     {
 136         *firstp = 1;
 137         cf->head.state = CFILE_STATE_HASH;
 138         cf->head.block_size = block_size;
 139         cf->head.hash_size = 199;
 140         hash_bytes = cf->head.hash_size * sizeof(zint);
 141         cf->head.flat_bucket = cf->head.next_bucket = cf->head.first_bucket =
 142             (hash_bytes+sizeof(cf->head))/HASH_BSIZE + 2;
 143         cf->head.next_block = 1;
 144         cf->array = (zint *) xmalloc(hash_bytes);
 145         for (i = 0; i<cf->head.hash_size; i++)
 146             cf->array[i] = 0;
 147         if (wflag)
 148         {
 149             if (mf_write(cf->hash_mf, 0, 0, sizeof(cf->head), &cf->head))
 150             {
 151                 cf_close(cf);
 152                 return 0;
 153             }
 154             if (write_head(cf))
 155             {
 156                 cf_close(cf);
 157                 return 0;
 158             }
 159         }
 160     }
 161     else
 162     {
 163         *firstp = 0;
 164         assert(cf->head.block_size == block_size);
 165         assert(cf->head.hash_size > 2);
 166         hash_bytes = cf->head.hash_size * sizeof(zint);
 167         assert(cf->head.next_bucket > 0);
 168         assert(cf->head.next_block > 0);
 169         if (cf->head.state == CFILE_STATE_HASH)
 170             cf->array = (zint *) xmalloc(hash_bytes);
 171         else
 172             cf->array = NULL;
 173         if (read_head(cf) == -1)
 174         {
 175             cf_close(cf);
 176             return 0;
 177         }
 178     }
 179     if (cf->head.state == CFILE_STATE_HASH)
 180     {
 181         cf->parray = (struct CFile_hash_bucket **)
 182             xmalloc(cf->head.hash_size * sizeof(*cf->parray));
 183         for (i = 0; i<cf->head.hash_size; i++)
 184             cf->parray[i] = NULL;
 185     }
 186     return cf;
 187 }
 188
 189 static int cf_hash(CFile cf, zint no)
 190 {
 191     return (int) (((no >> 3) % cf->head.hash_size));
 192 }
 193
 194 static void release_bucket(CFile cf, struct CFile_hash_bucket *p)
 195 {
 196     if (p->lru_prev)
 197         p->lru_prev->lru_next = p->lru_next;
 198     else
 199         cf->bucket_lru_back = p->lru_next;
 200     if (p->lru_next)
 201         p->lru_next->lru_prev = p->lru_prev;
 202     else
 203         cf->bucket_lru_front = p->lru_prev;
 204
 205     *p->h_prev = p->h_next;
 206     if (p->h_next)
 207         p->h_next->h_prev = p->h_prev;
 208
 209     --(cf->bucket_in_memory);
 210     xfree(p);
 211 }
 212
 213 static int flush_bucket(CFile cf, int no_to_flush)
 214 {
 215     int i;
 216     int ret = 0;
 217     struct CFile_hash_bucket *p;
 218
 219     for (i = 0; i != no_to_flush; i++)
 220     {
 221         p = cf->bucket_lru_back;
 222         if (!p)
 223             break;
 224         if (p->dirty)
 225         {
 226             if (ret == 0)
 227             {
 228                 if (mf_write(cf->hash_mf, p->ph.this_bucket, 0, 0, &p->ph))
 229                     ret = -1;
 230             }
 231             cf->dirty = 1;
 232         }
 233         release_bucket(cf, p);
 234     }
 235     return ret;
 236 }
 237
 238 static struct CFile_hash_bucket *alloc_bucket(CFile cf, zint block_no, int hno)
 239 {
 240     struct CFile_hash_bucket *p, **pp;
 241
 242     if (cf->bucket_in_memory == cf->max_bucket_in_memory)
 243     {
 244         if (flush_bucket(cf, 1))
 245             return 0;
 246     }
 247     assert(cf->bucket_in_memory < cf->max_bucket_in_memory);
 248     ++(cf->bucket_in_memory);
 249     p = (struct CFile_hash_bucket *) xmalloc(sizeof(*p));
 250
 251     p->lru_next = NULL;
 252     p->lru_prev = cf->bucket_lru_front;
 253     if (cf->bucket_lru_front)
 254         cf->bucket_lru_front->lru_next = p;
 255     else
 256         cf->bucket_lru_back = p;
 257     cf->bucket_lru_front = p;
 258
 259     pp = cf->parray + hno;
 260     p->h_next = *pp;
 261     p->h_prev = pp;
 262     if (*pp)
 263         (*pp)->h_prev = &p->h_next;
 264     *pp = p;
 265     return p;
 266 }
 267
 268 static struct CFile_hash_bucket *get_bucket(CFile cf, zint block_no, int hno)
 269 {
 270     struct CFile_hash_bucket *p;
 271
 272     p = alloc_bucket(cf, block_no, hno);
 273     if (!p)
 274         return 0;
 275     p->dirty = 0;
 276     if (mf_read(cf->hash_mf, block_no, 0, 0, &p->ph) != 1)
 277     {
 278         yaz_log(YLOG_FATAL, "read get_bucket");
 279         release_bucket(cf, p);
 280         return 0;
 281     }
 282     assert(p->ph.this_bucket == block_no);
 283     return p;
 284 }
 285
 286 static struct CFile_hash_bucket *new_bucket(CFile cf, zint *block_nop, int hno)
 287 {
 288     struct CFile_hash_bucket *p;
 289     int i;
 290     zint block_no;
 291
 292     block_no = *block_nop = cf->head.next_bucket++;
 293     p = alloc_bucket(cf, block_no, hno);
 294     if (!p)
 295         return 0;
 296     p->dirty = 1;
 297
 298     for (i = 0; i<HASH_BUCKET; i++)
 299     {
 300         p->ph.vno[i] = 0;
 301         p->ph.no[i] = 0;
 302     }
 303     p->ph.next_bucket = 0;
 304     p->ph.this_bucket = block_no;
 305     return p;
 306 }
 307
 308 static int cf_lookup_flat(CFile cf, zint no, zint *vno)
 309 {
 310     zint hno = (no*sizeof(zint))/HASH_BSIZE;
 311     int off = (int) ((no*sizeof(zint)) - hno*HASH_BSIZE);
 312
 313     *vno = 0;
 314     if (mf_read(cf->hash_mf, hno+cf->head.next_bucket, off, sizeof(zint), vno)
 315         == -1)
 316         return -1;
 317     if (*vno)
 318         return 1;
 319     return 0;
 320 }
 321
 322 static int cf_lookup_hash(CFile cf, zint no, zint *vno)
 323 {
 324     int hno = cf_hash(cf, no);
 325     struct CFile_hash_bucket *hb;
 326     zint block_no;
 327     int i;
 328
 329     for (hb = cf->parray[hno]; hb; hb = hb->h_next)
 330     {
 331         for (i = 0; i<HASH_BUCKET && hb->ph.vno[i]; i++)
 332             if (hb->ph.no[i] == no)
 333             {
 334                 (cf->no_hits)++;
 335                 *vno = hb->ph.vno[i];
 336                 return 1;
 337             }
 338     }
 339     for (block_no = cf->array[hno]; block_no; block_no = hb->ph.next_bucket)
 340     {
 341         for (hb = cf->parray[hno]; hb; hb = hb->h_next)
 342         {
 343             if (hb->ph.this_bucket == block_no)
 344                 break;
 345         }
 346         if (hb)
 347             continue;
 348 #if EXTRA_CHECK
 349         for (hb = cf->bucket_lru_back; hb; hb = hb->lru_next)
 350         {
 351             if (hb->ph.this_bucket == block_no)
 352             {
 353                 yaz_log(YLOG_FATAL, "Found hash bucket on other chain(1)");
 354                 return -1;
 355             }
 356             for (i = 0; i<HASH_BUCKET && hb->ph.vno[i]; i++)
 357                 if (hb->ph.no[i] == no)
 358                 {
 359                     yaz_log(YLOG_FATAL, "Found hash bucket on other chain (2)");
 360                     return -1;
 361                 }
 362         }
 363 #endif
 364         (cf->no_miss)++;
 365         hb = get_bucket(cf, block_no, hno);
 366         if (!hb)
 367             return -1;
 368         for (i = 0; i<HASH_BUCKET && hb->ph.vno[i]; i++)
 369             if (hb->ph.no[i] == no)
 370             {
 371                 *vno = hb->ph.vno[i];
 372                 return 1;
 373             }
 374     }
 375     return 0;
 376 }
 377
 378 static int cf_write_flat(CFile cf, zint no, zint vno)
 379 {
 380     zint hno = (no*sizeof(zint))/HASH_BSIZE;
 381     int off = (int) ((no*sizeof(zint)) - hno*HASH_BSIZE);
 382
 383     hno += cf->head.next_bucket;
 384     if (hno >= cf->head.flat_bucket)
 385         cf->head.flat_bucket = hno+1;
 386     cf->dirty = 1;
 387     return mf_write(cf->hash_mf, hno, off, sizeof(zint), &vno);
 388 }
 389
 390 static int cf_moveto_flat(CFile cf)
 391 {
 392     struct CFile_hash_bucket *p;
 393     int j;
 394     zint i;
 395
 396     yaz_log(YLOG_DEBUG, "cf: Moving to flat shadow: %s", cf->rmf->name);
 397     yaz_log(YLOG_DEBUG, "cf: hits=%d miss=%d bucket_in_memory=" ZINT_FORMAT " total="
 398           ZINT_FORMAT,
 399         cf->no_hits, cf->no_miss, cf->bucket_in_memory,
 400         cf->head.next_bucket - cf->head.first_bucket);
 401     assert(cf->head.state == CFILE_STATE_HASH);
 402     if (flush_bucket(cf, -1))
 403         return -1;
 404     assert(cf->bucket_in_memory == 0);
 405     p = (struct CFile_hash_bucket *) xmalloc(sizeof(*p));
 406     for (i = cf->head.first_bucket; i < cf->head.next_bucket; i++)
 407     {
 408         if (mf_read(cf->hash_mf, i, 0, 0, &p->ph) != 1)
 409         {
 410             yaz_log(YLOG_FATAL|YLOG_ERRNO, "read bucket moveto flat");
 411             xfree(p);
 412             return -1;
 413         }
 414         for (j = 0; j < HASH_BUCKET && p->ph.vno[j]; j++)
 415         {
 416             if (cf_write_flat(cf, p->ph.no[j], p->ph.vno[j]))
 417             {
 418                 xfree(p);
 419                 return -1;
 420             }
 421         }
 422     }
 423     xfree(p);
 424     xfree(cf->array);
 425     cf->array = NULL;
 426     xfree(cf->parray);
 427     cf->parray = NULL;
 428     cf->head.state = CFILE_STATE_FLAT;
 429     cf->dirty = 1;
 430     return 0;
 431 }
 432
 433 static int cf_lookup(CFile cf, zint no, zint *vno)
 434 {
 435     if (cf->head.state > 1)
 436         return cf_lookup_flat(cf, no, vno);
 437     return cf_lookup_hash(cf, no, vno);
 438 }
 439
 440 static zint cf_new_flat(CFile cf, zint no)
 441 {
 442     zint vno = (cf->head.next_block)++;
 443
 444     cf_write_flat(cf, no, vno);
 445     return vno;
 446 }
 447
 448 static zint cf_new_hash(CFile cf, zint no)
 449 {
 450     int hno = cf_hash(cf, no);
 451     struct CFile_hash_bucket *hbprev = NULL, *hb = cf->parray[hno];
 452     zint *bucketpp = &cf->array[hno];
 453     int i;
 454     zint vno = (cf->head.next_block)++;
 455
 456     for (hb = cf->parray[hno]; hb; hb = hb->h_next)
 457         if (!hb->ph.vno[HASH_BUCKET-1])
 458             for (i = 0; i<HASH_BUCKET; i++)
 459                 if (!hb->ph.vno[i])
 460                 {
 461                     (cf->no_hits)++;
 462                     hb->ph.no[i] = no;
 463                     hb->ph.vno[i] = vno;
 464                     hb->dirty = 1;
 465                     return vno;
 466                 }
 467
 468     while (*bucketpp)
 469     {
 470         for (hb = cf->parray[hno]; hb; hb = hb->h_next)
 471             if (hb->ph.this_bucket == *bucketpp)
 472             {
 473                 bucketpp = &hb->ph.next_bucket;
 474                 hbprev = hb;
 475                 break;
 476             }
 477         if (hb)
 478             continue;
 479
 480 #if 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                 return 0;
 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  * c-file-style: "Stroustrup"
 649  * indent-tabs-mode: nil
 650  * End:
 651  * vim: shiftwidth=4 tabstop=8 expandtab
 652  */
 653