First version
[3rdparty/ote_partner/tlk.git] / lib / bcache / bcache.c
1 /*
2  * Copyright (c) 2007 Travis Geiselbrecht
3  *
4  * Permission is hereby granted, free of charge, to any person obtaining
5  * a copy of this software and associated documentation files
6  * (the "Software"), to deal in the Software without restriction,
7  * including without limitation the rights to use, copy, modify, merge,
8  * publish, distribute, sublicense, and/or sell copies of the Software,
9  * and to permit persons to whom the Software is furnished to do so,
10  * subject to the following conditions:
11  * 
12  * The above copyright notice and this permission notice shall be
13  * included in all copies or substantial portions of the Software.
14  * 
15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
16  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
17  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
18  * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
19  * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
20  * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
21  * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
22  */
23 #include <list.h>
24 #include <stdlib.h>
25 #include <assert.h>
26 #include <string.h>
27 #include <sys/types.h>
28 #include <debug.h>
29 #include <lib/bcache.h>
30 #include <lib/bio.h>
31
32 #define LOCAL_TRACE 0
33
34 struct bcache_block {
35         struct list_node node;
36         bnum_t blocknum;
37         int ref_count;
38         bool is_dirty;
39         void *ptr;
40 };
41
42 struct bcache_stats {
43         uint32_t hits;
44         uint32_t depth;
45         uint32_t misses;
46         uint32_t reads;
47         uint32_t writes;
48 };
49
50 struct bcache {
51         bdev_t *dev;
52         size_t block_size;
53         int count;
54         struct bcache_stats stats;
55
56         struct list_node free_list;
57         struct list_node lru_list;
58
59         struct bcache_block *blocks;
60 };
61
62 bcache_t bcache_create(bdev_t *dev, size_t block_size, int block_count)
63 {
64         struct bcache *cache;
65
66         cache = malloc(sizeof(struct bcache));
67         
68         cache->dev = dev;
69         cache->block_size = block_size;
70         cache->count = block_count;
71         memset(&cache->stats, 0, sizeof(cache->stats));
72
73         list_initialize(&cache->free_list);
74         list_initialize(&cache->lru_list);
75
76         cache->blocks = malloc(sizeof(struct bcache_block) * block_count);
77         int i;
78         for (i=0; i < block_count; i++) {
79                 cache->blocks[i].ref_count = 0;
80                 cache->blocks[i].is_dirty = false;
81                 cache->blocks[i].ptr = malloc(block_size);
82                 // add to the free list
83                 list_add_head(&cache->free_list, &cache->blocks[i].node);       
84         }
85
86         return (bcache_t)cache;
87 }
88
89 static int flush_block(struct bcache *cache, struct bcache_block *block)
90 {
91         int rc;
92
93         rc = bio_write(cache->dev, block->ptr,
94                         (off_t)block->blocknum * cache->block_size,
95                         cache->block_size);
96         if (rc < 0)
97                 goto exit;
98
99         block->is_dirty = false;
100         cache->stats.writes++;
101         rc = 0;
102 exit:
103         return (rc);
104 }
105
106 void bcache_destroy(bcache_t _cache)
107 {
108         struct bcache *cache = _cache;
109         int i;
110
111         for (i=0; i < cache->count; i++) {
112                 DEBUG_ASSERT(cache->blocks[i].ref_count == 0);
113
114                 if (cache->blocks[i].is_dirty)
115                         printf("warning: freeing dirty block %u\n",
116                                 cache->blocks[i].blocknum);
117
118                 free(cache->blocks[i].ptr);
119         }
120
121         free(cache);
122 }
123
124 /* find a block if it's already present */
125 static struct bcache_block *find_block(struct bcache *cache, uint blocknum)
126 {
127         uint32_t depth = 0;
128         struct bcache_block *block;
129
130         LTRACEF("num %u\n", blocknum);
131
132         block = NULL;
133         list_for_every_entry(&cache->lru_list, block, struct bcache_block, node) {
134                 LTRACEF("looking at entry %p, num %u\n", block, block->blocknum);
135                 depth++;
136
137                 if (block->blocknum == blocknum) {
138                         list_delete(&block->node);
139                         list_add_tail(&cache->lru_list, &block->node);
140                         cache->stats.hits++;
141                         cache->stats.depth += depth;
142                         return block;
143                 }
144         }
145
146         cache->stats.misses++;
147         return NULL;
148 }
149
150 /* allocate a new block */
151 static struct bcache_block *alloc_block(struct bcache *cache)
152 {
153         int err;
154         struct bcache_block *block;
155
156         /* pop one off the free list if it's present */
157         block = list_remove_head_type(&cache->free_list, struct bcache_block, node);
158         if (block) {
159                 block->ref_count = 0;
160                 list_add_tail(&cache->lru_list, &block->node);
161                 LTRACEF("found block %p on free list\n", block);
162                 return block;
163         }
164
165         /* walk the lru, looking for a free block */
166         list_for_every_entry(&cache->lru_list, block, struct bcache_block, node) {
167                 LTRACEF("looking at %p, num %u\n", block, block->blocknum);
168                 if (block->ref_count == 0) {
169                         if (block->is_dirty) {
170                                 err = flush_block(cache, block);
171                                 if (err)
172                                         return NULL;
173                         }
174
175                         // add it to the tail of the lru
176                         list_delete(&block->node);
177                         list_add_tail(&cache->lru_list, &block->node);
178                         return block;
179                 }
180         }
181
182         return NULL;
183 }
184
185 static struct bcache_block *find_or_fill_block(struct bcache *cache, uint blocknum)
186 {
187         int err;
188
189         LTRACEF("block %u\n", blocknum);
190
191         /* see if it's already in the cache */
192         struct bcache_block *block = find_block(cache, blocknum);
193         if (block == NULL) {
194                 LTRACEF("wasn't allocated\n");
195
196                 /* allocate a new block and fill it */
197                 block = alloc_block(cache);
198                 DEBUG_ASSERT(block);
199
200                 LTRACEF("wasn't allocated, new block %p\n", block);
201
202                 block->blocknum = blocknum;
203                 err = bio_read(cache->dev, block->ptr, (off_t)blocknum * cache->block_size, cache->block_size);
204                 if (err < 0) {
205                         /* free the block, return an error */
206                         list_add_tail(&cache->free_list, &block->node);
207                         return NULL;
208                 }
209
210                 cache->stats.reads++;
211         }
212
213         DEBUG_ASSERT(block->blocknum == blocknum);
214
215         return block;
216 }
217
218 int bcache_read_block(bcache_t _cache, void *buf, uint blocknum)
219 {
220         struct bcache *cache = _cache;
221
222         LTRACEF("buf %p, blocknum %u\n", buf, blocknum);
223
224         struct bcache_block *block = find_or_fill_block(cache, blocknum);
225         if (block == NULL) {
226                 /* error */
227                 return -1;
228         }
229
230         memcpy(buf, block->ptr, cache->block_size);
231         return 0;
232 }
233
234 int bcache_get_block(bcache_t _cache, void **ptr, uint blocknum)
235 {
236         struct bcache *cache = _cache;
237
238         LTRACEF("ptr %p, blocknum %u\n", ptr, blocknum);
239
240         DEBUG_ASSERT(ptr);
241
242         struct bcache_block *block = find_or_fill_block(cache, blocknum);
243         if (block == NULL) {
244                 /* error */
245                 return -1;
246         }
247
248         /* increment the ref count to keep it from being freed */
249         block->ref_count++;
250         *ptr = block->ptr;
251
252         return 0;
253 }
254
255 int bcache_put_block(bcache_t _cache, uint blocknum)
256 {
257         struct bcache *cache = _cache;
258
259         LTRACEF("blocknum %u\n", blocknum);
260
261         struct bcache_block *block = find_block(cache, blocknum);
262
263         /* be pretty hard on the caller for now */
264         DEBUG_ASSERT(block);
265         DEBUG_ASSERT(block->ref_count > 0);
266
267         block->ref_count--;
268
269         return 0;
270 }
271
272 int bcache_mark_block_dirty(bcache_t priv, uint blocknum)
273 {
274         int err;
275         struct bcache *cache = priv;
276         struct bcache_block *block;
277
278         block = find_block(cache, blocknum);
279         if (!block) {
280                 err = -1;
281                 goto exit;
282         }
283
284         block->is_dirty = true;
285         err = 0;
286 exit:
287         return (err);
288 }
289
290 int bcache_zero_block(bcache_t priv, uint blocknum)
291 {
292         int err;
293         struct bcache *cache = priv;
294         struct bcache_block *block;
295
296         block = find_block(cache, blocknum);
297         if (!block) {
298                 block = alloc_block(cache);
299                 if (!block) {
300                         err = -1;
301                         goto exit;
302                 }
303
304                 block->blocknum = blocknum;
305         }
306
307         memset(block->ptr, 0, cache->block_size);
308         block->is_dirty = true;
309         err = 0;
310 exit:
311         return (err);
312 }
313
314 int bcache_flush(bcache_t priv)
315 {
316         int err;
317         struct bcache *cache = priv;
318         struct bcache_block *block;
319
320         list_for_every_entry(&cache->lru_list, block, struct bcache_block, node) {
321                 if (block->is_dirty) {
322                         err = flush_block(cache, block);
323                         if (err)
324                                 goto exit;
325                 }
326         }
327
328         err = 0;
329 exit:
330         return (err);
331 }
332
333 void bcache_dump(bcache_t priv, const char *name)
334 {
335         uint32_t finds;
336         struct bcache *cache = priv;
337
338         finds = cache->stats.hits + cache->stats.misses;
339
340         printf("%s: hits=%u(%u%%) depth=%u misses=%u(%u%%) reads=%u writes=%u\n",
341                 name,
342                 cache->stats.hits,
343                 finds ? (cache->stats.hits * 100) / finds : 0,
344                 cache->stats.hits ? cache->stats.depth / cache->stats.hits : 0,
345                 cache->stats.misses,
346                 finds ? (cache->stats.misses * 100) / finds : 0,
347                 cache->stats.reads,
348                 cache->stats.writes);
349 }