1298800caSStefan Hajnoczi /*
2298800caSStefan Hajnoczi * QEMU Enhanced Disk Format L2 Cache
3298800caSStefan Hajnoczi *
4298800caSStefan Hajnoczi * Copyright IBM, Corp. 2010
5298800caSStefan Hajnoczi *
6298800caSStefan Hajnoczi * Authors:
7298800caSStefan Hajnoczi * Anthony Liguori <aliguori@us.ibm.com>
8298800caSStefan Hajnoczi *
9298800caSStefan Hajnoczi * This work is licensed under the terms of the GNU LGPL, version 2 or later.
10298800caSStefan Hajnoczi * See the COPYING.LIB file in the top-level directory.
11298800caSStefan Hajnoczi *
12298800caSStefan Hajnoczi */
13298800caSStefan Hajnoczi
14298800caSStefan Hajnoczi /*
15298800caSStefan Hajnoczi * L2 table cache usage is as follows:
16298800caSStefan Hajnoczi *
17298800caSStefan Hajnoczi * An open image has one L2 table cache that is used to avoid accessing the
18298800caSStefan Hajnoczi * image file for recently referenced L2 tables.
19298800caSStefan Hajnoczi *
20298800caSStefan Hajnoczi * Cluster offset lookup translates the logical offset within the block device
21298800caSStefan Hajnoczi * to a cluster offset within the image file. This is done by indexing into
22298800caSStefan Hajnoczi * the L1 and L2 tables which store cluster offsets. It is here where the L2
23298800caSStefan Hajnoczi * table cache serves up recently referenced L2 tables.
24298800caSStefan Hajnoczi *
25298800caSStefan Hajnoczi * If there is a cache miss, that L2 table is read from the image file and
26298800caSStefan Hajnoczi * committed to the cache. Subsequent accesses to that L2 table will be served
27298800caSStefan Hajnoczi * from the cache until the table is evicted from the cache.
28298800caSStefan Hajnoczi *
29298800caSStefan Hajnoczi * L2 tables are also committed to the cache when new L2 tables are allocated
30298800caSStefan Hajnoczi * in the image file. Since the L2 table cache is write-through, the new L2
31298800caSStefan Hajnoczi * table is first written out to the image file and then committed to the
32298800caSStefan Hajnoczi * cache.
33298800caSStefan Hajnoczi *
34298800caSStefan Hajnoczi * Multiple I/O requests may be using an L2 table cache entry at any given
35298800caSStefan Hajnoczi * time. That means an entry may be in use across several requests and
36298800caSStefan Hajnoczi * reference counting is needed to free the entry at the correct time. In
37298800caSStefan Hajnoczi * particular, an entry evicted from the cache will only be freed once all
38298800caSStefan Hajnoczi * references are dropped.
39298800caSStefan Hajnoczi *
40298800caSStefan Hajnoczi * An in-flight I/O request will hold a reference to a L2 table cache entry for
41298800caSStefan Hajnoczi * the period during which it needs to access the L2 table. This includes
42298800caSStefan Hajnoczi * cluster offset lookup, L2 table allocation, and L2 table update when a new
43298800caSStefan Hajnoczi * data cluster has been allocated.
44298800caSStefan Hajnoczi *
45298800caSStefan Hajnoczi * An interesting case occurs when two requests need to access an L2 table that
46298800caSStefan Hajnoczi * is not in the cache. Since the operation to read the table from the image
47298800caSStefan Hajnoczi * file takes some time to complete, both requests may see a cache miss and
48298800caSStefan Hajnoczi * start reading the L2 table from the image file. The first to finish will
49298800caSStefan Hajnoczi * commit its L2 table into the cache. When the second tries to commit its
50298800caSStefan Hajnoczi * table will be deleted in favor of the existing cache entry.
51298800caSStefan Hajnoczi */
52298800caSStefan Hajnoczi
5380c71a24SPeter Maydell #include "qemu/osdep.h"
54*5df022cfSPeter Maydell #include "qemu/memalign.h"
55298800caSStefan Hajnoczi #include "trace.h"
56298800caSStefan Hajnoczi #include "qed.h"
57298800caSStefan Hajnoczi
58298800caSStefan Hajnoczi /* Each L2 holds 2GB so this let's us fully cache a 100GB disk */
59298800caSStefan Hajnoczi #define MAX_L2_CACHE_SIZE 50
60298800caSStefan Hajnoczi
61298800caSStefan Hajnoczi /**
62298800caSStefan Hajnoczi * Initialize the L2 cache
63298800caSStefan Hajnoczi */
qed_init_l2_cache(L2TableCache * l2_cache)64298800caSStefan Hajnoczi void qed_init_l2_cache(L2TableCache *l2_cache)
65298800caSStefan Hajnoczi {
66298800caSStefan Hajnoczi QTAILQ_INIT(&l2_cache->entries);
67298800caSStefan Hajnoczi l2_cache->n_entries = 0;
68298800caSStefan Hajnoczi }
69298800caSStefan Hajnoczi
70298800caSStefan Hajnoczi /**
71298800caSStefan Hajnoczi * Free the L2 cache
72298800caSStefan Hajnoczi */
qed_free_l2_cache(L2TableCache * l2_cache)73298800caSStefan Hajnoczi void qed_free_l2_cache(L2TableCache *l2_cache)
74298800caSStefan Hajnoczi {
75298800caSStefan Hajnoczi CachedL2Table *entry, *next_entry;
76298800caSStefan Hajnoczi
77298800caSStefan Hajnoczi QTAILQ_FOREACH_SAFE(entry, &l2_cache->entries, node, next_entry) {
78298800caSStefan Hajnoczi qemu_vfree(entry->table);
797267c094SAnthony Liguori g_free(entry);
80298800caSStefan Hajnoczi }
81298800caSStefan Hajnoczi }
82298800caSStefan Hajnoczi
83298800caSStefan Hajnoczi /**
84298800caSStefan Hajnoczi * Allocate an uninitialized entry from the cache
85298800caSStefan Hajnoczi *
86298800caSStefan Hajnoczi * The returned entry has a reference count of 1 and is owned by the caller.
87298800caSStefan Hajnoczi * The caller must allocate the actual table field for this entry and it must
88298800caSStefan Hajnoczi * be freeable using qemu_vfree().
89298800caSStefan Hajnoczi */
qed_alloc_l2_cache_entry(L2TableCache * l2_cache)90298800caSStefan Hajnoczi CachedL2Table *qed_alloc_l2_cache_entry(L2TableCache *l2_cache)
91298800caSStefan Hajnoczi {
92298800caSStefan Hajnoczi CachedL2Table *entry;
93298800caSStefan Hajnoczi
947267c094SAnthony Liguori entry = g_malloc0(sizeof(*entry));
95298800caSStefan Hajnoczi entry->ref++;
96298800caSStefan Hajnoczi
97298800caSStefan Hajnoczi trace_qed_alloc_l2_cache_entry(l2_cache, entry);
98298800caSStefan Hajnoczi
99298800caSStefan Hajnoczi return entry;
100298800caSStefan Hajnoczi }
101298800caSStefan Hajnoczi
102298800caSStefan Hajnoczi /**
103298800caSStefan Hajnoczi * Decrease an entry's reference count and free if necessary when the reference
104298800caSStefan Hajnoczi * count drops to zero.
1051f01e50bSPaolo Bonzini *
1061f01e50bSPaolo Bonzini * Called with table_lock held.
107298800caSStefan Hajnoczi */
qed_unref_l2_cache_entry(CachedL2Table * entry)108298800caSStefan Hajnoczi void qed_unref_l2_cache_entry(CachedL2Table *entry)
109298800caSStefan Hajnoczi {
110298800caSStefan Hajnoczi if (!entry) {
111298800caSStefan Hajnoczi return;
112298800caSStefan Hajnoczi }
113298800caSStefan Hajnoczi
114298800caSStefan Hajnoczi entry->ref--;
115298800caSStefan Hajnoczi trace_qed_unref_l2_cache_entry(entry, entry->ref);
116298800caSStefan Hajnoczi if (entry->ref == 0) {
117298800caSStefan Hajnoczi qemu_vfree(entry->table);
1187267c094SAnthony Liguori g_free(entry);
119298800caSStefan Hajnoczi }
120298800caSStefan Hajnoczi }
121298800caSStefan Hajnoczi
122298800caSStefan Hajnoczi /**
123298800caSStefan Hajnoczi * Find an entry in the L2 cache. This may return NULL and it's up to the
124298800caSStefan Hajnoczi * caller to satisfy the cache miss.
125298800caSStefan Hajnoczi *
126298800caSStefan Hajnoczi * For a cached entry, this function increases the reference count and returns
127298800caSStefan Hajnoczi * the entry.
1281f01e50bSPaolo Bonzini *
1291f01e50bSPaolo Bonzini * Called with table_lock held.
130298800caSStefan Hajnoczi */
qed_find_l2_cache_entry(L2TableCache * l2_cache,uint64_t offset)131298800caSStefan Hajnoczi CachedL2Table *qed_find_l2_cache_entry(L2TableCache *l2_cache, uint64_t offset)
132298800caSStefan Hajnoczi {
133298800caSStefan Hajnoczi CachedL2Table *entry;
134298800caSStefan Hajnoczi
135298800caSStefan Hajnoczi QTAILQ_FOREACH(entry, &l2_cache->entries, node) {
136298800caSStefan Hajnoczi if (entry->offset == offset) {
137298800caSStefan Hajnoczi trace_qed_find_l2_cache_entry(l2_cache, entry, offset, entry->ref);
138298800caSStefan Hajnoczi entry->ref++;
139298800caSStefan Hajnoczi return entry;
140298800caSStefan Hajnoczi }
141298800caSStefan Hajnoczi }
142298800caSStefan Hajnoczi return NULL;
143298800caSStefan Hajnoczi }
144298800caSStefan Hajnoczi
145298800caSStefan Hajnoczi /**
146298800caSStefan Hajnoczi * Commit an L2 cache entry into the cache. This is meant to be used as part of
147298800caSStefan Hajnoczi * the process to satisfy a cache miss. A caller would allocate an entry which
148298800caSStefan Hajnoczi * is not actually in the L2 cache and then once the entry was valid and
149298800caSStefan Hajnoczi * present on disk, the entry can be committed into the cache.
150298800caSStefan Hajnoczi *
151298800caSStefan Hajnoczi * Since the cache is write-through, it's important that this function is not
152298800caSStefan Hajnoczi * called until the entry is present on disk and the L1 has been updated to
153298800caSStefan Hajnoczi * point to the entry.
154298800caSStefan Hajnoczi *
155298800caSStefan Hajnoczi * N.B. This function steals a reference to the l2_table from the caller so the
156298800caSStefan Hajnoczi * caller must obtain a new reference by issuing a call to
157298800caSStefan Hajnoczi * qed_find_l2_cache_entry().
1581f01e50bSPaolo Bonzini *
1591f01e50bSPaolo Bonzini * Called with table_lock held.
160298800caSStefan Hajnoczi */
qed_commit_l2_cache_entry(L2TableCache * l2_cache,CachedL2Table * l2_table)161298800caSStefan Hajnoczi void qed_commit_l2_cache_entry(L2TableCache *l2_cache, CachedL2Table *l2_table)
162298800caSStefan Hajnoczi {
163298800caSStefan Hajnoczi CachedL2Table *entry;
164298800caSStefan Hajnoczi
165298800caSStefan Hajnoczi entry = qed_find_l2_cache_entry(l2_cache, l2_table->offset);
166298800caSStefan Hajnoczi if (entry) {
167298800caSStefan Hajnoczi qed_unref_l2_cache_entry(entry);
168298800caSStefan Hajnoczi qed_unref_l2_cache_entry(l2_table);
169298800caSStefan Hajnoczi return;
170298800caSStefan Hajnoczi }
171298800caSStefan Hajnoczi
17214fe292dSStefan Hajnoczi /* Evict an unused cache entry so we have space. If all entries are in use
17314fe292dSStefan Hajnoczi * we can grow the cache temporarily and we try to shrink back down later.
17414fe292dSStefan Hajnoczi */
175298800caSStefan Hajnoczi if (l2_cache->n_entries >= MAX_L2_CACHE_SIZE) {
17614fe292dSStefan Hajnoczi CachedL2Table *next;
17714fe292dSStefan Hajnoczi QTAILQ_FOREACH_SAFE(entry, &l2_cache->entries, node, next) {
17814fe292dSStefan Hajnoczi if (entry->ref > 1) {
17914fe292dSStefan Hajnoczi continue;
18014fe292dSStefan Hajnoczi }
18114fe292dSStefan Hajnoczi
182298800caSStefan Hajnoczi QTAILQ_REMOVE(&l2_cache->entries, entry, node);
183298800caSStefan Hajnoczi l2_cache->n_entries--;
184298800caSStefan Hajnoczi qed_unref_l2_cache_entry(entry);
18514fe292dSStefan Hajnoczi
18614fe292dSStefan Hajnoczi /* Stop evicting when we've shrunk back to max size */
18714fe292dSStefan Hajnoczi if (l2_cache->n_entries < MAX_L2_CACHE_SIZE) {
18814fe292dSStefan Hajnoczi break;
18914fe292dSStefan Hajnoczi }
19014fe292dSStefan Hajnoczi }
191298800caSStefan Hajnoczi }
192298800caSStefan Hajnoczi
193298800caSStefan Hajnoczi l2_cache->n_entries++;
194298800caSStefan Hajnoczi QTAILQ_INSERT_TAIL(&l2_cache->entries, l2_table, node);
195298800caSStefan Hajnoczi }
196