Asterisk - The Open Source Telephony Project  GIT-master-93d0901
hash_buf.c
Go to the documentation of this file.
1 /*-
2  * Copyright (c) 1990, 1993, 1994
3  * The Regents of the University of California. All rights reserved.
4  *
5  * This code is derived from software contributed to Berkeley by
6  * Margo Seltzer.
7  *
8  * Redistribution and use in source and binary forms, with or without
9  * modification, are permitted provided that the following conditions
10  * are met:
11  * 1. Redistributions of source code must retain the above copyright
12  * notice, this list of conditions and the following disclaimer.
13  * 2. Redistributions in binary form must reproduce the above copyright
14  * notice, this list of conditions and the following disclaimer in the
15  * documentation and/or other materials provided with the distribution.
16  * 3. All advertising materials mentioning features or use of this software
17  * must display the following acknowledgement:
18  * This product includes software developed by the University of
19  * California, Berkeley and its contributors.
20  * 4. Neither the name of the University nor the names of its contributors
21  * may be used to endorse or promote products derived from this software
22  * without specific prior written permission.
23  *
24  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
25  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
26  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
27  * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
28  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
29  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
30  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
31  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
32  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
33  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
34  * SUCH DAMAGE.
35  */
36 
37 #if defined(LIBC_SCCS) && !defined(lint)
38 static char sccsid[] = "@(#)hash_buf.c 8.5 (Berkeley) 7/15/94";
39 #endif /* LIBC_SCCS and not lint */
40 
41 /*
42  * PACKAGE: hash
43  *
44  * DESCRIPTION:
45  * Contains buffer management
46  *
47  * ROUTINES:
48  * External
49  * __buf_init
50  * __get_buf
51  * __buf_free
52  * __reclaim_buf
53  * Internal
54  * newbuf
55  */
56 
57 #include <sys/param.h>
58 
59 #include <errno.h>
60 #include <stddef.h>
61 #include <stdio.h>
62 #include <stdlib.h>
63 
64 #ifdef DEBUG
65 #include <assert.h>
66 #endif
67 
68 #include "../include/db.h"
69 #include "hash.h"
70 #include "page.h"
71 #include "extern.h"
72 
74 
75 /* Unlink B from its place in the lru */
76 #define BUF_REMOVE(B) { \
77  (B)->prev->next = (B)->next; \
78  (B)->next->prev = (B)->prev; \
79 }
80 
81 /* Insert B after P */
82 #define BUF_INSERT(B, P) { \
83  (B)->next = (P)->next; \
84  (B)->prev = (P); \
85  (P)->next = (B); \
86  (B)->next->prev = (B); \
87 }
88 
89 #define MRU hashp->bufhead.next
90 #define LRU hashp->bufhead.prev
91 
92 #define MRU_INSERT(B) BUF_INSERT((B), &hashp->bufhead)
93 #define LRU_INSERT(B) BUF_INSERT((B), LRU)
94 
95 /*
96  * We are looking for a buffer with address "addr". If prev_bp is NULL, then
97  * address is a bucket index. If prev_bp is not NULL, then it points to the
98  * page previous to an overflow page that we are trying to find.
99  *
100  * CAVEAT: The buffer header accessed via prev_bp's ovfl field may no longer
101  * be valid. Therefore, you must always verify that its address matches the
102  * address you are seeking.
103  */
104 extern BUFHEAD *
105 __get_buf(hashp, addr, prev_bp, newpage)
106  HTAB *hashp;
107  u_int32_t addr;
108  BUFHEAD *prev_bp;
109  int newpage; /* If prev_bp set, indicates a new overflow page. */
110 {
111  register BUFHEAD *bp;
112  register u_int32_t is_disk_mask;
113  register int is_disk, segment_ndx = 0;
114  SEGMENT segp = 0;
115 
116  is_disk = 0;
117  is_disk_mask = 0;
118  if (prev_bp) {
119  bp = prev_bp->ovfl;
120  if (!bp || (bp->addr != addr))
121  bp = NULL;
122  if (!newpage)
123  is_disk = BUF_DISK;
124  } else {
125  /* Grab buffer out of directory */
126  segment_ndx = addr & (hashp->SGSIZE - 1);
127 
128  /* valid segment ensured by __call_hash() */
129  segp = hashp->dir[addr >> hashp->SSHIFT];
130 #ifdef DEBUG
131  assert(segp != NULL);
132 #endif
133  bp = PTROF(segp[segment_ndx]);
134  is_disk_mask = ISDISK(segp[segment_ndx]);
135  is_disk = is_disk_mask || !hashp->new_file;
136  }
137 
138  if (!bp) {
139  bp = newbuf(hashp, addr, prev_bp);
140  if (!bp ||
141  __get_page(hashp, bp->page, addr, !prev_bp, is_disk, 0))
142  return (NULL);
143  if (!prev_bp)
144  segp[segment_ndx] =
145  (BUFHEAD *)((ptrdiff_t)bp | is_disk_mask);
146  } else {
147  BUF_REMOVE(bp);
148  MRU_INSERT(bp);
149  }
150  return (bp);
151 }
152 
153 /*
154  * We need a buffer for this page. Either allocate one, or evict a resident
155  * one (if we have as many buffers as we're allowed) and put this one in.
156  *
157  * If newbuf finds an error (returning NULL), it also sets errno.
158  */
159 static BUFHEAD *
160 newbuf(hashp, addr, prev_bp)
161  HTAB *hashp;
162  u_int32_t addr;
163  BUFHEAD *prev_bp;
164 {
165  register BUFHEAD *bp; /* The buffer we're going to use */
166  register BUFHEAD *xbp; /* Temp pointer */
167  register BUFHEAD *next_xbp;
168  SEGMENT segp;
169  int segment_ndx;
170  u_int16_t oaddr, *shortp;
171 
172  oaddr = 0;
173  bp = LRU;
174  /*
175  * If LRU buffer is pinned, the buffer pool is too small. We need to
176  * allocate more buffers.
177  */
178  if (hashp->nbufs || (bp->flags & BUF_PIN)) {
179  /* Allocate a new one */
180  if ((bp = (BUFHEAD *)malloc(sizeof(BUFHEAD))) == NULL)
181  return (NULL);
182 #ifdef PURIFY
183  memset(bp, 0xff, sizeof(BUFHEAD));
184 #endif
185  if ((bp->page = (char *)malloc(hashp->BSIZE)) == NULL) {
186  free(bp);
187  return (NULL);
188  }
189 #ifdef PURIFY
190  memset(bp->page, 0xff, hashp->BSIZE);
191 #endif
192  if (hashp->nbufs)
193  hashp->nbufs--;
194  } else {
195  /* Kick someone out */
196  BUF_REMOVE(bp);
197  /*
198  * If this is an overflow page with addr 0, it's already been
199  * flushed back in an overflow chain and initialized.
200  */
201  if ((bp->addr != 0) || (bp->flags & BUF_BUCKET)) {
202  /*
203  * Set oaddr before __put_page so that you get it
204  * before bytes are swapped.
205  */
206  shortp = (u_int16_t *)bp->page;
207  if (shortp[0])
208  oaddr = shortp[shortp[0] - 1];
209  if ((bp->flags & BUF_MOD) && __put_page(hashp, bp->page,
210  bp->addr, (int)IS_BUCKET(bp->flags), 0))
211  return (NULL);
212  /*
213  * Update the pointer to this page (i.e. invalidate it).
214  *
215  * If this is a new file (i.e. we created it at open
216  * time), make sure that we mark pages which have been
217  * written to disk so we retrieve them from disk later,
218  * rather than allocating new pages.
219  */
220  if (IS_BUCKET(bp->flags)) {
221  segment_ndx = bp->addr & (hashp->SGSIZE - 1);
222  segp = hashp->dir[bp->addr >> hashp->SSHIFT];
223 #ifdef DEBUG
224  assert(segp != NULL);
225 #endif
226 
227  if (hashp->new_file &&
228  ((bp->flags & BUF_MOD) ||
229  ISDISK(segp[segment_ndx])))
230  segp[segment_ndx] = (BUFHEAD *)BUF_DISK;
231  else
232  segp[segment_ndx] = NULL;
233  }
234  /*
235  * Since overflow pages can only be access by means of
236  * their bucket, free overflow pages associated with
237  * this bucket.
238  */
239  for (xbp = bp; xbp->ovfl;) {
240  next_xbp = xbp->ovfl;
241  xbp->ovfl = 0;
242  xbp = next_xbp;
243 
244  /* Check that ovfl pointer is up date. */
245  if (IS_BUCKET(xbp->flags) ||
246  (oaddr != xbp->addr))
247  break;
248 
249  shortp = (u_int16_t *)xbp->page;
250  if (shortp[0])
251  /* set before __put_page */
252  oaddr = shortp[shortp[0] - 1];
253  if ((xbp->flags & BUF_MOD) && __put_page(hashp,
254  xbp->page, xbp->addr, 0, 0))
255  return (NULL);
256  xbp->addr = 0;
257  xbp->flags = 0;
258  BUF_REMOVE(xbp);
259  LRU_INSERT(xbp);
260  }
261  }
262  }
263 
264  /* Now assign this buffer */
265  bp->addr = addr;
266 #ifdef DEBUG1
267  (void)fprintf(stderr, "NEWBUF1: %d->ovfl was %d is now %d\n",
268  bp->addr, (bp->ovfl ? bp->ovfl->addr : 0), 0);
269 #endif
270  bp->ovfl = NULL;
271  if (prev_bp) {
272  /*
273  * If prev_bp is set, this is an overflow page, hook it in to
274  * the buffer overflow links.
275  */
276 #ifdef DEBUG1
277  (void)fprintf(stderr, "NEWBUF2: %d->ovfl was %d is now %d\n",
278  prev_bp->addr, (prev_bp->ovfl ? bp->ovfl->addr : 0),
279  (bp ? bp->addr : 0));
280 #endif
281  prev_bp->ovfl = bp;
282  bp->flags = 0;
283  } else
284  bp->flags = BUF_BUCKET;
285  MRU_INSERT(bp);
286  return (bp);
287 }
288 
289 extern void
290 __buf_init(hashp, nbytes)
291  HTAB *hashp;
292  int nbytes;
293 {
294  BUFHEAD *bfp;
295  int npages;
296 
297  bfp = &(hashp->bufhead);
298  npages = (nbytes + hashp->BSIZE - 1) >> hashp->BSHIFT;
299  npages = MAX(npages, MIN_BUFFERS);
300 
301  hashp->nbufs = npages;
302  bfp->next = bfp;
303  bfp->prev = bfp;
304  /*
305  * This space is calloc'd so these are already null.
306  *
307  * bfp->ovfl = NULL;
308  * bfp->flags = 0;
309  * bfp->page = NULL;
310  * bfp->addr = 0;
311  */
312 }
313 
314 extern int
315 __buf_free(hashp, do_free, to_disk)
316  HTAB *hashp;
317  int do_free, to_disk;
318 {
319  BUFHEAD *bp;
320 
321  /* Need to make sure that buffer manager has been initialized */
322  if (!LRU)
323  return (0);
324  for (bp = LRU; bp != &hashp->bufhead;) {
325  /* Check that the buffer is valid */
326  if (bp->addr || IS_BUCKET(bp->flags)) {
327  if (to_disk && (bp->flags & BUF_MOD) &&
328  __put_page(hashp, bp->page,
329  bp->addr, IS_BUCKET(bp->flags), 0))
330  return (-1);
331  }
332  /* Check if we are freeing stuff */
333  if (do_free) {
334  if (bp->page)
335  free(bp->page);
336  BUF_REMOVE(bp);
337  free(bp);
338  bp = LRU;
339  } else
340  bp = bp->prev;
341  }
342  return (0);
343 }
344 
345 extern void
346 __reclaim_buf(hashp, bp)
347  HTAB *hashp;
348  BUFHEAD *bp;
349 {
350  bp->ovfl = 0;
351  bp->addr = 0;
352  bp->flags = 0;
353  BUF_REMOVE(bp);
354  LRU_INSERT(bp);
355 }
if(!yyg->yy_init)
Definition: ast_expr2f.c:868
char * malloc()
void free()
#define MIN_BUFFERS
Definition: hash.h:124
#define PTROF(X)
Definition: hash.h:143
#define BUF_DISK
Definition: hash.h:55
#define IS_BUCKET(X)
Definition: hash.h:60
#define ISDISK(X)
Definition: hash.h:146
#define BUF_BUCKET
Definition: hash.h:56
#define BUF_PIN
Definition: hash.h:57
#define BUF_MOD
Definition: hash.h:54
void __buf_init(HTAB *hashp, int nbytes)
Definition: hash_buf.c:290
#define LRU
Definition: hash_buf.c:90
#define BUF_REMOVE(B)
Definition: hash_buf.c:76
int __buf_free(HTAB *hashp, int do_free, int to_disk)
Definition: hash_buf.c:315
static BUFHEAD *newbuf __P((HTAB *, u_int32_t, BUFHEAD *))
#define MRU_INSERT(B)
Definition: hash_buf.c:92
void __reclaim_buf(HTAB *hashp, BUFHEAD *bp)
Definition: hash_buf.c:346
static BUFHEAD * newbuf(HTAB *hashp, u_int32_t addr, BUFHEAD *prev_bp)
Definition: hash_buf.c:160
BUFHEAD * __get_buf(HTAB *hashp, u_int32_t addr, BUFHEAD *prev_bp, int newpage)
Definition: hash_buf.c:105
#define LRU_INSERT(B)
Definition: hash_buf.c:93
int __put_page(HTAB *hashp, char *p, u_int32_t bucket, int is_bucket, int is_bitmap)
Definition: hash_page.c:578
int __get_page(HTAB *hashp, char *p, u_int32_t bucket, int is_bucket, int is_disk, int is_bitmap)
Definition: hash_page.c:518
unsigned int u_int32_t
unsigned short u_int16_t
#define NULL
Definition: resample.c:96
Definition: hash.h:47
char * page
Definition: hash.h:52
BUFHEAD * ovfl
Definition: hash.h:50
char flags
Definition: hash.h:53
u_int32_t addr
Definition: hash.h:51
BUFHEAD * prev
Definition: hash.h:48
BUFHEAD * next
Definition: hash.h:49
Definition: hash.h:91
BUFHEAD bufhead
Definition: hash.h:116
int new_file
Definition: hash.h:107
SEGMENT * dir
Definition: hash.h:117
int nbufs
Definition: hash.h:114
#define MAX(a, b)
Definition: utils.h:228