root / page_cache.c @ 99afc91d
History | View | Annotate | Download (5 kB)
1 | 9fb26641 | Orit Wasserman | /*
|
---|---|---|---|
2 | 9fb26641 | Orit Wasserman | * Page cache for QEMU
|
3 | 9fb26641 | Orit Wasserman | * The cache is base on a hash of the page address
|
4 | 9fb26641 | Orit Wasserman | *
|
5 | 9fb26641 | Orit Wasserman | * Copyright 2012 Red Hat, Inc. and/or its affiliates
|
6 | 9fb26641 | Orit Wasserman | *
|
7 | 9fb26641 | Orit Wasserman | * Authors:
|
8 | 9fb26641 | Orit Wasserman | * Orit Wasserman <owasserm@redhat.com>
|
9 | 9fb26641 | Orit Wasserman | *
|
10 | 9fb26641 | Orit Wasserman | * This work is licensed under the terms of the GNU GPL, version 2 or later.
|
11 | 9fb26641 | Orit Wasserman | * See the COPYING file in the top-level directory.
|
12 | 9fb26641 | Orit Wasserman | *
|
13 | 9fb26641 | Orit Wasserman | */
|
14 | 9fb26641 | Orit Wasserman | |
15 | 9fb26641 | Orit Wasserman | #include <stdint.h> |
16 | 9fb26641 | Orit Wasserman | #include <stdio.h> |
17 | 9fb26641 | Orit Wasserman | #include <stdlib.h> |
18 | 9fb26641 | Orit Wasserman | #include <strings.h> |
19 | 9fb26641 | Orit Wasserman | #include <string.h> |
20 | 9fb26641 | Orit Wasserman | #include <sys/time.h> |
21 | 9fb26641 | Orit Wasserman | #include <sys/types.h> |
22 | 9fb26641 | Orit Wasserman | #include <stdbool.h> |
23 | 9fb26641 | Orit Wasserman | #include <glib.h> |
24 | 9fb26641 | Orit Wasserman | #include <strings.h> |
25 | 9fb26641 | Orit Wasserman | |
26 | 9fb26641 | Orit Wasserman | #include "qemu-common.h" |
27 | 9fb26641 | Orit Wasserman | #include "qemu/page_cache.h" |
28 | 9fb26641 | Orit Wasserman | |
29 | 9fb26641 | Orit Wasserman | #ifdef DEBUG_CACHE
|
30 | 9fb26641 | Orit Wasserman | #define DPRINTF(fmt, ...) \
|
31 | 9fb26641 | Orit Wasserman | do { fprintf(stdout, "cache: " fmt, ## __VA_ARGS__); } while (0) |
32 | 9fb26641 | Orit Wasserman | #else
|
33 | 9fb26641 | Orit Wasserman | #define DPRINTF(fmt, ...) \
|
34 | 9fb26641 | Orit Wasserman | do { } while (0) |
35 | 9fb26641 | Orit Wasserman | #endif
|
36 | 9fb26641 | Orit Wasserman | |
37 | 9fb26641 | Orit Wasserman | typedef struct CacheItem CacheItem; |
38 | 9fb26641 | Orit Wasserman | |
39 | 9fb26641 | Orit Wasserman | struct CacheItem {
|
40 | 9fb26641 | Orit Wasserman | uint64_t it_addr; |
41 | 9fb26641 | Orit Wasserman | uint64_t it_age; |
42 | 9fb26641 | Orit Wasserman | uint8_t *it_data; |
43 | 9fb26641 | Orit Wasserman | }; |
44 | 9fb26641 | Orit Wasserman | |
45 | 9fb26641 | Orit Wasserman | struct PageCache {
|
46 | 9fb26641 | Orit Wasserman | CacheItem *page_cache; |
47 | 9fb26641 | Orit Wasserman | unsigned int page_size; |
48 | 9fb26641 | Orit Wasserman | int64_t max_num_items; |
49 | 9fb26641 | Orit Wasserman | uint64_t max_item_age; |
50 | 9fb26641 | Orit Wasserman | int64_t num_items; |
51 | 9fb26641 | Orit Wasserman | }; |
52 | 9fb26641 | Orit Wasserman | |
53 | 9fb26641 | Orit Wasserman | PageCache *cache_init(int64_t num_pages, unsigned int page_size) |
54 | 9fb26641 | Orit Wasserman | { |
55 | 9fb26641 | Orit Wasserman | int64_t i; |
56 | 9fb26641 | Orit Wasserman | |
57 | 9fb26641 | Orit Wasserman | PageCache *cache; |
58 | 9fb26641 | Orit Wasserman | |
59 | 9fb26641 | Orit Wasserman | if (num_pages <= 0) { |
60 | 9fb26641 | Orit Wasserman | DPRINTF("invalid number of pages\n");
|
61 | 9fb26641 | Orit Wasserman | return NULL; |
62 | 9fb26641 | Orit Wasserman | } |
63 | 9fb26641 | Orit Wasserman | |
64 | 9fb26641 | Orit Wasserman | cache = g_malloc(sizeof(*cache));
|
65 | 9fb26641 | Orit Wasserman | |
66 | 9fb26641 | Orit Wasserman | /* round down to the nearest power of 2 */
|
67 | 9fb26641 | Orit Wasserman | if (!is_power_of_2(num_pages)) {
|
68 | 9fb26641 | Orit Wasserman | num_pages = pow2floor(num_pages); |
69 | 9fb26641 | Orit Wasserman | DPRINTF("rounding down to %" PRId64 "\n", num_pages); |
70 | 9fb26641 | Orit Wasserman | } |
71 | 9fb26641 | Orit Wasserman | cache->page_size = page_size; |
72 | 9fb26641 | Orit Wasserman | cache->num_items = 0;
|
73 | 9fb26641 | Orit Wasserman | cache->max_item_age = 0;
|
74 | 9fb26641 | Orit Wasserman | cache->max_num_items = num_pages; |
75 | 9fb26641 | Orit Wasserman | |
76 | 9fb26641 | Orit Wasserman | DPRINTF("Setting cache buckets to %" PRId64 "\n", cache->max_num_items); |
77 | 9fb26641 | Orit Wasserman | |
78 | 9fb26641 | Orit Wasserman | cache->page_cache = g_malloc((cache->max_num_items) * |
79 | 9fb26641 | Orit Wasserman | sizeof(*cache->page_cache));
|
80 | 9fb26641 | Orit Wasserman | |
81 | 9fb26641 | Orit Wasserman | for (i = 0; i < cache->max_num_items; i++) { |
82 | 9fb26641 | Orit Wasserman | cache->page_cache[i].it_data = NULL;
|
83 | 9fb26641 | Orit Wasserman | cache->page_cache[i].it_age = 0;
|
84 | 9fb26641 | Orit Wasserman | cache->page_cache[i].it_addr = -1;
|
85 | 9fb26641 | Orit Wasserman | } |
86 | 9fb26641 | Orit Wasserman | |
87 | 9fb26641 | Orit Wasserman | return cache;
|
88 | 9fb26641 | Orit Wasserman | } |
89 | 9fb26641 | Orit Wasserman | |
90 | 9fb26641 | Orit Wasserman | void cache_fini(PageCache *cache)
|
91 | 9fb26641 | Orit Wasserman | { |
92 | 9fb26641 | Orit Wasserman | int64_t i; |
93 | 9fb26641 | Orit Wasserman | |
94 | 9fb26641 | Orit Wasserman | g_assert(cache); |
95 | 9fb26641 | Orit Wasserman | g_assert(cache->page_cache); |
96 | 9fb26641 | Orit Wasserman | |
97 | 9fb26641 | Orit Wasserman | for (i = 0; i < cache->max_num_items; i++) { |
98 | 9fb26641 | Orit Wasserman | g_free(cache->page_cache[i].it_data); |
99 | 9fb26641 | Orit Wasserman | } |
100 | 9fb26641 | Orit Wasserman | |
101 | 9fb26641 | Orit Wasserman | g_free(cache->page_cache); |
102 | 9fb26641 | Orit Wasserman | cache->page_cache = NULL;
|
103 | 9fb26641 | Orit Wasserman | } |
104 | 9fb26641 | Orit Wasserman | |
105 | 9fb26641 | Orit Wasserman | static size_t cache_get_cache_pos(const PageCache *cache, |
106 | 9fb26641 | Orit Wasserman | uint64_t address) |
107 | 9fb26641 | Orit Wasserman | { |
108 | 9fb26641 | Orit Wasserman | size_t pos; |
109 | 9fb26641 | Orit Wasserman | |
110 | 9fb26641 | Orit Wasserman | g_assert(cache->max_num_items); |
111 | 9fb26641 | Orit Wasserman | pos = (address / cache->page_size) & (cache->max_num_items - 1);
|
112 | 9fb26641 | Orit Wasserman | return pos;
|
113 | 9fb26641 | Orit Wasserman | } |
114 | 9fb26641 | Orit Wasserman | |
115 | 9fb26641 | Orit Wasserman | bool cache_is_cached(const PageCache *cache, uint64_t addr) |
116 | 9fb26641 | Orit Wasserman | { |
117 | 9fb26641 | Orit Wasserman | size_t pos; |
118 | 9fb26641 | Orit Wasserman | |
119 | 9fb26641 | Orit Wasserman | g_assert(cache); |
120 | 9fb26641 | Orit Wasserman | g_assert(cache->page_cache); |
121 | 9fb26641 | Orit Wasserman | |
122 | 9fb26641 | Orit Wasserman | pos = cache_get_cache_pos(cache, addr); |
123 | 9fb26641 | Orit Wasserman | |
124 | 9fb26641 | Orit Wasserman | return (cache->page_cache[pos].it_addr == addr);
|
125 | 9fb26641 | Orit Wasserman | } |
126 | 9fb26641 | Orit Wasserman | |
127 | 9fb26641 | Orit Wasserman | static CacheItem *cache_get_by_addr(const PageCache *cache, uint64_t addr) |
128 | 9fb26641 | Orit Wasserman | { |
129 | 9fb26641 | Orit Wasserman | size_t pos; |
130 | 9fb26641 | Orit Wasserman | |
131 | 9fb26641 | Orit Wasserman | g_assert(cache); |
132 | 9fb26641 | Orit Wasserman | g_assert(cache->page_cache); |
133 | 9fb26641 | Orit Wasserman | |
134 | 9fb26641 | Orit Wasserman | pos = cache_get_cache_pos(cache, addr); |
135 | 9fb26641 | Orit Wasserman | |
136 | 9fb26641 | Orit Wasserman | return &cache->page_cache[pos];
|
137 | 9fb26641 | Orit Wasserman | } |
138 | 9fb26641 | Orit Wasserman | |
139 | 9fb26641 | Orit Wasserman | uint8_t *get_cached_data(const PageCache *cache, uint64_t addr)
|
140 | 9fb26641 | Orit Wasserman | { |
141 | 9fb26641 | Orit Wasserman | return cache_get_by_addr(cache, addr)->it_data;
|
142 | 9fb26641 | Orit Wasserman | } |
143 | 9fb26641 | Orit Wasserman | |
144 | 9fb26641 | Orit Wasserman | void cache_insert(PageCache *cache, uint64_t addr, uint8_t *pdata)
|
145 | 9fb26641 | Orit Wasserman | { |
146 | 9fb26641 | Orit Wasserman | |
147 | 9fb26641 | Orit Wasserman | CacheItem *it = NULL;
|
148 | 9fb26641 | Orit Wasserman | |
149 | 9fb26641 | Orit Wasserman | g_assert(cache); |
150 | 9fb26641 | Orit Wasserman | g_assert(cache->page_cache); |
151 | 9fb26641 | Orit Wasserman | |
152 | 9fb26641 | Orit Wasserman | /* actual update of entry */
|
153 | 9fb26641 | Orit Wasserman | it = cache_get_by_addr(cache, addr); |
154 | 9fb26641 | Orit Wasserman | |
155 | 9fb26641 | Orit Wasserman | if (!it->it_data) {
|
156 | 9fb26641 | Orit Wasserman | cache->num_items++; |
157 | 9fb26641 | Orit Wasserman | } |
158 | 9fb26641 | Orit Wasserman | |
159 | 9fb26641 | Orit Wasserman | it->it_data = pdata; |
160 | 9fb26641 | Orit Wasserman | it->it_age = ++cache->max_item_age; |
161 | 9fb26641 | Orit Wasserman | it->it_addr = addr; |
162 | 9fb26641 | Orit Wasserman | } |
163 | 9fb26641 | Orit Wasserman | |
164 | 9fb26641 | Orit Wasserman | int64_t cache_resize(PageCache *cache, int64_t new_num_pages) |
165 | 9fb26641 | Orit Wasserman | { |
166 | 9fb26641 | Orit Wasserman | PageCache *new_cache; |
167 | 9fb26641 | Orit Wasserman | int64_t i; |
168 | 9fb26641 | Orit Wasserman | |
169 | 9fb26641 | Orit Wasserman | CacheItem *old_it, *new_it; |
170 | 9fb26641 | Orit Wasserman | |
171 | 9fb26641 | Orit Wasserman | g_assert(cache); |
172 | 9fb26641 | Orit Wasserman | |
173 | 9fb26641 | Orit Wasserman | /* cache was not inited */
|
174 | 9fb26641 | Orit Wasserman | if (cache->page_cache == NULL) { |
175 | 9fb26641 | Orit Wasserman | return -1; |
176 | 9fb26641 | Orit Wasserman | } |
177 | 9fb26641 | Orit Wasserman | |
178 | 9fb26641 | Orit Wasserman | /* same size */
|
179 | 9fb26641 | Orit Wasserman | if (pow2floor(new_num_pages) == cache->max_num_items) {
|
180 | 9fb26641 | Orit Wasserman | return cache->max_num_items;
|
181 | 9fb26641 | Orit Wasserman | } |
182 | 9fb26641 | Orit Wasserman | |
183 | 9fb26641 | Orit Wasserman | new_cache = cache_init(new_num_pages, cache->page_size); |
184 | 9fb26641 | Orit Wasserman | if (!(new_cache)) {
|
185 | 9fb26641 | Orit Wasserman | DPRINTF("Error creating new cache\n");
|
186 | 9fb26641 | Orit Wasserman | return -1; |
187 | 9fb26641 | Orit Wasserman | } |
188 | 9fb26641 | Orit Wasserman | |
189 | 9fb26641 | Orit Wasserman | /* move all data from old cache */
|
190 | 9fb26641 | Orit Wasserman | for (i = 0; i < cache->max_num_items; i++) { |
191 | 9fb26641 | Orit Wasserman | old_it = &cache->page_cache[i]; |
192 | 9fb26641 | Orit Wasserman | if (old_it->it_addr != -1) { |
193 | 9fb26641 | Orit Wasserman | /* check for collision, if there is, keep MRU page */
|
194 | 9fb26641 | Orit Wasserman | new_it = cache_get_by_addr(new_cache, old_it->it_addr); |
195 | 9fb26641 | Orit Wasserman | if (new_it->it_data) {
|
196 | 9fb26641 | Orit Wasserman | /* keep the MRU page */
|
197 | 9fb26641 | Orit Wasserman | if (new_it->it_age >= old_it->it_age) {
|
198 | 9fb26641 | Orit Wasserman | g_free(old_it->it_data); |
199 | 9fb26641 | Orit Wasserman | } else {
|
200 | 9fb26641 | Orit Wasserman | g_free(new_it->it_data); |
201 | 9fb26641 | Orit Wasserman | new_it->it_data = old_it->it_data; |
202 | 9fb26641 | Orit Wasserman | new_it->it_age = old_it->it_age; |
203 | 9fb26641 | Orit Wasserman | new_it->it_addr = old_it->it_addr; |
204 | 9fb26641 | Orit Wasserman | } |
205 | 9fb26641 | Orit Wasserman | } else {
|
206 | 9fb26641 | Orit Wasserman | cache_insert(new_cache, old_it->it_addr, old_it->it_data); |
207 | 9fb26641 | Orit Wasserman | } |
208 | 9fb26641 | Orit Wasserman | } |
209 | 9fb26641 | Orit Wasserman | } |
210 | 9fb26641 | Orit Wasserman | |
211 | 9fb26641 | Orit Wasserman | cache->page_cache = new_cache->page_cache; |
212 | 9fb26641 | Orit Wasserman | cache->max_num_items = new_cache->max_num_items; |
213 | 9fb26641 | Orit Wasserman | cache->num_items = new_cache->num_items; |
214 | 9fb26641 | Orit Wasserman | |
215 | 9fb26641 | Orit Wasserman | g_free(new_cache); |
216 | 9fb26641 | Orit Wasserman | |
217 | 9fb26641 | Orit Wasserman | return cache->max_num_items;
|
218 | 9fb26641 | Orit Wasserman | } |