1 /*
2 * Copyright 2014 Vincent Sanders <vince@netsurf-browser.org>
3 *
4 * This file is part of NetSurf, http://www.netsurf-browser.org/
5 *
6 * NetSurf is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; version 2 of the License.
9 *
10 * NetSurf is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 * GNU General Public License for more details.
14 *
15 * You should have received a copy of the GNU General Public License
16 * along with this program. If not, see <http://www.gnu.org/licenses/>.
17 */
18
19 /**
20 * \file
21 * Low-level resource cache persistent storage implementation.
22 *
23 * file based backing store.
24 *
25 * \todo Consider improving eviction sorting to include objects size
26 * and remaining lifetime and other cost metrics.
27 *
28 * \todo Implement mmap retrieval where supported.
29 *
30 * \todo Implement static retrieval for metadata objects as their heap
31 * lifetime is typically very short, though this may be obsoleted
32 * by a small object storage strategy.
33 *
34 */
35
36 #include <unistd.h>
37 #include <string.h>
38 #include <sys/stat.h>
39 #include <sys/types.h>
40 #include <fcntl.h>
41 #include <errno.h>
42 #include <time.h>
43 #include <stdlib.h>
44 #include <nsutils/unistd.h>
45
46 #include "netsurf/inttypes.h"
47 #include "utils/filepath.h"
48 #include "utils/file.h"
49 #include "utils/nsurl.h"
50 #include "utils/log.h"
51 #include "utils/messages.h"
52 #include "utils/hashmap.h"
53 #include "desktop/gui_internal.h"
54 #include "netsurf/misc.h"
55
56 #include "content/backing_store.h"
57
58 /** Backing store file format version */
59 #define CONTROL_VERSION 202
60
61 /**
62 * Number of milliseconds after a update before control data
63 * maintenance is performed
64 */
65 #define CONTROL_MAINT_TIME 10000
66
67 /** Filename of serialised entries */
68 #define ENTRIES_FNAME "entries"
69
70 /** Filename of block file index */
71 #define BLOCKS_FNAME "blocks"
72
73 /** log2 block data address length (64k) */
74 #define BLOCK_ADDR_LEN 16
75
76 /** log2 number of entries per block file(1024) */
77 #define BLOCK_ENTRY_COUNT 10
78
79 /** log2 number of data block files */
80 #define BLOCK_FILE_COUNT (BLOCK_ADDR_LEN - BLOCK_ENTRY_COUNT)
81
82 /** log2 size of data blocks (8k) */
83 #define BLOCK_DATA_SIZE 13
84
85 /** log2 size of metadata blocks (8k) */
86 #define BLOCK_META_SIZE 13
87
88 /** length in bytes of a block files use map */
89 #define BLOCK_USE_MAP_SIZE (1 << (BLOCK_ENTRY_COUNT - 3))
90
91 /**
92 * The type used to store index values referring to store entries. Care
93 * must be taken with this type as it is used to build address to
94 * entry mapping so changing the size will have large impacts on
95 * memory usage.
96 */
97 typedef uint16_t entry_index_t;
98
99 /**
100 * The type used as a binary identifier for each entry derived from
101 * the URL. A larger identifier will have fewer collisions but
102 * requires proportionately more storage.
103 */
104 typedef uint32_t entry_ident_t;
105
106 /**
107 * The type used to store block file index values. If this is changed
108 * it will affect the entry storage/alignment and BLOCK_ADDR_LEN must
109 * also be updated.
110 */
111 typedef uint16_t block_index_t;
112
113
114 /**
115 * Entry element index values.
116 */
117 enum store_entry_elem_idx {
118 ENTRY_ELEM_DATA = 0, /**< entry element is data */
119 ENTRY_ELEM_META = 1, /**< entry element is metadata */
120 ENTRY_ELEM_COUNT = 2, /**< count of elements on an entry */
121 };
122
123 /**
124 * flags that indicate what additional information is contained within
125 * an entry element.
126 */
127 enum store_entry_elem_flags {
128 /** store not managing any allocation on entry */
129 ENTRY_ELEM_FLAG_NONE = 0,
130 /** entry data allocation is on heap */
131 ENTRY_ELEM_FLAG_HEAP = 0x1,
132 /** entry data allocation is mmaped */
133 ENTRY_ELEM_FLAG_MMAP = 0x2,
134 /** entry data allocation is in small object pool */
135 ENTRY_ELEM_FLAG_SMALL = 0x4,
136 };
137
138
139 enum store_entry_flags {
140 /** entry is normal */
141 ENTRY_FLAGS_NONE = 0,
142 /** entry has been invalidated but something still holding a reference */
143 ENTRY_FLAGS_INVALID = 1,
144 };
145
146 /**
147 * Backing store entry element.
148 *
149 * An element keeps data about:
150 * - the current memory allocation
151 * - the number of outstanding references to the memory
152 * - the size of the element data
153 * - flags controlling how the memory and element are handled
154 *
155 * @note Order is important to avoid excessive structure packing overhead.
156 */
157 struct store_entry_element {
158 uint8_t* data; /**< data allocated */
159 uint32_t size; /**< size of entry element on disc */
160 block_index_t block; /**< small object data block */
161 uint8_t ref; /**< element data reference count */
162 uint8_t flags; /**< entry flags */
163 };
164
165 /**
166 * Backing store object index entry.
167 *
168 * An entry in the backing store contains two elements for the actual
169 * data and the metadata. The two elements are treated identically for
170 * storage lifetime but as a collective whole for expiration and
171 * indexing.
172 *
173 * @note Order is important to avoid excessive structure packing overhead.
174 */
175 struct store_entry {
176 nsurl *url; /**< The URL for this entry */
177 int64_t last_used; /**< UNIX time the entry was last used */
178 uint16_t use_count; /**< number of times this entry has been accessed */
179 uint8_t flags; /**< entry flags */
180 /** Entry element (data or meta) specific information */
181 struct store_entry_element elem[ENTRY_ELEM_COUNT];
182 };
183
184 /**
185 * Small block file.
186 */
187 struct block_file {
188 /** file descriptor of the block file */
189 int fd;
190 /** map of used and unused entries within the block file */
191 uint8_t use_map[BLOCK_USE_MAP_SIZE];
192 };
193
194 /**
195 * log2 of block size.
196 */
197 static const unsigned int log2_block_size[ENTRY_ELEM_COUNT] = {
198 BLOCK_DATA_SIZE, /**< Data block size */
199 BLOCK_META_SIZE /**< Metadata block size */
200 };
201
202 /**
203 * Parameters controlling the backing store.
204 */
205 struct store_state {
206 /* store config */
207 char *path; /**< The path to the backing store */
208 size_t limit; /**< The backing store upper bound target size */
209 size_t hysteresis; /**< The hysteresis around the target size */
210
211 /**
212 * The cache object hash
213 */
214 hashmap_t *entries;
215
216 /** flag indicating if the entries have been made persistent
217 * since they were last changed.
218 */
219 bool entries_dirty;
220
221 /** small block indexes */
222 struct block_file blocks[ENTRY_ELEM_COUNT][BLOCK_FILE_COUNT];
223
224 /** flag indicating if the block file use maps have been made
225 * persistent since they were last changed.
226 */
227 bool blocks_dirty;
228
229 /** flag indicating if a block file has been opened for update
230 * since maintenance was previously done.
231 */
232 bool blocks_opened;
233
234
235 /* stats */
236 uint64_t total_alloc; /**< total size of all allocated storage. */
237
238 size_t hit_count; /**< number of cache hits */
239 uint64_t hit_size; /**< size of storage served */
240 size_t miss_count; /**< number of cache misses */
241
242 };
243
244 /**
245 * Global storage state.
246 *
247 * @todo Investigate if there is a way to have a context rather than
248 * use a global.
249 */
250 struct store_state *storestate;
251
252 /* Entries hashmap parameters
253 *
254 * Our hashmap has nsurl keys and store_entry values
255 */
256
257 static bool
entries_hashmap_key_eq(void * key1,void * key2)258 entries_hashmap_key_eq(void *key1, void *key2)
259 {
260 return nsurl_compare((nsurl *)key1, (nsurl *)key2, NSURL_COMPLETE);
261 }
262
263 static void *
entries_hashmap_value_alloc(void * key)264 entries_hashmap_value_alloc(void *key)
265 {
266 struct store_entry *ent = calloc(1, sizeof(struct store_entry));
267 if (ent != NULL) {
268 ent->url = nsurl_ref(key);
269 }
270 return ent;
271 }
272
273 static void
entries_hashmap_value_destroy(void * value)274 entries_hashmap_value_destroy(void *value)
275 {
276 struct store_entry *ent = value;
277 /** \todo Do we need to do any disk cleanup here? if so, meep! */
278 nsurl_unref(ent->url);
279 free(ent);
280 }
281
282 static hashmap_parameters_t entries_hashmap_parameters = {
283 .key_clone = (hashmap_key_clone_t)nsurl_ref,
284 .key_destroy = (hashmap_key_destroy_t)nsurl_unref,
285 .key_hash = (hashmap_key_hash_t)nsurl_hash,
286 .key_eq = entries_hashmap_key_eq,
287 .value_alloc = entries_hashmap_value_alloc,
288 .value_destroy = entries_hashmap_value_destroy,
289 };
290
291 /**
292 * Generate a filename for an object.
293 *
294 * this generates the filename for an object on disc. It is necessary
295 * for this to generate a filename which conforms to the limitations
296 * of all the filesystems the cache can be placed upon.
297 *
298 * From http://en.wikipedia.org/wiki/Comparison_of_file_systems#Limits
299 * the relevant subset is:
300 * - path elements no longer than 8 characters
301 * - acceptable characters are A-Z, 0-9
302 * - short total path lengths (255 or less)
303 * - no more than 77 entries per directory (6bits worth)
304 *
305 * The short total path lengths mean the encoding must represent as
306 * much data as possible in the least number of characters.
307 *
308 * To achieve all these goals we use RFC4648 base32 encoding which
309 * packs 5bits into each character of the filename. To represent a 32
310 * bit ident this requires a total path length of between 17 and 22
311 * bytes (including directory separators) BA/BB/BC/BD/BE/ABCDEFG
312 *
313 * @note Version 1.00 of the cache implementation used base64 to
314 * encode this, however that did not meet the requirement for only
315 * using uppercase characters.
316 *
317 * @note Versions prior to 1.30 only packed 5 bits per directory level
318 * A/B/C/D/E/F/ABCDEFG which only required 19 characters to represent
319 * but resulted in requiring an extra level of directory which is less
320 * desirable than the three extra characters using six bits.
321 *
322 * @param state The store state to use.
323 * @param ident The identifier to use.
324 * @param elem_idx The element index.
325 * @return The filename string or NULL on allocation error.
326 */
327 static char *
store_fname(struct store_state * state,entry_ident_t ident,int elem_idx)328 store_fname(struct store_state *state,
329 entry_ident_t ident,
330 int elem_idx)
331 {
332 char *fname = NULL;
333 uint8_t b32u_i[8]; /* base32 encoded ident */
334 const uint8_t *b32u_d[6]; /* base32 ident as separate components */
335
336 /* directories used to separate elements */
337 const char *base_dir_table[] = {
338 "d", "m", "dblk", "mblk"
339 };
340
341 /* RFC4648 base32 encoding table (six bits) */
342 const uint8_t encoding_table[64][3] = {
343 { 'A', 0, 0 }, { 'B', 0, 0 }, /* 0 */
344 { 'C', 0, 0 }, { 'D', 0, 0 }, /* 2 */
345 { 'E', 0, 0 }, { 'F', 0, 0 }, /* 4 */
346 { 'G', 0, 0 }, { 'H', 0, 0 }, /* 6 */
347 { 'I', 0, 0 }, { 'J', 0, 0 }, /* 8 */
348 { 'K', 0, 0 }, { 'L', 0, 0 }, /* 10 */
349 { 'M', 0, 0 }, { 'N', 0, 0 }, /* 12 */
350 { 'O', 0, 0 }, { 'P', 0, 0 }, /* 14 */
351 { 'Q', 0, 0 }, { 'R', 0, 0 }, /* 16 */
352 { 'S', 0, 0 }, { 'T', 0, 0 }, /* 18 */
353 { 'U', 0, 0 }, { 'V', 0, 0 }, /* 20 */
354 { 'W', 0, 0 }, { 'X', 0, 0 }, /* 22 */
355 { 'Y', 0, 0 }, { 'Z', 0, 0 }, /* 24 */
356 { '2', 0, 0 }, { '3', 0, 0 }, /* 26 */
357 { '4', 0, 0 }, { '5', 0, 0 }, /* 28 */
358 { '6', 0, 0 }, { '7', 0, 0 }, /* 30 */
359 { 'B', 'A', 0 }, { 'B', 'B', 0 }, /* 32 */
360 { 'B', 'C', 0 }, { 'B', 'D', 0 }, /* 34 */
361 { 'B', 'E', 0 }, { 'B', 'F', 0 }, /* 36 */
362 { 'B', 'G', 0 }, { 'B', 'H', 0 }, /* 38 */
363 { 'B', 'I', 0 }, { 'B', 'J', 0 }, /* 40 */
364 { 'B', 'K', 0 }, { 'B', 'L', 0 }, /* 42 */
365 { 'B', 'M', 0 }, { 'B', 'N', 0 }, /* 44 */
366 { 'B', 'O', 0 }, { 'B', 'P', 0 }, /* 46 */
367 { 'B', 'Q', 0 }, { 'B', 'R', 0 }, /* 48 */
368 { 'B', 'S', 0 }, { 'B', 'T', 0 }, /* 50 */
369 { 'B', 'U', 0 }, { 'B', 'V', 0 }, /* 52 */
370 { 'B', 'W', 0 }, { 'B', 'X', 0 }, /* 54 */
371 { 'B', 'Y', 0 }, { 'B', 'Z', 0 }, /* 56 */
372 { 'B', '2', 0 }, { 'B', '3', 0 }, /* 58 */
373 { 'B', '4', 0 }, { 'B', '5', 0 }, /* 60 */
374 { 'B', '6', 0 }, { 'B', '7', 0 } /* 62 */
375 };
376
377 /* base32 encode ident */
378 b32u_i[0] = encoding_table[(ident ) & 0x1f][0];
379 b32u_i[1] = encoding_table[(ident >> 5) & 0x1f][0];
380 b32u_i[2] = encoding_table[(ident >> 10) & 0x1f][0];
381 b32u_i[3] = encoding_table[(ident >> 15) & 0x1f][0];
382 b32u_i[4] = encoding_table[(ident >> 20) & 0x1f][0];
383 b32u_i[5] = encoding_table[(ident >> 25) & 0x1f][0];
384 b32u_i[6] = encoding_table[(ident >> 30) & 0x1f][0];
385 b32u_i[7] = 0; /* null terminate ident string */
386
387 /* base32 encode directory separators */
388 b32u_d[0] = (uint8_t*)base_dir_table[elem_idx];
389 b32u_d[1] = &encoding_table[(ident ) & 0x3f][0];
390 b32u_d[2] = &encoding_table[(ident >> 6) & 0x3f][0];
391 b32u_d[3] = &encoding_table[(ident >> 12) & 0x3f][0];
392 b32u_d[4] = &encoding_table[(ident >> 18) & 0x3f][0];
393 b32u_d[5] = &encoding_table[(ident >> 24) & 0x3f][0];
394
395 switch (elem_idx) {
396 case ENTRY_ELEM_DATA:
397 case ENTRY_ELEM_META:
398 netsurf_mkpath(&fname, NULL, 8,
399 state->path, b32u_d[0], b32u_d[1], b32u_d[2],
400 b32u_d[3], b32u_d[4], b32u_d[5], b32u_i);
401 break;
402
403 case (ENTRY_ELEM_COUNT + ENTRY_ELEM_META):
404 case (ENTRY_ELEM_COUNT + ENTRY_ELEM_DATA):
405 netsurf_mkpath(&fname, NULL, 3,
406 state->path, b32u_d[0], b32u_d[1]);
407 break;
408
409 default:
410 assert("bad element index" == NULL);
411 break;
412 }
413
414 return fname;
415 }
416
417 /**
418 * invalidate an element of an entry
419 *
420 * @param state The store state to use.
421 * @param bse The entry to invalidate.
422 * @param elem_idx The element index to invalidate.
423 * @return NSERROR_OK on success or error code on failure.
424 */
425 static nserror
invalidate_element(struct store_state * state,struct store_entry * bse,int elem_idx)426 invalidate_element(struct store_state *state,
427 struct store_entry *bse,
428 int elem_idx)
429 {
430 if (bse->elem[elem_idx].block != 0) {
431 block_index_t bf;
432 block_index_t bi;
433
434 /* block file block resides in */
435 bf = (bse->elem[elem_idx].block >> BLOCK_ENTRY_COUNT) &
436 ((1 << BLOCK_FILE_COUNT) - 1);
437
438 /* block index in file */
439 bi = bse->elem[elem_idx].block & ((1U << BLOCK_ENTRY_COUNT) -1);
440
441 /* clear bit in use map */
442 state->blocks[elem_idx][bf].use_map[bi >> 3] &= ~(1U << (bi & 7));
443 } else {
444 char *fname;
445
446 /* unlink the file from disc */
447 fname = store_fname(state, nsurl_hash(bse->url), elem_idx);
448 if (fname == NULL) {
449 return NSERROR_NOMEM;
450 }
451 unlink(fname);
452 free(fname);
453 }
454
455 state->total_alloc -= bse->elem[elem_idx].size;
456
457 return NSERROR_OK;
458 }
459
460 /**
461 * Remove the entry and files associated with an identifier.
462 *
463 * @param state The store state to use.
464 * @param bse The entry to invalidate.
465 * @return NSERROR_OK on success or error code on failure.
466 */
467 static nserror
invalidate_entry(struct store_state * state,struct store_entry * bse)468 invalidate_entry(struct store_state *state, struct store_entry *bse)
469 {
470 nserror ret;
471
472 /* mark entry as invalid */
473 bse->flags |= ENTRY_FLAGS_INVALID;
474
475 /* check if the entry has storage already allocated */
476 if (((bse->elem[ENTRY_ELEM_DATA].flags &
477 (ENTRY_ELEM_FLAG_HEAP | ENTRY_ELEM_FLAG_MMAP)) != 0) ||
478 ((bse->elem[ENTRY_ELEM_META].flags &
479 (ENTRY_ELEM_FLAG_HEAP | ENTRY_ELEM_FLAG_MMAP)) != 0)) {
480 /*
481 * This entry cannot be immediately removed as it has
482 * associated allocation so wait for allocation release.
483 */
484 NSLOG(netsurf, DEBUG,
485 "invalidating entry with referenced allocation");
486 return NSERROR_OK;
487 }
488
489 NSLOG(netsurf, VERBOSE, "Removing entry for %s", nsurl_access(bse->url));
490
491 ret = invalidate_element(state, bse, ENTRY_ELEM_META);
492 if (ret != NSERROR_OK) {
493 NSLOG(netsurf, ERROR, "Error invalidating metadata element");
494 }
495
496 ret = invalidate_element(state, bse, ENTRY_ELEM_DATA);
497 if (ret != NSERROR_OK) {
498 NSLOG(netsurf, ERROR, "Error invalidating data element");
499 }
500
501 /* As our final act we remove bse from the cache */
502 hashmap_remove(state->entries, bse->url);
503 /* From now, bse is invalid memory */
504
505 return NSERROR_OK;
506 }
507
508
509 /**
510 * Quick sort comparison.
511 */
compar(const void * va,const void * vb)512 static int compar(const void *va, const void *vb)
513 {
514 const struct store_entry *a = *(const struct store_entry **)va;
515 const struct store_entry *b = *(const struct store_entry **)vb;
516
517 /* consider the allocation flags - if an entry has an
518 * allocation it is considered more valuable as it cannot be
519 * freed.
520 */
521 if ((a->elem[ENTRY_ELEM_DATA].flags == ENTRY_ELEM_FLAG_NONE) &&
522 (b->elem[ENTRY_ELEM_DATA].flags != ENTRY_ELEM_FLAG_NONE)) {
523 return -1;
524 } else if ((a->elem[ENTRY_ELEM_DATA].flags != ENTRY_ELEM_FLAG_NONE) &&
525 (b->elem[ENTRY_ELEM_DATA].flags == ENTRY_ELEM_FLAG_NONE)) {
526 return 1;
527 }
528
529 if ((a->elem[ENTRY_ELEM_META].flags == ENTRY_ELEM_FLAG_NONE) &&
530 (b->elem[ENTRY_ELEM_META].flags != ENTRY_ELEM_FLAG_NONE)) {
531 return -1;
532 } else if ((a->elem[ENTRY_ELEM_META].flags != ENTRY_ELEM_FLAG_NONE) &&
533 (b->elem[ENTRY_ELEM_META].flags == ENTRY_ELEM_FLAG_NONE)) {
534 return 1;
535 }
536
537 if (a->use_count < b->use_count) {
538 return -1;
539 } else if (a->use_count > b->use_count) {
540 return 1;
541 }
542 /* use count is the same - now consider last use time */
543
544 if (a->last_used < b->last_used) {
545 return -1;
546 } else if (a->last_used > b->last_used) {
547 return 1;
548 }
549
550 /* they are the same */
551 return 0;
552 }
553
554 typedef struct {
555 struct store_entry **elist;
556 size_t ent_count;
557 } eviction_state_t;
558
559 /**
560 * Iterator for gathering entries to compute eviction order
561 */
562 static bool
entry_eviction_iterator_cb(void * key,void * value,void * ctx)563 entry_eviction_iterator_cb(void *key, void *value, void *ctx)
564 {
565 eviction_state_t *estate = ctx;
566 struct store_entry *ent = value;
567 estate->elist[estate->ent_count++] = ent;
568 return false;
569 }
570
571 /**
572 * Evict entries from backing store as per configuration.
573 *
574 * Entries are evicted to ensure the cache remains within the
575 * configured limits on size and number of entries.
576 *
577 * The approach is to check if the cache limits have been exceeded and
578 * if so build and sort list of entries to evict. The list is sorted
579 * by use count and then by age, so oldest object with least number of uses
580 * get evicted first.
581 *
582 * @param state The store state to use.
583 * @return NSERROR_OK on success or error code on failure.
584 */
store_evict(struct store_state * state)585 static nserror store_evict(struct store_state *state)
586 {
587 size_t ent = 0;
588 size_t removed = 0; /* size of removed entries */
589 nserror ret = NSERROR_OK;
590 size_t old_count;
591 eviction_state_t estate;
592
593 /* check if the cache has exceeded configured limit */
594 if (state->total_alloc < state->limit) {
595 /* cache within limits */
596 return NSERROR_OK;
597 }
598
599 NSLOG(netsurf, INFO,
600 "Evicting entries to reduce %"PRIu64" by %"PRIsizet,
601 state->total_alloc,
602 state->hysteresis);
603
604 /* allocate storage for the list */
605 old_count = hashmap_count(state->entries);
606 estate.ent_count = 0;
607 estate.elist = malloc(sizeof(struct state_entry*) * old_count);
608 if (estate.elist == NULL) {
609 return NSERROR_NOMEM;
610 }
611
612 if (hashmap_iterate(state->entries, entry_eviction_iterator_cb, &estate)) {
613 NSLOG(netsurf, WARNING, "Unexpected termination of eviction iterator");
614 free(estate.elist);
615 return NSERROR_UNKNOWN;
616 }
617
618 if (old_count != estate.ent_count) {
619 NSLOG(netsurf, WARNING, "Incorrect entry count after eviction iterator");
620 free(estate.elist);
621 return NSERROR_UNKNOWN;
622 }
623
624 qsort(estate.elist, estate.ent_count, sizeof(struct state_entry*), compar);
625
626 /* evict entries in listed order */
627 removed = 0;
628 for (ent = 0; ent < estate.ent_count; ent++) {
629 struct store_entry *bse = estate.elist[ent];
630
631 removed += bse->elem[ENTRY_ELEM_DATA].size;
632 removed += bse->elem[ENTRY_ELEM_META].size;
633
634 ret = invalidate_entry(state, bse);
635 if (ret != NSERROR_OK) {
636 break;
637 }
638
639 if (removed > state->hysteresis) {
640 break;
641 }
642 }
643
644 free(estate.elist);
645
646 NSLOG(netsurf, INFO,
647 "removed %"PRIsizet" in %"PRIsizet" entries, %"PRIu64" remaining in %"PRIsizet" entries",
648 removed, ent, state->total_alloc, old_count - ent);
649
650 return ret;
651 }
652
653 /**
654 * Write a single store entry to disk
655 *
656 * To serialise a single store entry for now we write out a 32bit int
657 * which is the length of the url, then that many bytes of the url.
658 * Then we write out the full store entry struct as-is, which includes
659 * a useless nsurl pointer.
660 */
661 static nserror
write_entry(struct store_entry * ent,int fd)662 write_entry(struct store_entry *ent, int fd)
663 {
664 uint32_t len = strlen(nsurl_access(ent->url));
665 if (write(fd, &len, sizeof(len)) != sizeof(len))
666 return NSERROR_SAVE_FAILED;
667 if (write(fd, nsurl_access(ent->url), len) != (ssize_t)len)
668 return NSERROR_SAVE_FAILED;
669 if (write(fd, ent, sizeof(*ent)) != sizeof(*ent))
670 return NSERROR_SAVE_FAILED;
671
672 return NSERROR_OK;
673 }
674
675 typedef struct {
676 int fd;
677 size_t written;
678 } write_entry_iteration_state;
679
680 /**
681 * Callback for iterating the entries hashmap
682 */
683 static bool
write_entry_iterator(void * key,void * value,void * ctx)684 write_entry_iterator(void *key, void *value, void *ctx)
685 {
686 /* We ignore the key */
687 struct store_entry *ent = value;
688 write_entry_iteration_state *state = ctx;
689 state->written++;
690 /* We stop early if we fail to write this entry */
691 return write_entry(ent, state->fd) != NSERROR_OK;
692 }
693
694 /**
695 * Write filesystem entries to file.
696 *
697 * Serialise entry index out to storage.
698 *
699 * @param state The backing store state to serialise.
700 * @return NSERROR_OK on success or error code on failure.
701 */
write_entries(struct store_state * state)702 static nserror write_entries(struct store_state *state)
703 {
704 char *tname = NULL; /* temporary file name for atomic replace */
705 char *fname = NULL; /* target filename */
706 write_entry_iteration_state weistate;
707 nserror ret;
708
709 memset(&weistate, 0, sizeof(weistate));
710
711 if (state->entries_dirty == false) {
712 /* entries have not been updated since last write */
713 return NSERROR_OK;
714 }
715
716 ret = netsurf_mkpath(&tname, NULL, 2, state->path, "t"ENTRIES_FNAME);
717 if (ret != NSERROR_OK) {
718 return ret;
719 }
720
721 weistate.fd = open(tname, O_RDWR | O_CREAT | O_TRUNC, S_IRUSR | S_IWUSR);
722 if (weistate.fd == -1) {
723 free(tname);
724 return NSERROR_SAVE_FAILED;
725 }
726
727 if (hashmap_iterate(state->entries, write_entry_iterator, &weistate)) {
728 /* The iteration ended early, so we failed */
729 close(weistate.fd);
730 unlink(tname);
731 free(tname);
732 return NSERROR_SAVE_FAILED;
733 }
734
735 close(weistate.fd);
736
737 ret = netsurf_mkpath(&fname, NULL, 2, state->path, ENTRIES_FNAME);
738 if (ret != NSERROR_OK) {
739 unlink(tname);
740 free(tname);
741 return ret;
742 }
743
744 /* remove() call is to handle non-POSIX rename() implementations */
745 (void)remove(fname);
746 if (rename(tname, fname) != 0) {
747 unlink(tname);
748 free(tname);
749 free(fname);
750 return NSERROR_SAVE_FAILED;
751 }
752
753 NSLOG(netsurf, INFO, "Wrote out %"PRIsizet" entries", weistate.written);
754
755 return NSERROR_OK;
756 }
757
758 /**
759 * Write block file use map to file.
760 *
761 * Serialise block file use map out to storage.
762 *
763 * \param state The backing store state to serialise.
764 * \return NSERROR_OK on success or error code on failure.
765 */
write_blocks(struct store_state * state)766 static nserror write_blocks(struct store_state *state)
767 {
768 int fd;
769 char *tname = NULL; /* temporary file name for atomic replace */
770 char *fname = NULL; /* target filename */
771 size_t blocks_size;
772 size_t written = 0;
773 size_t wr;
774 nserror ret;
775 int bfidx; /* block file index */
776 int elem_idx;
777
778 if (state->blocks_dirty == false) {
779 /* blocks use maps have not been updated since last write */
780 return NSERROR_OK;
781 }
782
783 ret = netsurf_mkpath(&tname, NULL, 2, state->path, "t"BLOCKS_FNAME);
784 if (ret != NSERROR_OK) {
785 return ret;
786 }
787
788 fd = open(tname, O_RDWR | O_CREAT | O_TRUNC, S_IRUSR | S_IWUSR);
789 if (fd == -1) {
790 free(tname);
791 return NSERROR_SAVE_FAILED;
792 }
793
794 blocks_size = (BLOCK_FILE_COUNT * ENTRY_ELEM_COUNT) * BLOCK_USE_MAP_SIZE;
795
796 for (elem_idx = 0; elem_idx < ENTRY_ELEM_COUNT; elem_idx++) {
797 for (bfidx = 0; bfidx < BLOCK_FILE_COUNT; bfidx++) {
798 wr = write(fd,
799 &state->blocks[elem_idx][bfidx].use_map[0],
800 BLOCK_USE_MAP_SIZE);
801 if (wr != BLOCK_USE_MAP_SIZE) {
802 NSLOG(netsurf, DEBUG,
803 "writing block file %d use index on file number %d failed",
804 elem_idx,
805 bfidx);
806 goto wr_err;
807 }
808 written += wr;
809 }
810 }
811 wr_err:
812 close(fd);
813
814 /* check all data was written */
815 if (written != blocks_size) {
816 unlink(tname);
817 free(tname);
818 return NSERROR_SAVE_FAILED;
819 }
820
821 ret = netsurf_mkpath(&fname, NULL, 2, state->path, BLOCKS_FNAME);
822 if (ret != NSERROR_OK) {
823 unlink(tname);
824 free(tname);
825 return ret;
826 }
827
828 /* remove() call is to handle non-POSIX rename() implementations */
829 (void)remove(fname);
830 if (rename(tname, fname) != 0) {
831 unlink(tname);
832 free(tname);
833 free(fname);
834 return NSERROR_SAVE_FAILED;
835 }
836
837 return NSERROR_OK;
838 }
839
840 /**
841 * Ensures block files are of the correct extent
842 *
843 * block files have their extent set to their maximum size to ensure
844 * subsequent reads and writes do not need to extend the file and are
845 * therefore faster.
846 *
847 * \param state The backing store state to set block extent for.
848 * \return NSERROR_OK on success or error code on failure.
849 */
set_block_extents(struct store_state * state)850 static nserror set_block_extents(struct store_state *state)
851 {
852 int bfidx; /* block file index */
853 int elem_idx;
854 int ftr;
855
856 if (state->blocks_opened == false) {
857 /* no blocks have been opened since last write */
858 return NSERROR_OK;
859 }
860
861 NSLOG(netsurf, DEBUG, "Starting");
862 for (elem_idx = 0; elem_idx < ENTRY_ELEM_COUNT; elem_idx++) {
863 for (bfidx = 0; bfidx < BLOCK_FILE_COUNT; bfidx++) {
864 if (state->blocks[elem_idx][bfidx].fd != -1) {
865 /* ensure block file is correct extent */
866 ftr = ftruncate(state->blocks[elem_idx][bfidx].fd, 1U << (log2_block_size[elem_idx] + BLOCK_ENTRY_COUNT));
867 if (ftr == -1) {
868 NSLOG(netsurf, ERROR,
869 "Truncate failed errno:%d",
870 errno);
871 }
872 }
873 }
874 }
875 NSLOG(netsurf, DEBUG, "Complete");
876
877 state->blocks_opened = false;
878
879 return NSERROR_OK;
880 }
881
882 /**
883 * maintenance of control structures.
884 *
885 * callback scheduled when control data has been update. Currently
886 * this is for when the entries table is dirty and requires
887 * serialising.
888 *
889 * \param s store state to maintain.
890 */
control_maintenance(void * s)891 static void control_maintenance(void *s)
892 {
893 struct store_state *state = s;
894
895 write_entries(state);
896 write_blocks(state);
897 set_block_extents(state);
898 }
899
900
901 /**
902 * Lookup a backing store entry in the entry table from a url.
903 *
904 * This finds the store entry associated with the given
905 * key. Additionally if an entry is found it updates the usage data
906 * about the entry.
907 *
908 * @param state The store state to use.
909 * @param url The value used as the unique key to search entries for.
910 * @param bse Pointer used to return value.
911 * @return NSERROR_OK and bse updated on success or NSERROR_NOT_FOUND
912 * if no entry corresponds to the url.
913 */
914 static nserror
get_store_entry(struct store_state * state,nsurl * url,struct store_entry ** bse)915 get_store_entry(struct store_state *state, nsurl *url, struct store_entry **bse)
916 {
917 struct store_entry *ent;
918
919 ent = hashmap_lookup(state->entries, url);
920
921 if (ent == NULL) {
922 return NSERROR_NOT_FOUND;
923 }
924
925 *bse = ent;
926
927 ent->last_used = time(NULL);
928 ent->use_count++;
929
930 state->entries_dirty = true;
931
932 guit->misc->schedule(CONTROL_MAINT_TIME, control_maintenance, state);
933
934 return NSERROR_OK;
935 }
936
937 /**
938 * Find next available small block.
939 */
alloc_block(struct store_state * state,int elem_idx)940 static block_index_t alloc_block(struct store_state *state, int elem_idx)
941 {
942 int bf;
943 int idx;
944 int bit;
945 uint8_t *map;
946
947 for (bf = 0; bf < BLOCK_FILE_COUNT; bf++) {
948 map = &state->blocks[elem_idx][bf].use_map[0];
949
950 for (idx = 0; idx < BLOCK_USE_MAP_SIZE; idx++) {
951 if (*(map + idx) != 0xff) {
952 /* located an unused block */
953 for (bit = 0; bit < 8;bit++) {
954 if (((*(map + idx)) & (1U << bit)) == 0) {
955 /* mark block as used */
956 *(map + idx) |= 1U << bit;
957 state->blocks_dirty = true;
958 return (((bf * BLOCK_USE_MAP_SIZE) + idx) * 8) + bit;
959 }
960 }
961 }
962 }
963 }
964
965 return 0;
966 }
967
968 /**
969 * Set a backing store entry in the entry table from a url.
970 *
971 * This creates a backing store entry in the entry table for a url.
972 *
973 * @param state The store state to use.
974 * @param url The value used as the unique key to search entries for.
975 * @param elem_idx The index of the entry element to use.
976 * @param data The data to store
977 * @param datalen The length of data in \a data
978 * @param bse Pointer used to return value.
979 * @return NSERROR_OK and \a bse updated on success or NSERROR_NOT_FOUND
980 * if no entry corresponds to the url.
981 */
982 static nserror
set_store_entry(struct store_state * state,nsurl * url,int elem_idx,uint8_t * data,const size_t datalen,struct store_entry ** bse)983 set_store_entry(struct store_state *state,
984 nsurl *url,
985 int elem_idx,
986 uint8_t *data,
987 const size_t datalen,
988 struct store_entry **bse)
989 {
990 struct store_entry *se;
991 nserror ret;
992 struct store_entry_element *elem;
993
994 NSLOG(netsurf, DEBUG, "url:%s", nsurl_access(url));
995
996 /* evict entries as required and ensure there is at least one
997 * new entry available.
998 */
999 ret = store_evict(state);
1000 if (ret != NSERROR_OK) {
1001 return ret;
1002 }
1003
1004 se = hashmap_lookup(state->entries, url);
1005 if (se == NULL) {
1006 se = hashmap_insert(state->entries, url);
1007 }
1008 if (se == NULL) {
1009 return NSERROR_NOMEM;
1010 }
1011
1012 /* the entry element */
1013 elem = &se->elem[elem_idx];
1014
1015 /* check if the element has storage already allocated */
1016 if ((elem->flags & (ENTRY_ELEM_FLAG_HEAP | ENTRY_ELEM_FLAG_MMAP)) != 0) {
1017 /* this entry cannot be removed as it has associated
1018 * allocation.
1019 */
1020 NSLOG(netsurf, ERROR,
1021 "attempt to overwrite entry with in use data");
1022 return NSERROR_PERMISSION;
1023 }
1024
1025 /* set the common entry data */
1026 se->use_count = 1;
1027 se->last_used = time(NULL);
1028
1029 /* store the data in the element */
1030 elem->flags |= ENTRY_ELEM_FLAG_HEAP;
1031 elem->data = data;
1032 elem->ref = 1;
1033
1034 /* account for size of entry element */
1035 state->total_alloc -= elem->size;
1036 elem->size = datalen;
1037 state->total_alloc += elem->size;
1038
1039 /* if the element will fit in a small block attempt to allocate one */
1040 if (elem->size <= (1U << log2_block_size[elem_idx])) {
1041 elem->block = alloc_block(state, elem_idx);
1042 }
1043
1044 /* ensure control maintenance scheduled. */
1045 state->entries_dirty = true;
1046 guit->misc->schedule(CONTROL_MAINT_TIME, control_maintenance, state);
1047
1048 *bse = se;
1049
1050 return NSERROR_OK;
1051 }
1052
1053
1054 /**
1055 * Open a file using a store ident.
1056 *
1057 * @param state The store state to use.
1058 * @param ident The identifier to open file for.
1059 * @param elem_idx The element within the store entry to open. The
1060 * value should be be one of the values in the
1061 * store_entry_elem_idx enum. Additionally it may have
1062 * ENTRY_ELEM_COUNT added to it to indicate block file
1063 * names.
1064 * @param openflags The flags used with the open call.
1065 * @return An fd from the open call or -1 on error.
1066 */
1067 static int
store_open(struct store_state * state,entry_ident_t ident,int elem_idx,int openflags)1068 store_open(struct store_state *state,
1069 entry_ident_t ident,
1070 int elem_idx,
1071 int openflags)
1072 {
1073 char *fname;
1074 nserror ret;
1075 int fd;
1076
1077 fname = store_fname(state, ident, elem_idx);
1078 if (fname == NULL) {
1079 NSLOG(netsurf, ERROR, "filename error");
1080 return -1;
1081 }
1082
1083 /* ensure all path elements to file exist if creating file */
1084 if (openflags & O_CREAT) {
1085 ret = netsurf_mkdir_all(fname);
1086 if (ret != NSERROR_OK) {
1087 NSLOG(netsurf, WARNING,
1088 "file path \"%s\" could not be created", fname);
1089 free(fname);
1090 return -1;
1091 }
1092 }
1093
1094 NSLOG(netsurf, DEBUG, "opening %s", fname);
1095 fd = open(fname, openflags, S_IRUSR | S_IWUSR);
1096
1097 free(fname);
1098
1099 return fd;
1100 }
1101
1102
1103 /**
1104 * Unlink entries file
1105 *
1106 * @param state The backing store state.
1107 * @return NSERROR_OK on success or error code on failure.
1108 */
1109 static nserror
unlink_entries(struct store_state * state)1110 unlink_entries(struct store_state *state)
1111 {
1112 char *fname = NULL;
1113 nserror ret;
1114
1115 ret = netsurf_mkpath(&fname, NULL, 2, state->path, ENTRIES_FNAME);
1116 if (ret != NSERROR_OK) {
1117 return ret;
1118 }
1119
1120 unlink(fname);
1121
1122 free(fname);
1123 return NSERROR_OK;
1124 }
1125
1126 /**
1127 * Read description entries into memory.
1128 *
1129 * @param state The backing store state to put the loaded entries in.
1130 * @return NSERROR_OK on success or error code on faliure.
1131 */
1132 static nserror
read_entries(struct store_state * state)1133 read_entries(struct store_state *state)
1134 {
1135 char *fname = NULL;
1136 char *url;
1137 nsurl *nsurl;
1138 nserror ret;
1139 size_t read_entries = 0;
1140 struct store_entry *ent;
1141 int fd;
1142
1143 ret = netsurf_mkpath(&fname, NULL, 2, state->path, ENTRIES_FNAME);
1144 if (ret != NSERROR_OK) {
1145 return ret;
1146 }
1147
1148 state->entries = hashmap_create(&entries_hashmap_parameters);
1149 if (state->entries == NULL) {
1150 free(fname);
1151 return NSERROR_NOMEM;
1152 }
1153
1154 fd = open(fname, O_RDWR);
1155 if (fd != -1) {
1156 uint32_t urllen;
1157 while (read(fd, &urllen, sizeof(urllen)) == sizeof(urllen)) {
1158 url = calloc(1, urllen+1);
1159 if (url == NULL) {
1160 close(fd);
1161 free(fname);
1162 return NSERROR_NOMEM;
1163 }
1164 if (read(fd, url, urllen) != (ssize_t)urllen) {
1165 free(url);
1166 close(fd);
1167 free(fname);
1168 return NSERROR_INIT_FAILED;
1169 }
1170 ret = nsurl_create(url, &nsurl);
1171 if (ret != NSERROR_OK) {
1172 free(url);
1173 close(fd);
1174 free(fname);
1175 return ret;
1176 }
1177 free(url);
1178 /* We have to be careful here about nsurl refs */
1179 ent = hashmap_insert(state->entries, nsurl);
1180 if (ent == NULL) {
1181 nsurl_unref(nsurl);
1182 close(fd);
1183 free(fname);
1184 return NSERROR_NOMEM;
1185 }
1186 /* At this point, ent actually owns a ref of nsurl */
1187 if (read(fd, ent, sizeof(*ent)) != sizeof(*ent)) {
1188 /* The read failed, so reset the ptr */
1189 ent->url = nsurl; /* It already had a ref */
1190 nsurl_unref(nsurl);
1191 close(fd);
1192 free(fname);
1193 return NSERROR_INIT_FAILED;
1194 }
1195 ent->url = nsurl; /* It already owns a ref */
1196 nsurl_unref(nsurl);
1197 NSLOG(netsurf, DEBUG, "Successfully read entry for %s", nsurl_access(ent->url));
1198 read_entries++;
1199 /* Note the size allocation */
1200 state->total_alloc += ent->elem[ENTRY_ELEM_DATA].size;
1201 state->total_alloc += ent->elem[ENTRY_ELEM_META].size;
1202 /* And ensure we don't pretend to have this in memory yet */
1203 ent->elem[ENTRY_ELEM_DATA].flags &= ~(ENTRY_ELEM_FLAG_HEAP | ENTRY_ELEM_FLAG_MMAP);
1204 ent->elem[ENTRY_ELEM_META].flags &= ~(ENTRY_ELEM_FLAG_HEAP | ENTRY_ELEM_FLAG_MMAP);
1205
1206 }
1207 close(fd);
1208 }
1209
1210 NSLOG(netsurf, INFO, "Read %"PRIsizet" entries from cache", read_entries);
1211
1212 free(fname);
1213 return NSERROR_OK;
1214 }
1215
1216
1217 /**
1218 * Read block file usage bitmaps.
1219 *
1220 * @param state The backing store state to put the loaded entries in.
1221 * @return NSERROR_OK on success or error code on failure.
1222 */
1223 static nserror
read_blocks(struct store_state * state)1224 read_blocks(struct store_state *state)
1225 {
1226 int bfidx; /* block file index */
1227 int elem_idx;
1228 int fd;
1229 ssize_t rd;
1230 char *fname = NULL;
1231 nserror ret;
1232
1233 ret = netsurf_mkpath(&fname, NULL, 2, state->path, BLOCKS_FNAME);
1234 if (ret != NSERROR_OK) {
1235 return ret;
1236 }
1237
1238 NSLOG(netsurf, INFO, "Initialising block use map from %s", fname);
1239
1240 fd = open(fname, O_RDWR);
1241 free(fname);
1242 if (fd != -1) {
1243 /* initialise block file use array */
1244 for (elem_idx = 0; elem_idx < ENTRY_ELEM_COUNT; elem_idx++) {
1245 for (bfidx = 0; bfidx < BLOCK_FILE_COUNT; bfidx++) {
1246 rd = read(fd,
1247 &state->blocks[elem_idx][bfidx].use_map[0],
1248 BLOCK_USE_MAP_SIZE);
1249 if (rd <= 0) {
1250 NSLOG(netsurf, ERROR,
1251 "reading block file %d use index on file number %d failed",
1252 elem_idx,
1253 bfidx);
1254 goto rd_err;
1255 }
1256 }
1257 }
1258 rd_err:
1259 close(fd);
1260
1261 } else {
1262 NSLOG(netsurf, INFO, "Initialising block use map to defaults");
1263 /* ensure block 0 (invalid sentinel) is skipped */
1264 state->blocks[ENTRY_ELEM_DATA][0].use_map[0] = 1;
1265 state->blocks[ENTRY_ELEM_META][0].use_map[0] = 1;
1266 }
1267
1268 /* initialise block file file descriptors */
1269 for (bfidx = 0; bfidx < BLOCK_FILE_COUNT; bfidx++) {
1270 state->blocks[ENTRY_ELEM_DATA][bfidx].fd = -1;
1271 state->blocks[ENTRY_ELEM_META][bfidx].fd = -1;
1272 }
1273
1274 return NSERROR_OK;
1275 }
1276
1277 /**
1278 * Write the cache tag file.
1279 *
1280 * @param state The cache state.
1281 * @return NSERROR_OK on success or error code on failure.
1282 */
1283 static nserror
write_cache_tag(struct store_state * state)1284 write_cache_tag(struct store_state *state)
1285 {
1286 FILE *fcachetag;
1287 nserror ret;
1288 char *fname = NULL;
1289
1290 ret = netsurf_mkpath(&fname, NULL, 2, state->path, "CACHEDIR.TAG");
1291 if (ret != NSERROR_OK) {
1292 return ret;
1293 }
1294
1295 fcachetag = fopen(fname, "wb");
1296
1297 free(fname);
1298
1299 if (fcachetag == NULL) {
1300 return NSERROR_NOT_FOUND;
1301 }
1302
1303 fprintf(fcachetag,
1304 "Signature: 8a477f597d28d172789f06886806bc55\n"
1305 "# This file is a cache directory tag created by NetSurf.\n"
1306 "# For information about cache directory tags, see:\n"
1307 "# http://www.brynosaurus.com/cachedir/\n");
1308
1309 fclose(fcachetag);
1310
1311 return NSERROR_OK;
1312 }
1313
1314 /**
1315 * Write the control file for the current state.
1316 *
1317 * @param state The state to write to the control file.
1318 * @return NSERROR_OK on success or error code on failure.
1319 */
1320 static nserror
write_control(struct store_state * state)1321 write_control(struct store_state *state)
1322 {
1323 FILE *fcontrol;
1324 nserror ret;
1325 char *fname = NULL;
1326
1327 ret = netsurf_mkpath(&fname, NULL, 2, state->path, "control");
1328 if (ret != NSERROR_OK) {
1329 return ret;
1330 }
1331
1332 NSLOG(netsurf, INFO, "writing control file \"%s\"", fname);
1333
1334 ret = netsurf_mkdir_all(fname);
1335 if (ret != NSERROR_OK) {
1336 free(fname);
1337 return ret;
1338 }
1339
1340 fcontrol = fopen(fname, "wb");
1341
1342 free(fname);
1343
1344 if (fcontrol == NULL) {
1345 return NSERROR_NOT_FOUND;
1346 }
1347
1348 fprintf(fcontrol, "%u%c", CONTROL_VERSION, 0);
1349
1350 fclose(fcontrol);
1351
1352 return NSERROR_OK;
1353 }
1354
1355
1356 /**
1357 * Read and parse the control file.
1358 *
1359 * @param state The state to read from the control file.
1360 * @return NSERROR_OK on success or error code on failure.
1361 */
1362 static nserror
read_control(struct store_state * state)1363 read_control(struct store_state *state)
1364 {
1365 nserror ret;
1366 FILE *fcontrol;
1367 unsigned int ctrlversion;
1368 char *fname = NULL;
1369
1370 ret = netsurf_mkpath(&fname, NULL, 2, state->path, "control");
1371 if (ret != NSERROR_OK) {
1372 return ret;
1373 }
1374
1375 NSLOG(netsurf, INFO, "opening control file \"%s\"", fname);
1376
1377 fcontrol = fopen(fname, "rb");
1378
1379 free(fname);
1380
1381 if (fcontrol == NULL) {
1382 /* unable to open control file */
1383 if (errno == ENOENT) {
1384 return NSERROR_NOT_FOUND;
1385 } else {
1386 return NSERROR_INIT_FAILED;
1387 }
1388 }
1389
1390 /* read control and setup new state */
1391
1392 /* first line is version */
1393 if (fscanf(fcontrol, "%u", &ctrlversion) != 1) {
1394 goto control_error;
1395 }
1396
1397 if (ctrlversion != CONTROL_VERSION) {
1398 goto control_error;
1399 }
1400
1401 if (fgetc(fcontrol) != 0) {
1402 goto control_error;
1403 }
1404
1405 fclose(fcontrol);
1406
1407 return NSERROR_OK;
1408
1409 control_error: /* problem with the control file */
1410
1411 fclose(fcontrol);
1412
1413 return NSERROR_INIT_FAILED;
1414 }
1415
1416
1417
1418
1419 /* Functions exported in the backing store table */
1420
1421 /**
1422 * Initialise the backing store.
1423 *
1424 * @param parameters to configure backing store.
1425 * @return NSERROR_OK on success or error code on failure.
1426 */
1427 static nserror
initialise(const struct llcache_store_parameters * parameters)1428 initialise(const struct llcache_store_parameters *parameters)
1429 {
1430 struct store_state *newstate;
1431 nserror ret;
1432
1433 /* check backing store is not already initialised */
1434 if (storestate != NULL) {
1435 return NSERROR_INIT_FAILED;
1436 }
1437
1438 /* if we are not allowed any space simply give up on init */
1439 if (parameters->limit == 0) {
1440 return NSERROR_OK;
1441 }
1442
1443 /* if the path to the cache directory is not set do not init */
1444 if (parameters->path == NULL) {
1445 return NSERROR_OK;
1446 }
1447
1448 /* allocate new store state and set defaults */
1449 newstate = calloc(1, sizeof(struct store_state));
1450 if (newstate == NULL) {
1451 return NSERROR_NOMEM;
1452 }
1453
1454 newstate->path = strdup(parameters->path);
1455 newstate->limit = parameters->limit;
1456 newstate->hysteresis = parameters->hysteresis;
1457
1458 /* read store control and create new if required */
1459 ret = read_control(newstate);
1460 if (ret != NSERROR_OK) {
1461 if (ret == NSERROR_NOT_FOUND) {
1462 NSLOG(netsurf, INFO, "cache control file not found, making fresh");
1463 } else {
1464 NSLOG(netsurf, ERROR, "read control failed %s",
1465 messages_get_errorcode(ret));
1466 ret = netsurf_recursive_rm(newstate->path);
1467 if (ret != NSERROR_OK) {
1468 NSLOG(netsurf, WARNING, "Error `%s` while removing `%s`",
1469 messages_get_errorcode(ret), newstate->path);
1470 NSLOG(netsurf, WARNING, "Unable to clean up partial cache state.");
1471 NSLOG(netsurf, WARNING, "Funky behaviour may ensue.");
1472 } else {
1473 NSLOG(netsurf, INFO, "Successfully removed old cache from `%s`",
1474 newstate->path);
1475 }
1476 }
1477 ret = write_control(newstate);
1478 if (ret == NSERROR_OK) {
1479 unlink_entries(newstate);
1480 write_cache_tag(newstate);
1481 }
1482 }
1483 if (ret != NSERROR_OK) {
1484 /* that went well obviously */
1485 free(newstate->path);
1486 free(newstate);
1487 return ret;
1488 }
1489
1490 /* read filesystem entries */
1491 ret = read_entries(newstate);
1492 if (ret != NSERROR_OK) {
1493 /* that went well obviously */
1494 free(newstate->path);
1495 free(newstate);
1496 return ret;
1497 }
1498
1499 /* read blocks */
1500 ret = read_blocks(newstate);
1501 if (ret != NSERROR_OK) {
1502 /* oh dear */
1503 hashmap_destroy(newstate->entries);
1504 free(newstate->path);
1505 free(newstate);
1506 return ret;
1507 }
1508
1509 storestate = newstate;
1510
1511 NSLOG(netsurf, INFO, "FS backing store init successful");
1512
1513 NSLOG(netsurf, INFO,
1514 "path:%s limit:%"PRIsizet" hyst:%"PRIsizet,
1515 newstate->path,
1516 newstate->limit,
1517 newstate->hysteresis);
1518 NSLOG(netsurf, INFO, "Using %"PRIu64"/%"PRIsizet,
1519 newstate->total_alloc, newstate->limit);
1520
1521 return NSERROR_OK;
1522 }
1523
1524
1525 /**
1526 * Finalise the backing store.
1527 *
1528 * \todo This will cause the backing store to leak any outstanding memory
1529 * allocations. This will probably best be done by a global use count.
1530 *
1531 * @return NSERROR_OK on success.
1532 */
1533 static nserror
finalise(void)1534 finalise(void)
1535 {
1536 int bf; /* block file index */
1537 unsigned int op_count;
1538
1539 if (storestate != NULL) {
1540 guit->misc->schedule(-1, control_maintenance, storestate);
1541 write_entries(storestate);
1542 write_blocks(storestate);
1543
1544 /* ensure all block files are closed */
1545 for (bf = 0; bf < BLOCK_FILE_COUNT; bf++) {
1546 if (storestate->blocks[ENTRY_ELEM_DATA][bf].fd != -1) {
1547 close(storestate->blocks[ENTRY_ELEM_DATA][bf].fd);
1548 }
1549 if (storestate->blocks[ENTRY_ELEM_META][bf].fd != -1) {
1550 close(storestate->blocks[ENTRY_ELEM_META][bf].fd);
1551 }
1552 }
1553
1554 op_count = storestate->hit_count + storestate->miss_count;
1555
1556 /* avoid division by zero */
1557 if (op_count > 0) {
1558 NSLOG(netsurf, INFO,
1559 "Cache total/hit/miss/fail (counts) %d/%"PRIsizet"/%"PRIsizet"/%d (100%%/%"PRIsizet"%%/%"PRIsizet"%%/%d%%)",
1560 op_count,
1561 storestate->hit_count,
1562 storestate->miss_count,
1563 0,
1564 (storestate->hit_count * 100) / op_count,
1565 (storestate->miss_count * 100) / op_count,
1566 0);
1567 }
1568
1569 hashmap_destroy(storestate->entries);
1570 free(storestate->path);
1571 free(storestate);
1572 storestate = NULL;
1573 }
1574 return NSERROR_OK;
1575 }
1576
1577
1578 /**
1579 * Write an element of an entry to backing storage in a small block file.
1580 *
1581 * \param state The backing store state to use.
1582 * \param bse The entry to store
1583 * \param elem_idx The element index within the entry.
1584 * \return NSERROR_OK on success or error code.
1585 */
store_write_block(struct store_state * state,struct store_entry * bse,int elem_idx)1586 static nserror store_write_block(struct store_state *state,
1587 struct store_entry *bse,
1588 int elem_idx)
1589 {
1590 block_index_t bf = (bse->elem[elem_idx].block >> BLOCK_ENTRY_COUNT) &
1591 ((1 << BLOCK_FILE_COUNT) - 1); /* block file block resides in */
1592 block_index_t bi = bse->elem[elem_idx].block & ((1U << BLOCK_ENTRY_COUNT) -1); /* block index in file */
1593 ssize_t wr;
1594 off_t offst;
1595
1596 /* ensure the block file fd is good */
1597 if (state->blocks[elem_idx][bf].fd == -1) {
1598 state->blocks[elem_idx][bf].fd = store_open(state, bf,
1599 elem_idx + ENTRY_ELEM_COUNT, O_CREAT | O_RDWR);
1600 if (state->blocks[elem_idx][bf].fd == -1) {
1601 NSLOG(netsurf, ERROR, "Open failed errno %d", errno);
1602 return NSERROR_SAVE_FAILED;
1603 }
1604
1605 /* flag that a block file has been opened */
1606 state->blocks_opened = true;
1607 }
1608
1609 offst = (unsigned int)bi << log2_block_size[elem_idx];
1610
1611 wr = nsu_pwrite(state->blocks[elem_idx][bf].fd,
1612 bse->elem[elem_idx].data,
1613 bse->elem[elem_idx].size,
1614 offst);
1615 if (wr != (ssize_t)bse->elem[elem_idx].size) {
1616 NSLOG(netsurf, ERROR,
1617 "Write failed %"PRIssizet" of %d bytes from %p at %"PRIsizet" block %d errno %d",
1618 wr,
1619 bse->elem[elem_idx].size,
1620 bse->elem[elem_idx].data,
1621 (size_t)offst,
1622 bse->elem[elem_idx].block,
1623 errno);
1624 return NSERROR_SAVE_FAILED;
1625 }
1626
1627 NSLOG(netsurf, INFO,
1628 "Wrote %"PRIssizet" bytes from %p at %"PRIsizet" block %d", wr,
1629 bse->elem[elem_idx].data, (size_t)offst,
1630 bse->elem[elem_idx].block);
1631
1632 return NSERROR_OK;
1633 }
1634
1635 /**
1636 * Write an element of an entry to backing storage as an individual file.
1637 *
1638 * \param state The backing store state to use.
1639 * \param bse The entry to store
1640 * \param elem_idx The element index within the entry.
1641 * \return NSERROR_OK on success or error code.
1642 */
store_write_file(struct store_state * state,struct store_entry * bse,int elem_idx)1643 static nserror store_write_file(struct store_state *state,
1644 struct store_entry *bse,
1645 int elem_idx)
1646 {
1647 ssize_t wr;
1648 int fd;
1649 int err;
1650
1651 fd = store_open(state, nsurl_hash(bse->url), elem_idx, O_CREAT | O_WRONLY);
1652 if (fd < 0) {
1653 perror("");
1654 NSLOG(netsurf, ERROR, "Open failed %d errno %d", fd, errno);
1655 return NSERROR_SAVE_FAILED;
1656 }
1657
1658 wr = write(fd, bse->elem[elem_idx].data, bse->elem[elem_idx].size);
1659 err = errno; /* close can change errno */
1660
1661 close(fd);
1662 if (wr != (ssize_t)bse->elem[elem_idx].size) {
1663 NSLOG(netsurf, ERROR,
1664 "Write failed %"PRIssizet" of %d bytes from %p errno %d",
1665 wr,
1666 bse->elem[elem_idx].size,
1667 bse->elem[elem_idx].data,
1668 err);
1669
1670 /** @todo Delete the file? */
1671 return NSERROR_SAVE_FAILED;
1672 }
1673
1674 NSLOG(netsurf, VERBOSE, "Wrote %"PRIssizet" bytes from %p", wr,
1675 bse->elem[elem_idx].data);
1676
1677 return NSERROR_OK;
1678 }
1679
1680 /**
1681 * Place an object in the backing store.
1682 *
1683 * takes ownership of the heap block passed in.
1684 *
1685 * @param url The url is used as the unique primary key for the data.
1686 * @param bsflags The flags to control how the object is stored.
1687 * @param data The objects source data.
1688 * @param datalen The length of the \a data.
1689 * @return NSERROR_OK on success or error code on failure.
1690 */
1691 static nserror
store(nsurl * url,enum backing_store_flags bsflags,uint8_t * data,const size_t datalen)1692 store(nsurl *url,
1693 enum backing_store_flags bsflags,
1694 uint8_t *data,
1695 const size_t datalen)
1696 {
1697 nserror ret;
1698 struct store_entry *bse;
1699 int elem_idx;
1700
1701 /* check backing store is initialised */
1702 if (storestate == NULL) {
1703 return NSERROR_INIT_FAILED;
1704 }
1705
1706 /* calculate the entry element index */
1707 if ((bsflags & BACKING_STORE_META) != 0) {
1708 elem_idx = ENTRY_ELEM_META;
1709 } else {
1710 elem_idx = ENTRY_ELEM_DATA;
1711 }
1712
1713 /* set the store entry up */
1714 ret = set_store_entry(storestate, url, elem_idx, data, datalen, &bse);
1715 if (ret != NSERROR_OK) {
1716 NSLOG(netsurf, ERROR, "store entry setting failed");
1717 return ret;
1718 }
1719
1720 if (bse->elem[elem_idx].block != 0) {
1721 /* small block storage */
1722 ret = store_write_block(storestate, bse, elem_idx);
1723 } else {
1724 /* separate file in backing store */
1725 ret = store_write_file(storestate, bse, elem_idx);
1726 }
1727
1728 return ret;
1729 }
1730
1731 /**
1732 * release any allocation for an entry
1733 */
entry_release_alloc(struct store_entry_element * elem)1734 static nserror entry_release_alloc(struct store_entry_element *elem)
1735 {
1736 if ((elem->flags & ENTRY_ELEM_FLAG_HEAP) != 0) {
1737 elem->ref--;
1738 if (elem->ref == 0) {
1739 NSLOG(netsurf, DEEPDEBUG, "freeing %p", elem->data);
1740 free(elem->data);
1741 elem->flags &= ~ENTRY_ELEM_FLAG_HEAP;
1742 }
1743 }
1744 return NSERROR_OK;
1745 }
1746
1747
1748 /**
1749 * Read an element of an entry from a small block file in the backing storage.
1750 *
1751 * \param state The backing store state to use.
1752 * \param bse The entry to read.
1753 * \param elem_idx The element index within the entry.
1754 * \return NSERROR_OK on success or error code.
1755 */
store_read_block(struct store_state * state,struct store_entry * bse,int elem_idx)1756 static nserror store_read_block(struct store_state *state,
1757 struct store_entry *bse,
1758 int elem_idx)
1759 {
1760 block_index_t bf = (bse->elem[elem_idx].block >> BLOCK_ENTRY_COUNT) &
1761 ((1 << BLOCK_FILE_COUNT) - 1); /* block file block resides in */
1762 block_index_t bi = bse->elem[elem_idx].block & ((1 << BLOCK_ENTRY_COUNT) -1); /* block index in file */
1763 ssize_t rd;
1764 off_t offst;
1765
1766 /* ensure the block file fd is good */
1767 if (state->blocks[elem_idx][bf].fd == -1) {
1768 state->blocks[elem_idx][bf].fd = store_open(state, bf,
1769 elem_idx + ENTRY_ELEM_COUNT, O_CREAT | O_RDWR);
1770 if (state->blocks[elem_idx][bf].fd == -1) {
1771 NSLOG(netsurf, ERROR, "Open failed errno %d", errno);
1772 return NSERROR_SAVE_FAILED;
1773 }
1774
1775 /* flag that a block file has been opened */
1776 state->blocks_opened = true;
1777 }
1778
1779 offst = (unsigned int)bi << log2_block_size[elem_idx];
1780
1781 rd = nsu_pread(state->blocks[elem_idx][bf].fd,
1782 bse->elem[elem_idx].data,
1783 bse->elem[elem_idx].size,
1784 offst);
1785 if (rd != (ssize_t)bse->elem[elem_idx].size) {
1786 NSLOG(netsurf, ERROR,
1787 "Failed reading %"PRIssizet" of %d bytes into %p from %"PRIsizet" block %d errno %d",
1788 rd,
1789 bse->elem[elem_idx].size,
1790 bse->elem[elem_idx].data,
1791 (size_t)offst,
1792 bse->elem[elem_idx].block,
1793 errno);
1794 return NSERROR_SAVE_FAILED;
1795 }
1796
1797 NSLOG(netsurf, DEEPDEBUG,
1798 "Read %"PRIssizet" bytes into %p from %"PRIsizet" block %d", rd,
1799 bse->elem[elem_idx].data, (size_t)offst,
1800 bse->elem[elem_idx].block);
1801
1802 return NSERROR_OK;
1803 }
1804
1805 /**
1806 * Read an element of an entry from an individual file in the backing storage.
1807 *
1808 * \param state The backing store state to use.
1809 * \param bse The entry to read.
1810 * \param elem_idx The element index within the entry.
1811 * \return NSERROR_OK on success or error code.
1812 */
store_read_file(struct store_state * state,struct store_entry * bse,int elem_idx)1813 static nserror store_read_file(struct store_state *state,
1814 struct store_entry *bse,
1815 int elem_idx)
1816 {
1817 int fd;
1818 ssize_t rd; /* return from read */
1819 int ret = NSERROR_OK;
1820 size_t tot = 0; /* total size */
1821
1822 /* separate file in backing store */
1823 fd = store_open(storestate, nsurl_hash(bse->url), elem_idx, O_RDONLY);
1824 if (fd < 0) {
1825 NSLOG(netsurf, ERROR, "Open failed %d errno %d", fd, errno);
1826 /** @todo should this invalidate the entry? */
1827 return NSERROR_NOT_FOUND;
1828 }
1829
1830 while (tot < bse->elem[elem_idx].size) {
1831 rd = read(fd,
1832 bse->elem[elem_idx].data + tot,
1833 bse->elem[elem_idx].size - tot);
1834 if (rd <= 0) {
1835 NSLOG(netsurf, ERROR,
1836 "read error returned %"PRIssizet" errno %d",
1837 rd,
1838 errno);
1839 ret = NSERROR_NOT_FOUND;
1840 break;
1841 }
1842 tot += rd;
1843 }
1844
1845 close(fd);
1846
1847 NSLOG(netsurf, DEEPDEBUG, "Read %"PRIsizet" bytes into %p", tot,
1848 bse->elem[elem_idx].data);
1849
1850 return ret;
1851 }
1852
1853 /**
1854 * Retrieve an object from the backing store.
1855 *
1856 * @param[in] url The url is used as the unique primary key for the data.
1857 * @param[in] bsflags The flags to control how the object is retrieved.
1858 * @param[out] data_out The objects data.
1859 * @param[out] datalen_out The length of the \a data retrieved.
1860 * @return NSERROR_OK on success or error code on failure.
1861 */
1862 static nserror
fetch(nsurl * url,enum backing_store_flags bsflags,uint8_t ** data_out,size_t * datalen_out)1863 fetch(nsurl *url,
1864 enum backing_store_flags bsflags,
1865 uint8_t **data_out,
1866 size_t *datalen_out)
1867 {
1868 nserror ret;
1869 struct store_entry *bse;
1870 struct store_entry_element *elem;
1871 int elem_idx;
1872
1873 /* check backing store is initialised */
1874 if (storestate == NULL) {
1875 return NSERROR_INIT_FAILED;
1876 }
1877
1878 /* fetch store entry */
1879 ret = get_store_entry(storestate, url, &bse);
1880 if (ret != NSERROR_OK) {
1881 NSLOG(netsurf, DEBUG, "Entry for %s not found", nsurl_access(url));
1882 storestate->miss_count++;
1883 return ret;
1884 }
1885 storestate->hit_count++;
1886
1887 NSLOG(netsurf, DEBUG, "retrieving cache data for url:%s",
1888 nsurl_access(url));
1889
1890 /* calculate the entry element index */
1891 if ((bsflags & BACKING_STORE_META) != 0) {
1892 elem_idx = ENTRY_ELEM_META;
1893 } else {
1894 elem_idx = ENTRY_ELEM_DATA;
1895 }
1896 elem = &bse->elem[elem_idx];
1897
1898 /* if an allocation already exists return it */
1899 if ((elem->flags & ENTRY_ELEM_FLAG_HEAP) != 0) {
1900 /* use the existing allocation and bump the ref count. */
1901 elem->ref++;
1902
1903 NSLOG(netsurf, DEEPDEBUG,
1904 "Using existing entry (%p) allocation %p refs:%d", bse,
1905 elem->data, elem->ref);
1906
1907 } else {
1908 /* allocate from the heap */
1909 elem->data = malloc(elem->size);
1910 if (elem->data == NULL) {
1911 NSLOG(netsurf, ERROR,
1912 "Failed to create new heap allocation");
1913 return NSERROR_NOMEM;
1914 }
1915 NSLOG(netsurf, DEEPDEBUG, "Created new heap allocation %p",
1916 elem->data);
1917
1918 /* mark the entry as having a valid heap allocation */
1919 elem->flags |= ENTRY_ELEM_FLAG_HEAP;
1920 elem->ref = 1;
1921
1922 /* fill the new block */
1923 if (elem->block != 0) {
1924 ret = store_read_block(storestate, bse, elem_idx);
1925 } else {
1926 ret = store_read_file(storestate, bse, elem_idx);
1927 }
1928 }
1929
1930 /* free the allocation if there is a read error */
1931 if (ret != NSERROR_OK) {
1932 entry_release_alloc(elem);
1933 } else {
1934 /* update stats and setup return pointers */
1935 storestate->hit_size += elem->size;
1936
1937 *data_out = elem->data;
1938 *datalen_out = elem->size;
1939 }
1940
1941 return ret;
1942 }
1943
1944
1945 /**
1946 * release a previously fetched or stored memory object.
1947 *
1948 * @param[in] url The url is used as the unique primary key to invalidate.
1949 * @param[in] bsflags The flags to control how the object data is released.
1950 * @return NSERROR_OK on success or error code on failure.
1951 */
release(nsurl * url,enum backing_store_flags bsflags)1952 static nserror release(nsurl *url, enum backing_store_flags bsflags)
1953 {
1954 nserror ret;
1955 struct store_entry *bse;
1956 struct store_entry_element *elem;
1957
1958 /* check backing store is initialised */
1959 if (storestate == NULL) {
1960 return NSERROR_INIT_FAILED;
1961 }
1962
1963 ret = get_store_entry(storestate, url, &bse);
1964 if (ret != NSERROR_OK) {
1965 NSLOG(netsurf, WARNING, "entry not found");
1966 return ret;
1967 }
1968
1969 /* the entry element */
1970 if ((bsflags & BACKING_STORE_META) != 0) {
1971 elem = &bse->elem[ENTRY_ELEM_META];
1972 } else {
1973 elem = &bse->elem[ENTRY_ELEM_DATA];
1974 }
1975
1976 ret = entry_release_alloc(elem);
1977
1978 /* if the entry has previously been invalidated but had
1979 * allocation it must be invalidated fully now the allocation
1980 * has been released.
1981 */
1982 if ((ret == NSERROR_OK) &&
1983 ((bse->flags & ENTRY_FLAGS_INVALID) != 0)) {
1984 ret = invalidate_entry(storestate, bse);
1985 }
1986
1987 return ret;
1988 }
1989
1990
1991 /**
1992 * Invalidate a source object from the backing store.
1993 *
1994 * The entry (if present in the backing store) must no longer
1995 * be returned as a result to the fetch or meta operations.
1996 *
1997 * @param url The url is used as the unique primary key to invalidate.
1998 * @return NSERROR_OK on success or error code on failure.
1999 */
2000 static nserror
invalidate(nsurl * url)2001 invalidate(nsurl *url)
2002 {
2003 nserror ret;
2004 struct store_entry *bse;
2005
2006 /* check backing store is initialised */
2007 if (storestate == NULL) {
2008 return NSERROR_INIT_FAILED;
2009 }
2010
2011 ret = get_store_entry(storestate, url, &bse);
2012 if (ret != NSERROR_OK) {
2013 return ret;
2014 }
2015
2016 return invalidate_entry(storestate, bse);
2017 }
2018
2019
2020 static struct gui_llcache_table llcache_table = {
2021 .initialise = initialise,
2022 .finalise = finalise,
2023 .store = store,
2024 .fetch = fetch,
2025 .invalidate = invalidate,
2026 .release = release,
2027 };
2028
2029 struct gui_llcache_table *filesystem_llcache_table = &llcache_table;
2030