Add zebrasrv.pid
[idzebra-moved-to-github.git] / bfile / cfile.c
1 /* $Id: cfile.c,v 1.27 2002-08-02 19:26:55 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 #include <assert.h>
26 #include <stdlib.h>
27 #include <string.h>
28
29 #include <zebrautl.h>
30 #include <mfile.h>
31 #include "cfile.h"
32
33 static int write_head (CFile cf)
34 {
35     int left = cf->head.hash_size * sizeof(int);
36     int bno = 1;
37     const char *tab = (char*) cf->array;
38
39     if (!tab)
40         return 0;
41     while (left >= (int) HASH_BSIZE)
42     {
43         mf_write (cf->hash_mf, bno++, 0, 0, tab);
44         tab += HASH_BSIZE;
45         left -= HASH_BSIZE;
46     }
47     if (left > 0)
48         mf_write (cf->hash_mf, bno, 0, left, tab);
49     return 0;
50 }
51
52 static int read_head (CFile cf)
53 {
54     int left = cf->head.hash_size * sizeof(int);
55     int bno = 1;
56     char *tab = (char*) cf->array;
57
58     if (!tab)
59         return 0;
60     while (left >= (int) HASH_BSIZE)
61     {
62         mf_read (cf->hash_mf, bno++, 0, 0, tab);
63         tab += HASH_BSIZE;
64         left -= HASH_BSIZE;
65     }
66     if (left > 0)
67         mf_read (cf->hash_mf, bno, 0, left, tab);
68     return 0;
69 }
70
71
72 CFile cf_open (MFile mf, MFile_area area, const char *fname,
73                int block_size, int wflag, int *firstp)
74 {
75     char path[1024];
76     int i;
77     CFile cf = (CFile) xmalloc (sizeof(*cf));
78     int hash_bytes;
79    
80     cf->rmf = mf; 
81     logf (LOG_DEBUG, "cf: open %s %s", cf->rmf->name, wflag ? "rdwr" : "rd");
82     sprintf (path, "%s-b", fname);
83     if (!(cf->block_mf = mf_open (area, path, block_size, wflag)))
84     {
85         logf (LOG_FATAL|LOG_ERRNO, "Failed to open %s", path);
86         exit (1);
87     }
88     sprintf (path, "%s-i", fname);
89     if (!(cf->hash_mf = mf_open (area, path, HASH_BSIZE, wflag)))
90     {
91         logf (LOG_FATAL|LOG_ERRNO, "Failed to open %s", path);
92         exit (1);
93     }
94     assert (firstp);
95     if (!mf_read (cf->hash_mf, 0, 0, sizeof(cf->head), &cf->head) ||
96         !cf->head.state)
97     {
98         *firstp = 1;
99         cf->head.state = 1;
100         cf->head.block_size = block_size;
101         cf->head.hash_size = 199;
102         hash_bytes = cf->head.hash_size * sizeof(int);
103         cf->head.flat_bucket = cf->head.next_bucket = cf->head.first_bucket = 
104             (hash_bytes+sizeof(cf->head))/HASH_BSIZE + 2;
105         cf->head.next_block = 1;
106         if (wflag)
107             mf_write (cf->hash_mf, 0, 0, sizeof(cf->head), &cf->head);
108         cf->array = (int *) xmalloc (hash_bytes);
109         for (i = 0; i<cf->head.hash_size; i++)
110             cf->array[i] = 0;
111         if (wflag)
112             write_head (cf);
113     }
114     else
115     {
116         *firstp = 0;
117         assert (cf->head.block_size == block_size);
118         assert (cf->head.hash_size > 2);
119         hash_bytes = cf->head.hash_size * sizeof(int);
120         assert (cf->head.next_bucket > 0);
121         assert (cf->head.next_block > 0);
122         if (cf->head.state == 1)
123             cf->array = (int *) xmalloc (hash_bytes);
124         else
125             cf->array = NULL;
126         read_head (cf);
127     }
128     if (cf->head.state == 1)
129     {
130         cf->parray = (struct CFile_hash_bucket **)
131             xmalloc (cf->head.hash_size * sizeof(*cf->parray));
132         for (i = 0; i<cf->head.hash_size; i++)
133             cf->parray[i] = NULL;
134     }
135     else
136         cf->parray = NULL;
137     cf->bucket_lru_front = cf->bucket_lru_back = NULL;
138     cf->bucket_in_memory = 0;
139     cf->max_bucket_in_memory = 100;
140     cf->dirty = 0;
141     cf->iobuf = (char *) xmalloc (cf->head.block_size);
142     memset (cf->iobuf, 0, cf->head.block_size);
143     cf->no_hits = 0;
144     cf->no_miss = 0;
145     zebra_mutex_init (&cf->mutex);
146     return cf;
147 }
148
149 static int cf_hash (CFile cf, int no)
150 {
151     return (no>>3) % cf->head.hash_size;
152 }
153
154 static void release_bucket (CFile cf, struct CFile_hash_bucket *p)
155 {
156     if (p->lru_prev)
157         p->lru_prev->lru_next = p->lru_next;
158     else
159         cf->bucket_lru_back = p->lru_next;
160     if (p->lru_next)
161         p->lru_next->lru_prev = p->lru_prev;
162     else
163         cf->bucket_lru_front = p->lru_prev;
164
165     *p->h_prev = p->h_next;
166     if (p->h_next)
167         p->h_next->h_prev = p->h_prev;
168     
169     --(cf->bucket_in_memory);
170     xfree (p);
171 }
172
173 static void flush_bucket (CFile cf, int no_to_flush)
174 {
175     int i;
176     struct CFile_hash_bucket *p;
177
178     for (i = 0; i != no_to_flush; i++)
179     {
180         p = cf->bucket_lru_back;
181         if (!p)
182             break;
183         if (p->dirty)
184         {
185             mf_write (cf->hash_mf, p->ph.this_bucket, 0, 0, &p->ph);
186             cf->dirty = 1;
187         }
188         release_bucket (cf, p);
189     }
190 }
191
192 static struct CFile_hash_bucket *alloc_bucket (CFile cf, int block_no, int hno)
193 {
194     struct CFile_hash_bucket *p, **pp;
195
196     if (cf->bucket_in_memory == cf->max_bucket_in_memory)
197         flush_bucket (cf, 1);
198     assert (cf->bucket_in_memory < cf->max_bucket_in_memory);
199     ++(cf->bucket_in_memory);
200     p = (struct CFile_hash_bucket *) xmalloc (sizeof(*p));
201
202     p->lru_next = NULL;
203     p->lru_prev = cf->bucket_lru_front;
204     if (cf->bucket_lru_front)
205         cf->bucket_lru_front->lru_next = p;
206     else
207         cf->bucket_lru_back = p;
208     cf->bucket_lru_front = p; 
209
210     pp = cf->parray + hno;
211     p->h_next = *pp;
212     p->h_prev = pp;
213     if (*pp)
214         (*pp)->h_prev = &p->h_next;
215     *pp = p;
216     return p;
217 }
218
219 static struct CFile_hash_bucket *get_bucket (CFile cf, int block_no, int hno)
220 {
221     struct CFile_hash_bucket *p;
222
223     p = alloc_bucket (cf, block_no, hno);
224     if (!mf_read (cf->hash_mf, block_no, 0, 0, &p->ph))
225     {
226         logf (LOG_FATAL|LOG_ERRNO, "read get_bucket");
227         exit (1);
228     }
229     assert (p->ph.this_bucket == block_no);
230     p->dirty = 0;
231     return p;
232 }
233
234 static struct CFile_hash_bucket *new_bucket (CFile cf, int *block_nop, int hno)
235 {
236     struct CFile_hash_bucket *p;
237     int i, block_no;
238
239     block_no = *block_nop = cf->head.next_bucket++;
240     p = alloc_bucket (cf, block_no, hno);
241
242     for (i = 0; i<HASH_BUCKET; i++)
243     {
244         p->ph.vno[i] = 0;
245         p->ph.no[i] = 0;
246     }
247     p->ph.next_bucket = 0;
248     p->ph.this_bucket = block_no;
249     p->dirty = 1;
250     return p;
251 }
252
253 static int cf_lookup_flat (CFile cf, int no)
254 {
255     int hno = (no*sizeof(int))/HASH_BSIZE;
256     int off = (no*sizeof(int)) - hno*HASH_BSIZE;
257     int vno = 0;
258
259     mf_read (cf->hash_mf, hno+cf->head.next_bucket, off, sizeof(int), &vno);
260     return vno;
261 }
262
263 static int cf_lookup_hash (CFile cf, int no)
264 {
265     int hno = cf_hash (cf, no);
266     struct CFile_hash_bucket *hb;
267     int block_no, i;
268
269     for (hb = cf->parray[hno]; hb; hb = hb->h_next)
270     {
271         for (i = 0; i<HASH_BUCKET && hb->ph.vno[i]; i++)
272             if (hb->ph.no[i] == no)
273             {
274                 (cf->no_hits)++;
275                 return hb->ph.vno[i];
276             }
277     }
278     for (block_no = cf->array[hno]; block_no; block_no = hb->ph.next_bucket)
279     {
280         for (hb = cf->parray[hno]; hb; hb = hb->h_next)
281         {
282             if (hb->ph.this_bucket == block_no)
283                 break;
284         }
285         if (hb)
286             continue;
287 #if 0
288         /* extra check ... */
289         for (hb = cf->bucket_lru_back; hb; hb = hb->lru_next)
290         {
291             if (hb->ph.this_bucket == block_no)
292             {
293                 logf (LOG_FATAL, "Found hash bucket on other chain (1)");
294                 abort ();
295             }
296             for (i = 0; i<HASH_BUCKET && hb->ph.vno[i]; i++)
297                 if (hb->ph.no[i] == no)
298                 {
299                     logf (LOG_FATAL, "Found hash bucket on other chain (2)");
300                     abort ();
301                 }
302         }
303 #endif
304         (cf->no_miss)++;
305         hb = get_bucket (cf, block_no, hno);
306         for (i = 0; i<HASH_BUCKET && hb->ph.vno[i]; i++)
307             if (hb->ph.no[i] == no)
308                 return hb->ph.vno[i];
309     }
310     return 0;
311 }
312
313 static void cf_write_flat (CFile cf, int no, int vno)
314 {
315     int hno = (no*sizeof(int))/HASH_BSIZE;
316     int off = (no*sizeof(int)) - hno*HASH_BSIZE;
317
318     hno += cf->head.next_bucket;
319     if (hno >= cf->head.flat_bucket)
320         cf->head.flat_bucket = hno+1;
321     cf->dirty = 1;
322     mf_write (cf->hash_mf, hno, off, sizeof(int), &vno);
323 }
324
325 static void cf_moveto_flat (CFile cf)
326 {
327     struct CFile_hash_bucket *p;
328     int i, j;
329
330     logf (LOG_DEBUG, "cf: Moving to flat shadow: %s", cf->rmf->name);
331     logf (LOG_DEBUG, "cf: hits=%d miss=%d bucket_in_memory=%d total=%d",
332         cf->no_hits, cf->no_miss, cf->bucket_in_memory, 
333         cf->head.next_bucket - cf->head.first_bucket);
334     assert (cf->head.state == 1);
335     flush_bucket (cf, -1);
336     assert (cf->bucket_in_memory == 0);
337     p = (struct CFile_hash_bucket *) xmalloc (sizeof(*p));
338     for (i = cf->head.first_bucket; i < cf->head.next_bucket; i++)
339     {
340         if (!mf_read (cf->hash_mf, i, 0, 0, &p->ph))
341         {
342             logf (LOG_FATAL|LOG_ERRNO, "read bucket moveto flat");
343             exit (1);
344         }
345         for (j = 0; j < HASH_BUCKET && p->ph.vno[j]; j++)
346             cf_write_flat (cf, p->ph.no[j], p->ph.vno[j]);
347     }
348     xfree (p);
349     xfree (cf->array);
350     cf->array = NULL;
351     xfree (cf->parray);
352     cf->parray = NULL;
353     cf->head.state = 2;
354     cf->dirty = 1;
355 }
356
357 static int cf_lookup (CFile cf, int no)
358 {
359     if (cf->head.state > 1)
360         return cf_lookup_flat (cf, no);
361     return cf_lookup_hash (cf, no);
362 }
363
364 static int cf_new_flat (CFile cf, int no)
365 {
366     int vno = (cf->head.next_block)++;
367
368     cf_write_flat (cf, no, vno);
369     return vno;
370 }
371
372 static int cf_new_hash (CFile cf, int no)
373 {
374     int hno = cf_hash (cf, no);
375     struct CFile_hash_bucket *hbprev = NULL, *hb = cf->parray[hno];
376     int *bucketpp = &cf->array[hno]; 
377     int i, vno = (cf->head.next_block)++;
378   
379     for (hb = cf->parray[hno]; hb; hb = hb->h_next)
380         if (!hb->ph.vno[HASH_BUCKET-1])
381             for (i = 0; i<HASH_BUCKET; i++)
382                 if (!hb->ph.vno[i])
383                 {
384                     (cf->no_hits)++;
385                     hb->ph.no[i] = no;
386                     hb->ph.vno[i] = vno;
387                     hb->dirty = 1;
388                     return vno;
389                 }
390
391     while (*bucketpp)
392     {
393         for (hb = cf->parray[hno]; hb; hb = hb->h_next)
394             if (hb->ph.this_bucket == *bucketpp)
395             {
396                 bucketpp = &hb->ph.next_bucket;
397                 hbprev = hb;
398                 break;
399             }
400         if (hb)
401             continue;
402
403 #if 0
404         /* extra check ... */
405         for (hb = cf->bucket_lru_back; hb; hb = hb->lru_next)
406         {
407             if (hb->ph.this_bucket == *bucketpp)
408             {
409                 logf (LOG_FATAL, "Found hash bucket on other chain");
410                 abort ();
411             }
412         }
413 #endif
414         (cf->no_miss)++;
415         hb = get_bucket (cf, *bucketpp, hno);
416         assert (hb);
417         for (i = 0; i<HASH_BUCKET; i++)
418             if (!hb->ph.vno[i])
419             {
420                 hb->ph.no[i] = no;
421                 hb->ph.vno[i] = vno;
422                 hb->dirty = 1;
423                 return vno;
424             }
425         bucketpp = &hb->ph.next_bucket;
426         hbprev = hb;
427     }
428     if (hbprev)
429         hbprev->dirty = 1;
430     hb = new_bucket (cf, bucketpp, hno);
431     hb->ph.no[0] = no;
432     hb->ph.vno[0] = vno;
433     return vno;
434 }
435
436 int cf_new (CFile cf, int no)
437 {
438     if (cf->head.state > 1)
439         return cf_new_flat (cf, no);
440     if (cf->no_miss*2 > cf->no_hits)
441     {
442         cf_moveto_flat (cf);
443         assert (cf->head.state > 1);
444         return cf_new_flat (cf, no);
445     }
446     return cf_new_hash (cf, no);
447 }
448
449
450 int cf_read (CFile cf, int no, int offset, int nbytes, void *buf)
451 {
452     int block;
453     
454     assert (cf);
455     zebra_mutex_lock (&cf->mutex);
456     if (!(block = cf_lookup (cf, no)))
457     {
458         zebra_mutex_unlock (&cf->mutex);
459         return -1;
460     }
461     zebra_mutex_unlock (&cf->mutex);
462     if (!mf_read (cf->block_mf, block, offset, nbytes, buf))
463     {
464         logf (LOG_FATAL|LOG_ERRNO, "cf_read no=%d, block=%d", no, block);
465         exit (1);
466     }
467     return 1;
468 }
469
470 int cf_write (CFile cf, int no, int offset, int nbytes, const void *buf)
471 {
472     int block;
473
474     assert (cf);
475     zebra_mutex_lock (&cf->mutex);
476     if (!(block = cf_lookup (cf, no)))
477     {
478         block = cf_new (cf, no);
479         if (offset || nbytes)
480         {
481             mf_read (cf->rmf, no, 0, 0, cf->iobuf);
482             memcpy (cf->iobuf + offset, buf, nbytes);
483             buf = cf->iobuf;
484             offset = 0;
485             nbytes = 0;
486         }
487     }
488     zebra_mutex_unlock (&cf->mutex);
489     if (mf_write (cf->block_mf, block, offset, nbytes, buf))
490     {
491         logf (LOG_FATAL|LOG_ERRNO, "cf_write no=%d, block=%d", no, block);
492         exit (1);
493     }
494     return 0;
495 }
496
497 int cf_close (CFile cf)
498 {
499     logf (LOG_DEBUG, "cf: close hits=%d miss=%d bucket_in_memory=%d total=%d",
500           cf->no_hits, cf->no_miss, cf->bucket_in_memory,
501           cf->head.next_bucket - cf->head.first_bucket);
502     flush_bucket (cf, -1);
503     if (cf->dirty)
504     {
505         mf_write (cf->hash_mf, 0, 0, sizeof(cf->head), &cf->head);
506         write_head (cf);
507     }
508     mf_close (cf->hash_mf);
509     mf_close (cf->block_mf);
510     xfree (cf->array);
511     xfree (cf->parray);
512     xfree (cf->iobuf);
513     zebra_mutex_destroy (&cf->mutex);
514     xfree (cf);
515     return 0;
516 }
517