1/*
2 * This file is part of the KDE project.
3 *
4 * SPDX-FileCopyrightText: 2010 Michael Pyne <mpyne@kde.org>
5 * SPDX-License-Identifier: LGPL-2.0-only
6 */
7
8#ifndef KSDCMEMORY_P_H
9#define KSDCMEMORY_P_H
10
11#include "kcoreaddons_debug.h"
12#include "ksdclock_p.h"
13#include "kshareddatacache.h"
14
15/*
16 * A very simple class whose only purpose is to be thrown as an exception from
17 * underlying code to indicate that the shared cache is apparently corrupt.
18 * This must be caught by top-level library code and used to unlink the cache
19 * in this circumstance.
20 *
21 * @internal
22 */
23class KSDCCorrupted
24{
25public:
26 KSDCCorrupted()
27 {
28 qCWarning(KCOREADDONS_DEBUG) << "Error detected in cache!";
29 }
30
31 KSDCCorrupted(const QString message)
32 {
33 qCWarning(KCOREADDONS_DEBUG).noquote() << message;
34 }
35
36 KSDCCorrupted(const char *message)
37 {
38 KSDCCorrupted(QLatin1String(message));
39 }
40};
41
42typedef qint32 pageID;
43
44// =========================================================================
45// Description of the cache:
46//
47// The shared memory cache is designed to be handled as two separate objects,
48// all contained in the same global memory segment. First off, there is the
49// basic header data, consisting of the global header followed by the
50// accounting data necessary to hold items (described in more detail
51// momentarily). Following the accounting data is the start of the "page table"
52// (essentially just as you'd see it in an Operating Systems text).
53//
54// The page table contains shared memory split into fixed-size pages, with a
55// configurable page size. In the event that the data is too large to fit into
56// a single logical page, it will need to occupy consecutive pages of memory.
57//
58// The accounting data that was referenced earlier is split into two:
59//
60// 1. index table, containing a fixed-size list of possible cache entries.
61// Each index entry is of type IndexTableEntry (below), and holds the various
62// accounting data and a pointer to the first page.
63//
64// 2. page table, which is used to speed up the process of searching for
65// free pages of memory. There is one entry for every page in the page table,
66// and it contains the index of the one entry in the index table actually
67// holding the page (or <0 if the page is free).
68//
69// The entire segment looks like so:
70// ?════════?═════════════?════════════?═══════?═══════?═══════?═══════?═══?
71// ? Header │ Index Table │ Page Table ? Pages │ │ │ │...?
72// ?════════?═════════════?════════════?═══════?═══════?═══════?═══════?═══?
73// =========================================================================
74
75// All elements of this struct must be "plain old data" (POD) types since it
76// will be in shared memory. In addition, no pointers! To point to something
77// you must use relative offsets since the pointer start addresses will be
78// different in each process.
79struct IndexTableEntry {
80 uint fileNameHash;
81 uint totalItemSize; // in bytes
82 mutable uint useCount;
83 time_t addTime;
84 mutable time_t lastUsedTime;
85 pageID firstPage;
86};
87
88// Page table entry
89struct PageTableEntry {
90 // int so we can use values <0 for unassigned pages.
91 qint32 index;
92};
93
94// Each individual page contains the cached data. The first page starts off with
95// the utf8-encoded key, a null '\0', and then the data follows immediately
96// from the next byte, possibly crossing consecutive page boundaries to hold
97// all of the data.
98// There is, however, no specific struct for a page, it is simply a location in
99// memory.
100
101// This is effectively the layout of the shared memory segment. The variables
102// contained within form the header, data contained afterwards is pointed to
103// by using special accessor functions.
104struct SharedMemory {
105 /*
106 * Note to downstream packagers: This version flag is intended to be
107 * machine-specific. The KDE-provided source code will not set the lower
108 * two bits to allow for distribution-specific needs, with the exception
109 * of version 1 which was already defined in KDE Platform 4.5.
110 * e.g. the next version bump will be from 4 to 8, then 12, etc.
111 */
112 enum {
113 PIXMAP_CACHE_VERSION = 12,
114 MINIMUM_CACHE_SIZE = 4096,
115 };
116
117 /// The maximum number of probes to make while searching for a bucket in
118 /// the presence of collisions in the cache index table.
119 static const uint MAX_PROBE_COUNT = 6;
120
121 // Note to those who follow me. You should not, under any circumstances, ever
122 // re-arrange the following two fields, even if you change the version number
123 // for later revisions of this code.
124 QAtomicInt ready; ///< DO NOT INITIALIZE
125 quint8 version;
126
127 // See kshareddatacache_p.h
128 SharedLock shmLock;
129
130 uint cacheSize;
131 uint cacheAvail;
132 QAtomicInt evictionPolicy;
133
134 // pageSize and cacheSize determine the number of pages. The number of
135 // pages determine the page table size and (indirectly) the index table
136 // size.
137 QAtomicInt pageSize;
138
139 // This variable is added to reserve space for later cache timestamping
140 // support. The idea is this variable will be updated when the cache is
141 // written to, to allow clients to detect a changed cache quickly.
142 QAtomicInt cacheTimestamp;
143
144 /*
145 * Converts the given average item size into an appropriate page size.
146 */
147 static unsigned equivalentPageSize(unsigned itemSize);
148
149 // Returns pageSize in unsigned format.
150 unsigned cachePageSize() const;
151
152 /*
153 * This is effectively the class ctor. But since we're in shared memory,
154 * there's a few rules:
155 *
156 * 1. To allow for some form of locking in the initial-setup case, we
157 * use an atomic int, which will be initialized to 0 by mmap(). Then to
158 * take the lock we atomically increment the 0 to 1. If we end up calling
159 * the QAtomicInt constructor we can mess that up, so we can't use a
160 * constructor for this class either.
161 * 2. Any member variable you add takes up space in shared memory as well,
162 * so make sure you need it.
163 */
164 bool performInitialSetup(uint _cacheSize, uint _pageSize);
165
166 void clearInternalTables();
167 const IndexTableEntry *indexTable() const;
168 const PageTableEntry *pageTable() const;
169 const void *cachePages() const;
170 const void *page(pageID at) const;
171
172 // The following are non-const versions of some of the methods defined
173 // above. They use const_cast<> because I feel that is better than
174 // duplicating the code. I suppose template member functions (?)
175 // may work, may investigate later.
176 IndexTableEntry *indexTable();
177 PageTableEntry *pageTable();
178 void *cachePages();
179 void *page(pageID at);
180 uint pageTableSize() const;
181 uint indexTableSize() const;
182
183 /*
184 * @return the index of the first page, for the set of contiguous
185 * pages that can hold @p pagesNeeded PAGES.
186 */
187 pageID findEmptyPages(uint pagesNeeded) const;
188
189 // left < right?
190 static bool lruCompare(const IndexTableEntry &l, const IndexTableEntry &r);
191
192 // left < right?
193 static bool seldomUsedCompare(const IndexTableEntry &l, const IndexTableEntry &r);
194
195 // left < right?
196 static bool ageCompare(const IndexTableEntry &l, const IndexTableEntry &r);
197
198 void defragment();
199
200 /*
201 * Finds the index entry for a given key.
202 * @param key UTF-8 encoded key to search for.
203 * @return The index of the entry in the cache named by @p key. Returns
204 * <0 if no such entry is present.
205 */
206 qint32 findNamedEntry(const QByteArray &key) const;
207
208 // Function to use with std::unique_ptr in removeUsedPages below...
209 static void deleteTable(IndexTableEntry *table);
210
211 /*
212 * Removes the requested number of pages.
213 *
214 * @param numberNeeded the number of pages required to fulfill a current request.
215 * This number should be <0 and <= the number of pages in the cache.
216 * @return The identifier of the beginning of a consecutive block of pages able
217 * to fill the request. Returns a value >= pageTableSize() if no such
218 * request can be filled.
219 * @internal
220 */
221 uint removeUsedPages(uint numberNeeded);
222
223 // Returns the total size required for a given cache size.
224 static uint totalSize(uint cacheSize, uint effectivePageSize);
225
226 uint fileNameHash(const QByteArray &utf8FileName) const;
227 void clear();
228 void removeEntry(uint index);
229
230 static quint32 generateHash(const QByteArray &buffer);
231
232 /*
233 * @return the smallest integer greater than or equal to (@p a / @p b).
234 * @param a Numerator, should be ≥ 0.
235 * @param b Denominator, should be > 0.
236 */
237 static unsigned intCeil(unsigned a, unsigned b);
238};
239
240#endif /* KSDCMEMORY_P_H */
241

source code of kcoreaddons/src/lib/caching/ksdcmemory_p.h