1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
|
/*
* core/cache.c: A simple LRU-based cache implementation.
*
*/
#include <stdio.h>
#include <string.h>
#include <dprintf.h>
#include "core.h"
#include "cache.h"
/*
* Initialize the cache data structres. the _block_size_shift_ specify
* the block size, which is 512 byte for FAT fs of the current
* implementation since the block(cluster) size in FAT is a bit big.
*
*/
void cache_init(struct device *dev, int block_size_shift)
{
struct cache *prev, *cur;
char *data = dev->cache_data;
struct cache *head, *cache;
int i;
dev->cache_block_size = 1 << block_size_shift;
if (dev->cache_size < dev->cache_block_size + 2*sizeof(struct cache)) {
dev->cache_head = NULL;
return; /* Cache unusably small */
}
/* We need one struct cache for the headnode plus one for each block */
dev->cache_entries =
(dev->cache_size - sizeof(struct cache))/
(dev->cache_block_size + sizeof(struct cache));
dev->cache_head = head = (struct cache *)
(data + (dev->cache_entries << block_size_shift));
cache = dev->cache_head + 1; /* First cache descriptor */
head->prev = &cache[dev->cache_entries-1];
head->next->prev = dev->cache_head;
head->block = -1;
head->data = NULL;
prev = head;
for (i = 0; i < dev->cache_entries; i++) {
cur = &cache[i];
cur->data = data;
cur->block = -1;
cur->prev = prev;
prev->next = cur;
data += dev->cache_block_size;
prev = cur++;
}
}
/*
* Lock a block permanently in the cache
*/
void cache_lock_block(struct cache *cs)
{
cs->prev->next = cs->next;
cs->next->prev = cs->prev;
cs->next = cs->prev = NULL;
}
/*
* Check for a particular BLOCK in the block cache,
* and if it is already there, just do nothing and return;
* otherwise pick a victim block and update the LRU link.
*/
struct cache *_get_cache_block(struct device *dev, block_t block)
{
struct cache *head = dev->cache_head;
struct cache *cs;
int i;
cs = dev->cache_head + 1;
for (i = 0; i < dev->cache_entries; i++) {
if (cs->block == block)
goto found;
cs++;
}
/* Not found, pick a victim */
cs = head->next;
found:
/* Move to the end of the LRU chain, unless the block is already locked */
if (cs->next) {
cs->prev->next = cs->next;
cs->next->prev = cs->prev;
cs->prev = head->prev;
head->prev->next = cs;
cs->next = head;
head->prev = cs;
}
return cs;
}
/*
* Check for a particular BLOCK in the block cache,
* and if it is already there, just do nothing and return;
* otherwise load it from disk and update the LRU link.
* Return the data pointer.
*/
const void *get_cache(struct device *dev, block_t block)
{
struct cache *cs;
cs = _get_cache_block(dev, block);
if (cs->block != block) {
cs->block = block;
getoneblk(dev->disk, cs->data, block, dev->cache_block_size);
}
return cs->data;
}
|