1 /*
2 * core/cache.c: A simple LRU-based cache implementation.
3 *
4 */
5
6 #include <stdio.h>
7 #include <string.h>
8 #include <dprintf.h>
9 #include "core.h"
10 #include "cache.h"
11
12
13 /*
14 * Initialize the cache data structres. the _block_size_shift_ specify
15 * the block size, which is 512 byte for FAT fs of the current
16 * implementation since the block(cluster) size in FAT is a bit big.
17 */
cache_init(struct device * dev,int block_size_shift)18 void cache_init(struct device *dev, int block_size_shift)
19 {
20 struct cache *prev, *cur;
21 char *data = dev->cache_data;
22 struct cache *head, *cache;
23 int i;
24
25 dev->cache_block_size = 1 << block_size_shift;
26
27 if (dev->cache_size < dev->cache_block_size + 2*sizeof(struct cache)) {
28 dev->cache_head = NULL;
29 return; /* Cache unusably small */
30 }
31
32 /* We need one struct cache for the headnode plus one for each block */
33 dev->cache_entries =
34 (dev->cache_size - sizeof(struct cache))/
35 (dev->cache_block_size + sizeof(struct cache));
36
37 dev->cache_head = head = (struct cache *)
38 (data + (dev->cache_entries << block_size_shift));
39 cache = head + 1; /* First cache descriptor */
40
41 head->prev = &cache[dev->cache_entries-1];
42 head->prev->next = head;
43 head->block = -1;
44 head->data = NULL;
45
46 prev = head;
47
48 for (i = 0; i < dev->cache_entries; i++) {
49 cur = &cache[i];
50 cur->data = data;
51 cur->block = -1;
52 cur->prev = prev;
53 prev->next = cur;
54 data += dev->cache_block_size;
55 prev = cur++;
56 }
57
58 dev->cache_init = 1; /* Set cache as initialized */
59 }
60
61 /*
62 * Lock a block permanently in the cache by removing it
63 * from the LRU chain.
64 */
cache_lock_block(struct cache * cs)65 void cache_lock_block(struct cache *cs)
66 {
67 cs->prev->next = cs->next;
68 cs->next->prev = cs->prev;
69
70 cs->next = cs->prev = NULL;
71 }
72
73 /*
74 * Check for a particular BLOCK in the block cache,
75 * and if it is already there, just do nothing and return;
76 * otherwise pick a victim block and update the LRU link.
77 */
_get_cache_block(struct device * dev,block_t block)78 struct cache *_get_cache_block(struct device *dev, block_t block)
79 {
80 struct cache *head = dev->cache_head;
81 struct cache *cs;
82 int i;
83
84 cs = dev->cache_head + 1;
85
86 for (i = 0; i < dev->cache_entries; i++) {
87 if (cs->block == block)
88 goto found;
89 cs++;
90 }
91
92 /* Not found, pick a victim */
93 cs = head->next;
94
95 found:
96 /* Move to the end of the LRU chain, unless the block is already locked */
97 if (cs->next) {
98 cs->prev->next = cs->next;
99 cs->next->prev = cs->prev;
100
101 cs->prev = head->prev;
102 head->prev->next = cs;
103 cs->next = head;
104 head->prev = cs;
105 }
106
107 return cs;
108 }
109
110 /*
111 * Check for a particular BLOCK in the block cache,
112 * and if it is already there, just do nothing and return;
113 * otherwise load it from disk and update the LRU link.
114 * Return the data pointer.
115 */
get_cache(struct device * dev,block_t block)116 const void *get_cache(struct device *dev, block_t block)
117 {
118 struct cache *cs;
119
120 cs = _get_cache_block(dev, block);
121 if (cs->block != block) {
122 cs->block = block;
123 getoneblk(dev->disk, cs->data, block, dev->cache_block_size);
124 }
125
126 return cs->data;
127 }
128
129 /*
130 * Read data from the cache at an arbitrary byte offset and length.
131 * This is useful for filesystems whose metadata is not necessarily
132 * aligned with their blocks.
133 *
134 * This is still reading linearly on the disk.
135 */
cache_read(struct fs_info * fs,void * buf,uint64_t offset,size_t count)136 size_t cache_read(struct fs_info *fs, void *buf, uint64_t offset, size_t count)
137 {
138 const char *cd;
139 char *p = buf;
140 size_t off, cnt, total;
141 block_t block;
142
143 total = count;
144 while (count) {
145 block = offset >> fs->block_shift;
146 off = offset & (fs->block_size - 1);
147 cd = get_cache(fs->fs_dev, block);
148 if (!cd)
149 break;
150 cnt = fs->block_size - off;
151 if (cnt > count)
152 cnt = count;
153 memcpy(p, cd + off, cnt);
154 count -= cnt;
155 p += cnt;
156 offset += cnt;
157 }
158 return total - count;
159 }
160