bfile/cfile.c

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