Commit | Line | Data |
---|---|---|
70544bea MO |
1 | /*- |
2 | * Copyright (c) 1990 The Regents of the University of California. | |
3 | * All rights reserved. | |
4 | * | |
5 | * This code is derived from software contributed to Berkeley by | |
6 | * Mike Olson. | |
7 | * | |
8 | * %sccs.include.redist.c% | |
9 | */ | |
10 | ||
11 | #if defined(LIBC_SCCS) && !defined(lint) | |
fb91cf55 | 12 | static char sccsid[] = "@(#)lrutils.c 5.2 (Berkeley) %G%"; |
70544bea MO |
13 | #endif /* LIBC_SCCS and not lint */ |
14 | ||
fb91cf55 KB |
15 | #include <stdlib.h> |
16 | #include <string.h> | |
70544bea MO |
17 | #include "lrucache.h" |
18 | ||
19 | /* | |
20 | * LRUGETPG -- Get a free page from the LRU cache. | |
21 | * | |
22 | * This routine grows the cache if necessary, finds an unused page if | |
23 | * it can, and handles flushing dirty buffers to disk. | |
24 | * | |
25 | * One of the parameters to this routine (f) is the routine that called | |
26 | * us. If we have to grow the cache, we call this routine recursively | |
27 | * in order to fill the buffer. The reason for this is that we have | |
28 | * two interfaces that call lrugetpg(). Lruget() fills a page from disk, | |
29 | * and lrugetnew() just allocates a new (empty) page. | |
30 | * | |
31 | * Parameters: | |
32 | * l -- LRU cache to use. | |
33 | * pgno -- page number for which we want a buffer | |
34 | * nread -- pointer to an int to get number of bytes read | |
35 | * f -- who called us | |
36 | * | |
37 | * Returns: | |
38 | * (char *) pointer to buffer to use, or NULL on failure. | |
39 | * | |
40 | * Warnings: | |
41 | * The buffer returned is locked down until the user does an | |
42 | * explicit lrurelease() on it. | |
43 | */ | |
44 | ||
45 | char * | |
46 | lrugetpg(l, pgno, nread, f) | |
47 | LRUCACHE *l; | |
48 | int pgno; | |
49 | int *nread; | |
50 | char *(*f)(); | |
51 | { | |
52 | CACHE_ENT *ce; | |
53 | LRU_ENT *lruent; | |
54 | char *buffer; | |
55 | ||
56 | /* if we're allowed to grow the cache, do so */ | |
57 | if (l->lru_cursz < l->lru_csize) { | |
58 | ||
59 | /* get a buffer */ | |
60 | if ((buffer = (char *) malloc((unsigned) l->lru_psize)) | |
61 | == (char *) NULL) | |
62 | return ((char *) NULL); | |
63 | ||
64 | /* get and LRU list entry */ | |
65 | if ((lruent = (LRU_ENT *) malloc((unsigned) sizeof(LRU_ENT))) | |
66 | == (LRU_ENT *) NULL) | |
67 | return ((char *) NULL); | |
68 | lruent->l_buffer = buffer; | |
69 | lruent->l_pgno = pgno; | |
70 | lruent->l_flags = NULL; | |
71 | ||
72 | /* manage spaghetti */ | |
73 | lruent->l_prev = (LRU_ENT *) NULL; | |
74 | lruent->l_next = l->lru_head; | |
75 | if (l->lru_head != (LRU_ENT *) NULL) | |
76 | l->lru_head->l_prev = lruent; | |
77 | l->lru_head = lruent; | |
78 | if (l->lru_tail == (LRU_ENT *) NULL) | |
79 | l->lru_tail = lruent; | |
80 | ||
81 | /* add it to the hash table */ | |
82 | ce = lruhashput(l, pgno, lruent); | |
83 | l->lru_cursz++; | |
84 | } else { | |
85 | lruent = l->lru_tail; | |
86 | ||
87 | /* find the oldest unused buffer */ | |
88 | while (lruent != (LRU_ENT *) NULL | |
89 | && !(lruent->l_flags & F_FREE)) | |
90 | lruent = lruent->l_prev; | |
91 | ||
92 | /* if no free buffer was found, we have to grow the cache */ | |
93 | if (lruent == (LRU_ENT *) NULL) { | |
94 | if (lrugrow(l) < 0) | |
95 | return ((char *) NULL); | |
96 | return ((*f)((LRU) l, pgno, nread)); | |
97 | } | |
98 | ||
99 | /* okay, found a free buffer -- update hash table and list */ | |
100 | ce = lruhashget(l, lruent->l_pgno); | |
101 | if (lruhashdel(l, lruent->l_pgno) < 0) | |
102 | return ((char *) NULL); | |
103 | ||
104 | /* flush the old page to disk, if necessary */ | |
105 | if (lruent->l_flags & F_DIRTY) | |
106 | if (lruflush(l, lruent) < 0) | |
107 | return ((char *) NULL); | |
108 | ||
109 | /* update stats, hash table, and list */ | |
110 | lruent->l_pgno = pgno; | |
111 | lruhead(l, lruent); | |
112 | ce = lruhashput(l, pgno, lruent); | |
113 | buffer = lruent->l_buffer; | |
114 | } | |
115 | #ifdef lint | |
116 | ce = ce; | |
117 | #endif /* lint */ | |
118 | ||
119 | /* lock this page down */ | |
120 | lruent->l_flags &= ~F_FREE; | |
121 | ||
122 | return (buffer); | |
123 | } | |
124 | ||
125 | /* | |
126 | * LRUHEAD -- Move an LRU list entry to the head of the list. | |
127 | * | |
128 | * The head of the list is where the most recently used item goes. | |
129 | * | |
130 | * Parameters: | |
131 | * l -- LRU cache | |
132 | * lruent -- entry to move to the head of the list | |
133 | * | |
134 | * Returns: | |
135 | * None | |
136 | * | |
137 | * Side Effects: | |
138 | * Updates the cache's head and tail pointers as required. | |
139 | */ | |
140 | ||
141 | void | |
142 | lruhead(l, lruent) | |
143 | LRUCACHE *l; | |
144 | LRU_ENT *lruent; | |
145 | { | |
146 | LRU_ENT *next; | |
147 | LRU_ENT *prev; | |
148 | ||
149 | if (l->lru_head == lruent) | |
150 | return; | |
151 | ||
152 | next = lruent->l_next; | |
153 | prev = lruent->l_prev; | |
154 | lruent->l_prev = (LRU_ENT *) NULL; | |
155 | lruent->l_next = l->lru_head; | |
156 | l->lru_head->l_prev = lruent; | |
157 | l->lru_head = lruent; | |
158 | ||
159 | prev->l_next = next; | |
160 | if (next != (LRU_ENT *) NULL) | |
161 | next->l_prev = prev; | |
162 | ||
163 | if (l->lru_tail == lruent) | |
164 | l->lru_tail = prev; | |
165 | } | |
166 | ||
167 | /* | |
168 | * LRUGROW -- Grow the LRU cache | |
169 | * | |
170 | * This routine is called only if we can't satisfy a user's get() request | |
171 | * using an existing buffer. We need to rebuild the hash table so that | |
172 | * subsequent lookups work correctly, since the cache size is used to | |
173 | * compute hash keys. | |
174 | * | |
175 | * Parameters: | |
176 | * l -- LRU cache to grow | |
177 | * | |
178 | * Returns: | |
179 | * Zero on success, -1 on failure | |
180 | */ | |
181 | ||
182 | int | |
183 | lrugrow(l) | |
184 | LRUCACHE *l; | |
185 | { | |
186 | int oldsz, newsz; | |
187 | CACHE_ENT **new; | |
188 | CACHE_ENT *ce, *nce; | |
189 | int h; | |
190 | int i; | |
191 | ||
192 | oldsz = l->lru_csize; | |
193 | newsz = l->lru_csize + 1; | |
194 | ||
195 | /* get a new hash table */ | |
196 | if ((new = (CACHE_ENT **) malloc((unsigned)newsz * sizeof(CACHE_ENT *))) | |
197 | == (CACHE_ENT **) NULL) | |
198 | return (-1); | |
199 | ||
200 | /* build the new hash table */ | |
201 | bzero((char *) new, (size_t) (newsz * sizeof(CACHE_ENT *))); | |
202 | for (i = oldsz; --i >= 0; ) { | |
203 | for (ce = l->lru_cache[i]; ce != (CACHE_ENT *) NULL; ) { | |
204 | nce = ce->c_chain; | |
205 | h = ce->c_pgno % newsz; | |
206 | ce->c_chain = new[h]; | |
207 | new[h] = ce; | |
208 | ce = nce; | |
209 | } | |
210 | } | |
211 | ||
212 | /* get rid of the old hash table, and update the cache */ | |
213 | free ((char *) (l->lru_cache)); | |
214 | l->lru_cache = new; | |
215 | l->lru_csize = newsz; | |
216 | ||
217 | return (0); | |
218 | } |