?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Debug: Improve data dump in dump_block()
[hed.git] / libhed / file.c
blobdccc970453abee35e88efc981f68059a71b8308e
1 /* $Id$ */
2
3 /*
4 * hed - Hexadecimal editor
5 * Copyright (C) 2004 Petr Baudis <pasky@ucw.cz>
6 *
7 * This program is free software; you can redistribute it and/or modify
8 * it under the terms of version 2 of the GNU General Public License as
9 * published by the Free Software Foundation.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
19 */
20
21 /*
22 * There hammer on the anvil smote,
23 * There chisel clove, and graver wrote;
24 * There forged was blade, and bound was hilt;
25 * The delver mined, the mason built.
26 * There beryl, pearl, and opal pale,
27 * And metal wrought like fishes' mail,
28 * Buckler and corslet, axe and sword,
29 * And shining spears were laid in hoard.
30 */
31
32 /* Feature macros needed for:
33 * - memrchr
34 * - pread, pwrite
35 * - stpcpy
36 */
37 #define _GNU_SOURCE
38
39 #include <config.h>
40
41 #include <errno.h>
42 #include <fcntl.h>
43 #include <limits.h>
44 #include <stdio.h>
45 #include <stdlib.h>
46 #include <string.h>
47 #include <sys/ioctl.h>
48 #include <unistd.h>
49 #include <linux/fs.h> /* BLKGETSIZE and BLKGETSIZE64 */
50
51 #include "file.h"
52 #include "file_priv.h"
53 #include "access.h"
54 #include "cache.h"
55 #include "swap.h"
56 #include "tree.h"
57 #include "expr.h"
58
59 /* memrchr() might not be available */
60 #ifndef HAVE_MEMRCHR
61 # include "memrchr.c"
62 #endif /* HAVE_MEMRCHR */
63
64 /*
65 * `Piles of jewels?' said Gandalf. `No. The Orcs have often plundered Moria;
66 * there is nothing left in the upper halls. And since the dwarves fled, no one
67 * dares to seek the shafts and treasuries down in the deep places: they are
68 * drowned in water--or in a shadow of fear.'
69 */
70
71 /* TODO: Currently the file blocks allocation is not very sophisticated and
72 * when the weather is bad it could probably have rather horrible results. */
73
74 #undef BLOCKS_DEBUG
75 #ifdef BLOCKS_DEBUG
76 #define BDEBUG(x...) fprintf(stderr, x)
77 #else
78 #define BDEBUG(x...)
79 #endif
80
81 /* Number of blocks in cache */
82 #define CACHE_LENGTH 64
83
84 /* Blocks for readahead */
85 #define FILE_READAHEAD (CACHE_LENGTH/2)
86
87 /* Searches for data object don't care about the EOF flag */
88 #define STATEMASK_SANS_EOF (HED_BLOCK_STATEMASK & ~HED_BLOCK_EOF)
89
90 #define first_block(f) next_block(last_block(f))
91 #define prev_block(b) (tree_entry(prev_in_tree(&(b)->t),struct hed_block,t))
92 #define next_block(b) (tree_entry(next_in_tree(&(b)->t),struct hed_block,t))
93 #define last_block(f) (&(f)->terminal_block)
94
95 #define block_offset(b) tree_block_offset(&(b)->t)
96
97 #define recalc_block_recursive(b) recalc_node_recursive(&(b)->t)
98
99 #define chain_block(tree,b,p) insert_into_tree((tree), &(b)->t, &(p)->t)
100 #define recalc_chain_block(tree,b,p) do { \
101 chain_block((tree), (b), (p)); \
102 recalc_block_recursive((b)); \
103 } while (0)
104
105 #define unchain_block(tree,b) del_from_tree((tree), &(b)->t)
106 #define recalc_unchain_block(tree,b) recalc_del_from_tree((tree), &(b)->t)
107
108 #define init_block_list(tree,b) init_tree(tree, &(b)->t)
109 #define init_block_link(b) init_node(&(b)->t)
110
111 #define find_block(tree,o) tree_entry(find_in_tree((tree),(o)),struct hed_block,t)
112
113 #define block_is_loadable(b) \
114 (((b)->flags & (HED_BLOCK_VIRTUAL | HED_BLOCK_EOF | HED_BLOCK_BAD)) \
115 == HED_BLOCK_VIRTUAL)
116
117 #ifdef HED_CONFIG_SWAP
118
119 /* Return the swp file object */
120 static inline struct swp_file *
121 file_swp(struct file_priv *file)
122 {
123 return file->swp;
124 }
125
126 #else
127
128 /* Provide a stub for the non-swap case */
129 static inline void *
130 file_swp(struct file_priv *file)
131 {
132 return NULL;
133 }
134
135 #endif
136
137 #ifdef HED_CONFIG_READAHEAD
138
139 #define file_ra_none(f) ((f)->readahead == HED_RA_NONE)
140 #define file_ra_forward(f) ((f)->readahead == HED_RA_FORWARD)
141 #define file_ra_backward(f) ((f)->readahead == HED_RA_BACKWARD)
142
143 static inline void
144 set_readahead(struct file_priv *file, int val)
145 {
146 file->readahead = val;
147 }
148
149 #else
150
151 #define file_ra_none(f) (1)
152 #define file_ra_forward(f) (0)
153 #define file_ra_backward(f) (0)
154 #define set_readahead(file,t) do {} while(0)
155
156 #endif /* HED_CONFIG_READAHEAD */
157
158 void
159 hed_file_set_readahead(struct hed_file *file, enum hed_readahead val)
160 {
161 set_readahead(file_private(file), val);
162 }
163
164
165 /* Get the physical offset of the byte immediately following @block. */
166 static inline hed_uoff_t
167 phys_end(const struct hed_block *block)
168 {
169 return hed_block_is_inserted(block)
170 ? block->phys_pos
171 : block->phys_pos + hed_block_size(block);
172 }
173
174 static struct hed_block *
175 next_nonzero_block(struct hed_block *block)
176 {
177 while (!hed_block_is_terminal(block)) {
178 block = next_block(block);
179 if (hed_block_size(block))
180 return block;
181 }
182 return NULL;
183 }
184
185 static struct hed_block *
186 prev_nonzero_block(struct hed_block *block)
187 {
188 do {
189 block = prev_block(block);
190 if (hed_block_is_terminal(block))
191 return NULL;
192 } while (!hed_block_size(block));
193 return block;
194 }
195
196 bool
197 hed_block_is_after_erase(struct hed_block *block)
198 {
199 struct hed_block *prev = prev_nonzero_block(block);
200 return prev
201 ? block->phys_pos > phys_end(prev)
202 : !!block->phys_pos;
203 }
204
205 bool
206 hed_block_is_after_insert(struct hed_block *block)
207 {
208 struct hed_block *prev = prev_nonzero_block(block);
209 return prev && hed_block_is_inserted(prev);
210 }
211
212 /* Get the blocks tree */
213 static inline struct hed_tree *
214 hed_file_blocks(struct file_priv *file)
215 {
216 return &file->blocks;
217 }
218
219 #ifndef BLOCKS_DEBUG
220 # define dump_blocks(file) {}
221 #else
222
223 static hed_uoff_t
224 block_phys_size(struct hed_block *block)
225 {
226 struct hed_block *next;
227
228 if (hed_block_is_terminal(block))
229 return 0;
230 next = next_block(block);
231 return next->phys_pos - block->phys_pos;
232 }
233
234 static void
235 dump_block(int level, struct file_priv *file, struct hed_tree_node *node,
236 hed_uoff_t *cur_offset, hed_uoff_t *cur_poffset)
237 {
238 struct hed_block *block = tree_entry(node, struct hed_block, t);
239 unsigned char *p;
240 hed_cursor_t *cur;
241 char t[21] = " ";
242 char data[9], *dp;
243
244 if (node->left)
245 dump_block(level + 1, file, node->left, cur_offset, cur_poffset);
246 p = hed_block_data(block);
247 dp = data;
248 if (p && hed_block_size(block)) {
249 if (node->maxoff >= 0)
250 dp += snprintf(dp, 3, "%02x", p[0]);
251 if (node->maxoff >= 1)
252 dp += snprintf(dp, 3, "%02x", p[1]);
253 if (node->maxoff >= 2)
254 dp += snprintf(dp, 3, "%02x", p[2]);
255 if (node->maxoff >= 3)
256 dp += snprintf(dp, 3, "%02x", p[3]);
257 }
258 memset(dp, ' ', sizeof(data) - (dp - data));
259 data[8] = 0;
260
261 if (level < 20) t[level] = '>'; else t[19] = '.';
262 fprintf(stderr, "%s [%06llx] [%06llx] %c%c%c%c%c %05llx %05llx"
263 " {%s} -- %p ^%p [%06llx]\n",
264 t,
265 (unsigned long long) *cur_offset,
266 (unsigned long long) *cur_poffset,
267 hed_block_is_bad(block) ? 'b' : ' ',
268 hed_block_is_eof(block) ? 'e' : ' ',
269 hed_block_is_virtual(block) ? 'v' : ' ',
270 hed_block_is_inserted(block) ? 'i' : ' ',
271 hed_block_is_dirty(block) ? '*' : ' ',
272 (unsigned long long) node->maxoff + 1,
273 (unsigned long long) block_phys_size(block),
274 data,
275 node, node->up,
276 (unsigned long long) node->cover_size
277 );
278 list_for_each_entry (cur, &block->refs, list) {
279 fprintf(stderr, " <%p>: %llx->%p:%llx\n",
280 cur, (long long)cur->pos,
281 cur->block, (unsigned long long)cur->off);
282 }
283 assert(*cur_poffset == block->phys_pos);
284 *cur_offset += node->maxoff + 1;
285 *cur_poffset += block_phys_size(block);
286 if (node->right)
287 dump_block(level + 1, file, node->right, cur_offset, cur_poffset);
288 assert(node->cover_size == (node->left ? node->left->cover_size : 0)
289 + (node->right ? node->right->cover_size : 0)
290 + node->maxoff + 1);
291 }
292
293 /* Walk the tree manually here, because foreach_block() does not provide
294 * the tree structure.
295 * TODO: Change this if you plan to debug any other block containers.
296 */
297 static void
298 dump_blocks(struct file_priv *file)
299 {
300 struct hed_block *first = first_block(file);
301 hed_uoff_t cur_offset, cur_poffset;
302
303 fprintf(stderr, "-- blocks dump --\n");
304 cur_offset = 0;
305 cur_poffset = first->phys_pos;
306 dump_block(0, file, hed_file_blocks(file)->root,
307 &cur_offset, &cur_poffset);
308 fprintf(stderr, "-- blocks dump end --\n");
309 }
310 #endif
311
312 static void
313 get_cursor(struct file_priv *file, hed_uoff_t offset, hed_cursor_t *curs)
314 {
315 struct hed_block *block;
316
317 block = find_block(hed_file_blocks(file), offset);
318 assert(block != NULL);
319 curs->pos = offset;
320 curs->block = block;
321 curs->off = offset - block_offset(block);
322 list_add(&curs->list, &block->refs);
323
324 BDEBUG("Mapped %llx to %llx+%llx/%llx\n",
325 offset, offset - curs->off, curs->off, hed_block_size(block));
326 }
327
328 void
329 hed_get_cursor(struct hed_file *file, hed_uoff_t offset, hed_cursor_t *curs)
330 {
331 get_cursor(file_private(file), offset, curs);
332 }
333
334 static inline void
335 put_cursor(hed_cursor_t *curs)
336 {
337 list_del(&curs->list);
338 }
339
340 void
341 hed_put_cursor(hed_cursor_t *curs)
342 {
343 put_cursor(curs);
344 }
345
346 void
347 hed_update_cursor(struct hed_file *file, hed_uoff_t offset, hed_cursor_t *curs)
348 {
349 put_cursor(curs);
350 get_cursor(file_private(file), offset, curs);
351 }
352
353 void
354 hed_dup_cursor(const hed_cursor_t *src, hed_cursor_t *dst)
355 {
356 dst->pos = src->pos;
357 dst->block = src->block;
358 dst->off = src->off;
359 list_add_tail(&dst->list, &src->block->refs);
360 }
361
362 void
363 hed_dup2_cursor(const hed_cursor_t *src, hed_cursor_t *dst)
364 {
365 if (hed_is_a_cursor(dst))
366 put_cursor(dst);
367 hed_dup_cursor(src, dst);
368 }
369
370 /* Move cursors from @old to @new, adding @off to their block
371 * offsets to keep them at the same position. */
372 static void
373 update_cursors(const struct hed_block *old, struct hed_block *new,
374 hed_off_t off)
375 {
376 hed_cursor_t *curs;
377
378 BDEBUG("Updating cursors from <%p> to <%p>%c%llx\n",
379 old, new, off >= 0 ? '+' : '-', off >= 0 ? off : -off);
380
381 list_for_each_entry(curs, &old->refs, list) {
382 curs->block = new;
383 curs->off += off;
384 }
385 }
386
387 /* Move cursors in the range <@start;@end> from @old to @new,
388 * adding @off to their block offset, plus moving the reference list. */
389 static void
390 move_cursors(const struct hed_block *old, struct hed_block *new,
391 hed_uoff_t start, hed_uoff_t end, hed_off_t off)
392 {
393 hed_cursor_t *curs, *nextcurs;
394
395 BDEBUG("Moving cursors from <%p>:%llx:%llx to <%p>%c%llx\n",
396 old, start, end, new,
397 off >= 0 ? '+' : '-', off >= 0 ? off : -off);
398
399 list_for_each_entry_safe(curs, nextcurs, &old->refs, list)
400 if (curs->off >= start && curs->off <= end) {
401 curs->block = new;
402 curs->off += off;
403 list_move(&curs->list, &new->refs);
404 }
405 }
406
407 /* Move cursors in the range @block:<@start;@end> to @newpos */
408 static void
409 move_cursors_abs(const struct hed_block *block,
410 hed_uoff_t start, hed_uoff_t end,
411 const hed_cursor_t *newpos)
412 {
413 hed_cursor_t *curs, *nextcurs;
414
415 BDEBUG("Moving cursors from <%p>:%llx:%llx to <%p>:%llx\n",
416 block, start, end, newpos->block, newpos->off);
417
418 list_for_each_entry_safe(curs, nextcurs, &block->refs, list)
419 if (curs->off >= start && curs->off <= end) {
420 curs->pos = newpos->pos;
421 curs->block = newpos->block;
422 curs->off = newpos->off;
423 list_move(&curs->list, &newpos->block->refs);
424 }
425 }
426
427 /* Update the positions of cursors at and after @start for all
428 * blocks starting at @block */
429 static void
430 slide_cursors(const struct hed_block *block, hed_uoff_t start, hed_off_t off)
431 {
432 hed_cursor_t *curs;
433 const struct hed_block *nblock;
434
435 BDEBUG("Sliding cursors >= %llx by %c%llx, starting at <%p>\n",
436 start, off >= 0 ? '+' : '-', off >= 0 ? off : -off, block);
437 nblock = block;
438 do {
439 block = nblock;
440 list_for_each_entry(curs, &block->refs, list)
441 if (curs->pos >= start)
442 curs->pos += off;
443 nblock = next_block(block);
444 } while (!hed_block_is_terminal(block));
445 }
446
447 static struct hed_block *
448 new_block(struct file_priv *file, long flags)
449 {
450 struct hed_block *new;
451
452 if (! (new = swp_zalloc(file_swp(file), sizeof(struct hed_block))) )
453 return NULL;
454
455 new->flags = flags;
456 init_block_link(new);
457 INIT_LIST_HEAD(&new->refs);
458 if (flags & HED_BLOCK_EXCACHE)
459 INIT_LIST_HEAD(&new->lru);
460 else
461 list_add_tail(&new->lru, &file->lru);
462
463 return new;
464 }
465
466 static struct hed_block *
467 new_virt_block(struct file_priv *file, hed_uoff_t pos, hed_uoff_t size,
468 long extraflags)
469 {
470 struct hed_block *new = new_block(file, (HED_BLOCK_EXCACHE |
471 HED_BLOCK_VIRTUAL |
472 extraflags));
473 if (!new)
474 return NULL;
475
476 new->t.maxoff = size - 1;
477 new->phys_pos = pos;
478 BDEBUG("Spawned new virtual block [%llx] at %llx\n", size, pos);
479 return new;
480 }
481
482 static struct hed_block *
483 new_data_block(struct file_priv *file, hed_uoff_t pos, hed_uoff_t size,
484 struct hed_block_data *dataobj)
485 {
486 struct hed_block *new = new_block(file, 0);
487 if (!new)
488 return NULL;
489
490 cache_get(dataobj);
491 new->dataobj = dataobj;
492 new->t.maxoff = size - 1;
493 new->phys_pos = pos;
494 new->dataoff = FILE_BLOCK_OFF(pos);
495 BDEBUG("Spawned new data block [%llx] at %llx\n", size, pos);
496 return new;
497 }
498
499 static void
500 file_free_block(struct file_priv *file, struct hed_block *block)
501 {
502 if (block->dataobj)
503 cache_put(file->cache, block->dataobj);
504 list_del(&block->lru);
505
506 swp_free(file_swp(file), block);
507 }
508
509 static void
510 merge_and_free(struct file_priv *file, struct hed_block *block,
511 struct hed_block *merger, hed_off_t off)
512 {
513 /* A bit more efficient than move_cursors() */
514 update_cursors(block, merger, off);
515 list_splice(&block->refs, &merger->refs);
516
517 /* Messing with block sizes and unchaining is a bit tricky
518 * since unchain_block() can splay(). So we really need
519 * to recalc_block_recursive() right after we update the size.
520 * If this place turns out to be a hot-spot, we can optimize
521 * the tree operations here. */
522 merger->t.maxoff += hed_block_size(block);
523 recalc_block_recursive(merger);
524
525 /* Destroy the block */
526 recalc_unchain_block(hed_file_blocks(file), block);
527 file_free_block(file, block);
528 }
529
530 /* This may kill the previous block as well, if it can be merged
531 * with the next one. It will never kill anything which _follows_. */
532 static void
533 kill_block(struct file_priv *file, struct hed_block *block)
534 {
535 struct hed_block *prev, *next;
536
537 assert(!hed_block_is_dirty(block) || !hed_block_size(block));
538
539 if (!hed_block_is_virtual(block)) {
540 /* Convert physical to virtual */
541 assert(block->dataobj);
542 cache_put(file->cache, block->dataobj);
543 block->dataobj = NULL;
544
545 list_del_init(&block->lru); /* unlink the block from LRU */
546 block->flags = HED_BLOCK_EXCACHE | HED_BLOCK_VIRTUAL |
547 (block->flags & HED_BLOCK_EOF);
548 }
549
550 prev = prev_block(block);
551 if (prev->flags == block->flags &&
552 prev->phys_pos + hed_block_size(prev) == block->phys_pos) {
553 merge_and_free(file, block, prev, hed_block_size(prev));
554 block = prev;
555 }
556
557 next = next_block(block);
558 if (next->flags == block->flags &&
559 block->phys_pos + hed_block_size(block) == next->phys_pos) {
560 update_cursors(next, next, hed_block_size(block));
561 next->phys_pos -= hed_block_size(block);
562 merge_and_free(file, block, next, 0);
563 block = next;
564 }
565
566 if (!hed_block_size(block)) {
567 /* No recalculation needed, zero size. */
568 unchain_block(hed_file_blocks(file), block);
569 file_free_block(file, block);
570 }
571 }
572
573 static bool
574 kill_block_if_empty(struct file_priv *file, struct hed_block *block)
575 {
576 if (!hed_block_is_terminal(block) && hed_block_size(block) == 0 &&
577 list_empty(&block->refs)) {
578 kill_block(file, block);
579 return true;
580 }
581 return false;
582 }
583
584 static struct hed_block *
585 split_block(struct file_priv *file, struct hed_block *block,
586 hed_uoff_t splitpoint)
587 {
588 struct hed_block *head;
589
590 head = new_block(file, block->flags & ~HED_BLOCK_TERMINAL);
591 if (!head)
592 return NULL;
593
594 if ( (head->dataobj = block->dataobj) ) {
595 cache_get(head->dataobj);
596 head->dataoff = block->dataoff;
597 block->dataoff += splitpoint;
598 } else
599 assert(hed_block_is_virtual(block));
600
601 head->t.maxoff = splitpoint - 1;
602 head->phys_pos = block->phys_pos;
603
604 block->t.maxoff -= splitpoint;
605 if (!hed_block_is_inserted(block))
606 block->phys_pos += splitpoint;
607 recalc_block_recursive(block);
608 recalc_chain_block(hed_file_blocks(file), head, block);
609
610 move_cursors(block, head, 0, splitpoint - 1, 0);
611 update_cursors(block, block, -splitpoint);
612
613 return head;
614 }
615
616 /* Replace a chunk in @block with @newblock */
617 static int
618 replace_chunk(struct file_priv *file, struct hed_block *block,
619 hed_uoff_t offset, struct hed_block *newblock)
620 {
621 size_t len;
622
623 assert(offset <= block->t.maxoff);
624 assert(newblock->t.maxoff <= block->t.maxoff - offset);
625
626 /* Re-create the head block if necessary */
627 if (offset && !split_block(file, block, offset))
628 return -1;
629
630 /* Move pointers to the new block */
631 len = hed_block_size(newblock);
632 assert(len > 0);
633 move_cursors(block, newblock, 0, len - 1, 0);
634
635 /* Shorten the tail block */
636 len = hed_block_size(newblock);
637 block->t.maxoff -= len;
638 block->dataoff += len;
639 assert(!hed_block_is_inserted(block));
640 block->phys_pos += len;
641 recalc_block_recursive(block);
642 update_cursors(block, block, -(hed_off_t)len);
643
644 /* Insert the new block */
645 recalc_chain_block(hed_file_blocks(file), newblock, block);
646
647 /* Kill the leading block if possible */
648 kill_block_if_empty(file, block);
649
650 return 0;
651 }
652
653 #ifdef HED_CONFIG_SWAP
654
655 static char *
656 swp_filename(const char *filename)
657 {
658 size_t fnlen = strlen(filename);
659 char *swp;
660 char *file;
661
662 if (!(swp = malloc(fnlen + 9)) )
663 return NULL;
664 strcpy(swp, filename);
665
666 file = strrchr(swp, '/');
667 file = file ? file + 1 : swp;
668 *file = '.';
669 strcpy(stpcpy(file + 1, filename + (file -swp)), ".hedswp");
670 return swp;
671 }
672
673 static char *
674 newswp_filename(char *swpname)
675 {
676 char *p = NULL; /* bogus assignment to silence a warning */
677 char *ret;
678
679 ret = swpname;
680 while (!access(ret, F_OK)) {
681 if (ret == swpname) {
682 if (! (ret = strdup(swpname)) )
683 return NULL;
684 p = ret + strlen(ret) - 1;
685 }
686
687 if (*p == 'a') {
688 free(ret);
689 return NULL;
690 }
691 --*p;
692 }
693 return ret;
694 }
695
696 int
697 hed_file_remove_swap(struct hed_file *f)
698 {
699 struct file_priv *file = file_private(f);
700 if (remove(file->swpname))
701 return -1;
702 if (rename(file->newswpname, file->swpname))
703 return -1;
704
705 free(file->newswpname);
706 file->newswpname = file->swpname;
707 return 0;
708 }
709
710 static inline struct file_priv *
711 file_swp_init(const char *name)
712 {
713 char *swpname, *newswpname;
714 struct swp_file *swp;
715 struct file_priv *file;
716
717 swpname = swp_filename(name);
718 if (!swpname)
719 goto fail;
720 newswpname = newswp_filename(swpname);
721 if (!newswpname)
722 goto fail_free_name;
723 swp = swp_init_write(newswpname);
724 if (!swp)
725 goto fail_free_newname;
726
727 assert(sizeof(struct swp_header) + sizeof(struct file_priv)
728 <= FILE_BLOCK_SIZE);
729 file = swp_private(swp);
730 memset(file, 0, sizeof *file);
731
732 file->swp = swp;
733 file->swpname = swpname;
734 file->newswpname = newswpname;
735
736 return file;
737
738 fail_free_newname:
739 free(newswpname);
740 fail_free_name:
741 if (swpname != newswpname)
742 free(swpname);
743 fail:
744 return NULL;
745 }
746
747 static inline void
748 file_swp_done(struct file_priv *file)
749 {
750 remove(file->newswpname);
751 if (file->newswpname != file->swpname)
752 free(file->newswpname);
753 free(file->swpname);
754 swp_done(file_swp(file));
755 /* file was de-allocated automatically with file->swp */
756 }
757
758 int
759 hed_file_has_swap(struct hed_file *f)
760 {
761 struct file_priv *file = file_private(f);
762 return file->swpname != file->newswpname;
763 }
764
765 char *
766 hed_file_swap_name(struct hed_file *f)
767 {
768 struct file_priv *file = file_private(f);
769 return file->swpname;
770 }
771
772 #else /* HED_CONFIG_SWAP */
773
774 static inline struct file_priv *
775 file_swp_init(const char *name)
776 {
777 return calloc(1, sizeof(struct file_priv));
778 }
779
780 static inline void
781 file_swp_done(struct file_priv *file)
782 {
783 free(file);
784 }
785
786 int
787 hed_file_has_swap(struct hed_file *file)
788 {
789 return 0;
790 }
791
792 int
793 hed_file_remove_swap(struct hed_file *file)
794 {
795 return 0;
796 }
797
798 char *
799 hed_file_swap_name(struct hed_file *file)
800 {
801 return NULL;
802 }
803
804 #endif /* HED_CONFIG_SWAP */
805
806 static inline struct stat *
807 file_stat(struct file_priv *file)
808 {
809 return &file->s;
810 }
811
812 int
813 hed_file_update_size(struct hed_file *f)
814 {
815 struct file_priv *file = file_private(f);
816 hed_uoff_t oldsize = file->f.phys_size;
817
818 if(fstat(file->fd, file_stat(file)) < 0)
819 return -1;
820
821 if (S_ISBLK(file_stat(file)->st_mode)) {
822 if (ioctl(file->fd, BLKGETSIZE64, &file->f.phys_size)) {
823 unsigned long size_in_blocks;
824 if (ioctl(file->fd, BLKGETSIZE, &size_in_blocks))
825 return -1;
826 file->f.phys_size = (hed_uoff_t)size_in_blocks << 9;
827 }
828 } else if (S_ISREG(file_stat(file)->st_mode)) {
829 file->f.phys_size = file_stat(file)->st_size;
830 } else if (S_ISCHR(file_stat(file)->st_mode)) {
831 if (lseek(file->fd, 0, SEEK_SET) < 0)
832 return -1;
833 file->f.phys_size = (hed_uoff_t)OFF_MAX + 1;
834 } else {
835 errno = EINVAL;
836 return -1;
837 }
838
839 file->f.size += file->f.phys_size - oldsize;
840 return 0;
841 }
842
843 static int
844 do_file_open(struct file_priv *file)
845 {
846 file->fd = open(file->f.name, O_RDONLY);
847 if (file->fd < 0) {
848 if (errno != ENOENT)
849 return errno;
850 fprintf(stderr, "Warning: File %s does not exist\n",
851 file->f.name);
852 memset(file_stat(file), 0, sizeof(struct stat));
853
854 } else if (hed_file_update_size(&file->f)) {
855 int errsv = errno;
856 close(file->fd);
857 return errsv;
858 }
859 return 0;
860 }
861
862 static int
863 file_setup_blocks(struct file_priv *file)
864 {
865 hed_uoff_t phys_size = file->f.phys_size;
866 struct hed_block *block;
867
868 block = &file->terminal_block;
869 block->flags = HED_BLOCK_EXCACHE | HED_BLOCK_VIRTUAL
870 | HED_BLOCK_EOF | HED_BLOCK_TERMINAL;
871 INIT_LIST_HEAD(&block->lru);
872 INIT_LIST_HEAD(&block->refs);
873 block->t.maxoff = OFF_MAX - phys_size;
874 block->phys_pos = phys_size;
875
876 init_block_list(hed_file_blocks(file), block);
877
878 if (phys_size) {
879 block = new_virt_block(file, 0, phys_size, 0);
880 if (!block)
881 return -1;
882 recalc_chain_block(hed_file_blocks(file), block,
883 &file->terminal_block);
884 }
885
886 return 0;
887 }
888
889 int
890 libhed_init(void)
891 {
892 return file_access_init();
893 }
894
895 struct hed_file *
896 hed_open(const char *name)
897 {
898 struct file_priv *file = file_swp_init(name);
899
900 if (!file)
901 goto fail;
902
903 file->f.name = name;
904 INIT_LIST_HEAD(&file->lru);
905
906 file->cache = cache_init(CACHE_LENGTH, file_swp(file));
907 if (!file->cache)
908 goto fail_file;
909
910 if (do_file_open(file))
911 goto fail_file;
912
913 if (file_setup_blocks(file))
914 goto fail_file;
915
916 fixup_register(file);
917
918 return &file->f;
919
920 fail_file:
921 hed_close(&file->f);
922 fail:
923 return NULL;
924 }
925
926 void
927 hed_close(struct hed_file *f)
928 {
929 struct file_priv *file = file_private(f);
930 assert(file);
931
932 /* Do not check for errors:
933 * 1. This FD is read-only => no data loss possbile
934 * 2. We're about to exit anyway => no resource leak
935 */
936 if (file->fd >= 0)
937 close(file->fd);
938
939 fixup_deregister(file);
940
941 /* No need to free file blocks here, because all data is
942 * allocated either from the cache or from the swap file
943 * and both is going to be destroyed now.
944 */
945
946 if (file->cache)
947 cache_done(file->cache);
948
949 file_swp_done(file);
950 }
951
952 /* Adjust a cursor after off gets outside its block */
953 static void
954 fixup_cursor_slow(hed_cursor_t *curs)
955 {
956 struct hed_block *block = curs->block;
957 hed_uoff_t off = curs->off;
958
959 do {
960 if ((hed_off_t)off < 0) {
961 block = prev_block(block);
962 off += hed_block_size(block);
963 } else {
964 off -= hed_block_size(block);
965 block = next_block(block);
966 }
967 } while (!hed_block_is_terminal(block) && off > block->t.maxoff);
968
969 curs->block = block;
970 curs->off = off;
971 list_move(&curs->list, &block->refs);
972 }
973
974 /* Adjust a cursor if off gets outside its block.
975 * This is separate from fixup_cursor_slow, because it is supposed
976 * to be small enough to be inlined (which is a win, because most of
977 * the time no fixup has to be done, so the fast inlined path is used).
978 */
979 static inline void
980 fixup_cursor(hed_cursor_t *curs)
981 {
982 if (curs->off > curs->block->t.maxoff)
983 fixup_cursor_slow(curs);
984 }
985
986 hed_off_t
987 hed_move_relative(hed_cursor_t *curs, hed_off_t num)
988 {
989 hed_off_t newpos = curs->pos + num;
990 if (newpos < 0) {
991 newpos = num < 0 ? 0 : OFF_MAX;
992 num = newpos - curs->pos;
993 }
994 curs->pos = newpos;
995 curs->off += num;
996 fixup_cursor(curs);
997 return num;
998 }
999
1000 /* Relative move with no checking (and only by a small amount) */
1001 static inline void
1002 move_rel_fast(hed_cursor_t *curs, ssize_t num)
1003 {
1004 curs->off += num;
1005 curs->pos += num;
1006 fixup_cursor(curs);
1007 }
1008
1009 static void
1010 alloc_caches(struct file_priv *file, struct hed_block_data **caches, int n)
1011 {
1012 struct remap_control rc;
1013 int i;
1014
1015 BDEBUG("Allocate %d caches (%d free slots available)\n",
1016 n, file->cache->nfree);
1017
1018 assert(n <= CACHE_LENGTH);
1019 while (file->cache->nfree < n) {
1020 struct hed_block *block;
1021
1022 assert(!list_empty(&file->lru));
1023 block = list_entry(file->lru.next, struct hed_block, lru);
1024 BDEBUG("Killing block at physical %llx\n", block->phys_pos);
1025 kill_block(file, block);
1026 }
1027
1028 for (i = 0; i < n; ++i) {
1029 caches[i] = cache_alloc(file->cache);
1030 assert(caches[i]);
1031 }
1032
1033 remap_init(&rc);
1034 remap_compact(&rc, file->cache, caches, n);
1035 for (i = 0; i < n; ++i)
1036 remap_add(&rc, caches[i]->data);
1037 remap_finish(&rc);
1038 }
1039
1040 static inline void
1041 free_caches(struct file_priv *file, struct hed_block_data **preload, int n)
1042 {
1043 int i;
1044
1045 for (i = 0; i < n; ++i)
1046 if (preload[i])
1047 cache_put(file->cache, preload[i]);
1048 }
1049
1050 static int
1051 file_load_data(struct file_priv *file,
1052 struct hed_block_data **caches, int n,
1053 hed_uoff_t offset)
1054 {
1055 struct hed_block_data *dataobj = caches[0];
1056 void *data = dataobj->data;
1057 ssize_t rsize, total, segsize;
1058
1059 segsize = n << FILE_BLOCK_SHIFT;
1060 for (total = 0; total < segsize; total += rsize) {
1061 rsize = pread(file->fd, data + total,
1062 segsize - total, offset + total);
1063 if (!rsize) {
1064 memset(data + total, 0, segsize - total);
1065 break;
1066 }
1067 if (rsize < 0) {
1068 cache_put(file->cache,
1069 caches[total >> FILE_BLOCK_SHIFT]);
1070 caches[total >> FILE_BLOCK_SHIFT] = NULL;
1071 total = FILE_BLOCK_ROUND(total);
1072 rsize = FILE_BLOCK_SIZE;
1073 BDEBUG("Error reading block at phys %llx: %s\n",
1074 offset + total, strerror(errno));
1075 }
1076 }
1077
1078 BDEBUG("Loaded data at phys %llx up to %llx\n",
1079 offset, offset + segsize);
1080 return 0;
1081 }
1082
1083 #ifdef HED_CONFIG_MMAP
1084
1085 static int
1086 file_load_data_mmap(struct file_priv *file,
1087 struct hed_block_data **caches, int n,
1088 hed_uoff_t offset)
1089 {
1090 void *data;
1091 ssize_t segsize;
1092 int i;
1093
1094 segsize = n << FILE_BLOCK_SHIFT;
1095 data = mmap(NULL, segsize,
1096 PROT_READ | PROT_WRITE,
1097 MAP_PRIVATE | (file->fd < 0 ? MAP_ANONYMOUS : 0),
1098 file->fd, offset);
1099
1100 if (data == MAP_FAILED) {
1101 BDEBUG("mmap failed at %llx: fail over to traditional read\n",
1102 offset);
1103
1104 data = mmap(NULL, segsize,
1105 PROT_READ | PROT_WRITE,
1106 MAP_PRIVATE | MAP_ANONYMOUS,
1107 0, 0);
1108 if (data == MAP_FAILED)
1109 return -1;
1110
1111 for (i = 0; i < n; ++i)
1112 caches[i]->data = data + (i << FILE_BLOCK_SHIFT);
1113 return file_load_data(file, caches, n, offset);
1114 }
1115
1116 for (i = 0; i < n; ++i)
1117 caches[i]->data = data + (i << FILE_BLOCK_SHIFT);
1118
1119 BDEBUG("Loaded data at phys %llx up to %llx\n",
1120 offset, offset + segsize);
1121 return 0;
1122 }
1123 # define file_load_data file_load_data_mmap
1124
1125 #endif
1126
1127 /* Find the block with the lowest physical position that intersects
1128 * the loaded segment. The search starts at @block.
1129 */
1130 static struct hed_block *
1131 first_load_block(struct hed_block *block, hed_uoff_t segstart)
1132 {
1133 struct hed_block *prev = block;
1134 do {
1135 block = prev;
1136 prev = prev_block(prev);
1137 } while (!hed_block_is_terminal(prev) && phys_end(prev) > segstart);
1138 return block;
1139 }
1140
1141 static int
1142 load_blocks(struct file_priv *file, const hed_cursor_t *from)
1143 {
1144 hed_uoff_t physpos, segstart;
1145 struct hed_block_data *preload[FILE_READAHEAD];
1146 size_t ra_bkw, ra_fwd, ra_off;
1147 hed_cursor_t pos;
1148 int nblocks;
1149 int ret;
1150
1151 segstart = hed_cursor_phys_pos(from);
1152 ra_bkw = FILE_BLOCK_OFF(segstart);
1153 ra_fwd = FILE_BLOCK_SIZE - ra_bkw;
1154
1155 if (file_ra_forward(file))
1156 ra_fwd += (FILE_READAHEAD - 1) << FILE_BLOCK_SHIFT;
1157 else if (file_ra_backward(file))
1158 ra_bkw += (FILE_READAHEAD - 1) << FILE_BLOCK_SHIFT;
1159
1160 if (ra_bkw > segstart)
1161 ra_bkw = segstart;
1162 if (ra_fwd > file->f.phys_size - segstart)
1163 ra_fwd = file->f.phys_size - segstart;
1164
1165 segstart -= ra_bkw;
1166 ra_fwd += ra_bkw;
1167 pos.block = first_load_block(from->block, segstart);
1168 pos.off = segstart >= pos.block->phys_pos
1169 ? segstart - pos.block->phys_pos
1170 : 0;
1171
1172 list_add(&pos.list, &pos.block->refs);
1173 nblocks = ((ra_fwd - 1) >> FILE_BLOCK_SHIFT) + 1;
1174 alloc_caches(file, preload, nblocks);
1175 put_cursor(&pos);
1176
1177 ret = -1; /* be a pessimist */
1178 if (file_load_data(file, preload, nblocks, segstart))
1179 goto out;
1180
1181 while (physpos = hed_cursor_phys_pos(&pos),
1182 ra_off = physpos - segstart,
1183 ra_off < ra_fwd) {
1184 struct hed_block_data *dataobj;
1185 struct hed_block *newblock;
1186 size_t datalen;
1187
1188 if (!hed_block_is_virtual(pos.block)) {
1189 pos.block = next_block(pos.block);
1190 pos.off = 0;
1191 continue;
1192 }
1193
1194 datalen = FILE_BLOCK_SIZE - FILE_BLOCK_OFF(physpos);
1195 if (datalen > hed_block_size(pos.block) - pos.off)
1196 datalen = hed_block_size(pos.block) - pos.off;
1197
1198 dataobj = preload[ra_off >> FILE_BLOCK_SHIFT];
1199 newblock = dataobj
1200 ? new_data_block(file, physpos, datalen, dataobj)
1201 : new_virt_block(file, physpos, datalen,
1202 HED_BLOCK_BAD);
1203 if (!newblock)
1204 goto out;
1205
1206 /* Punch the new block */
1207 BDEBUG("Add %s block at %llx, length %llx\n",
1208 hed_block_is_virtual(newblock) ? "error" : "physical",
1209 newblock->phys_pos, hed_block_size(newblock));
1210 if (replace_chunk(file, pos.block, pos.off, newblock)) {
1211 file_free_block(file, newblock);
1212 goto out;
1213 }
1214
1215 pos.block = next_block(newblock);
1216 pos.off = 0;
1217 }
1218 ret = 0;
1219
1220 out:
1221 /* All cache objects now have an extra reference from the
1222 * allocation. Drop it. */
1223 free_caches(file, preload, nblocks);
1224
1225 dump_blocks(file);
1226 return ret;
1227 }
1228
1229 /* Shorten a block at beginning and enlarge the preceding block.
1230 *
1231 * Re-allocate at most @len bytes from the beginning of @block to the
1232 * end of the preceding block.
1233 * If @block is virtual, this will effectively devirtualize the range.
1234 * If @block is not virtual, this will change the backing store of
1235 * the bytes in the range.
1236 * Returns: the number of bytes actually moved.
1237 */
1238 static size_t
1239 shrink_at_begin(struct hed_block *block, size_t len, long state)
1240 {
1241 struct hed_block *prev;
1242 size_t maxgrow;
1243
1244 /* Basic assumptions */
1245 assert(!(state & HED_BLOCK_VIRTUAL));
1246
1247 /* The previous block must exist: */
1248 prev = prev_block(block);
1249 if (hed_block_is_terminal(prev))
1250 return 0;
1251
1252 /* The block flags must match the requested @state: */
1253 if ((prev->flags & HED_BLOCK_STATEMASK) != state)
1254 return 0;
1255
1256 /* No deletions at end, or similar: */
1257 if (prev->phys_pos + hed_block_size(prev) != block->phys_pos)
1258 return 0;
1259
1260 /* Append less bytes than requested if not all are available */
1261 assert(prev->t.maxoff < prev->dataobj->size - prev->dataoff);
1262 maxgrow = prev->dataobj->size - prev->dataoff - hed_block_size(prev);
1263 if (len > maxgrow)
1264 len = maxgrow;
1265 if (!len)
1266 return 0;
1267
1268 BDEBUG("Appending 0:%lx to the previous block\n", len);
1269
1270 /* Move cursors away from the to-be-chopped beginning */
1271 move_cursors(block, prev, 0, len - 1, hed_block_size(prev));
1272
1273 /* Enlarge the previous block */
1274 prev->t.maxoff += len;
1275 recalc_block_recursive(prev);
1276
1277 /* Shorten the original block */
1278 block->t.maxoff -= len;
1279 block->dataoff += len;
1280 block->phys_pos += len;
1281 recalc_block_recursive(block);
1282 return len;
1283 }
1284
1285 /* Shorten a block at end and enlarge the following block.
1286 *
1287 * Re-allocate at most @len bytes from the end of @block to the
1288 * beginning of the following block.
1289 * If @block is virtual, this will effectively devirtualize the range.
1290 * If @block is not virtual, this will change the backing store of
1291 * the bytes in the range.
1292 * Returns: the number of bytes actually moved.
1293 */
1294 static size_t
1295 shrink_at_end(struct hed_block *block, size_t len, long state)
1296 {
1297 struct hed_block *next;
1298 hed_uoff_t off;
1299
1300 /* Basic assumptions */
1301 assert(!(state & HED_BLOCK_VIRTUAL));
1302
1303 /* The next block must exist: */
1304 if (hed_block_is_terminal(block))
1305 return 0;
1306 next = next_block(block);
1307
1308 /* The block flags must match the requested @state: */
1309 if ((next->flags & HED_BLOCK_STATEMASK) != state)
1310 return 0;
1311
1312 /* No deletions at end, or similar: */
1313 if (block->phys_pos + hed_block_size(block) != next->phys_pos)
1314 return 0;
1315
1316 /* Prepend less bytes than requested if not all are available */
1317 if (len > next->dataoff)
1318 len = next->dataoff;
1319 if (!len)
1320 return 0;
1321 off = hed_block_size(block) - len;
1322
1323 BDEBUG("Prepending %llx:%lx to the next block\n", off, len);
1324
1325 /* Shift cursors in the new physical block */
1326 update_cursors(next, next, len);
1327
1328 /* Move cursors away from the to-be-chopped end */
1329 move_cursors(block, next, off, UOFF_MAX, -off);
1330
1331 /* Enlarge the next block */
1332 next->dataoff -= len;
1333 next->phys_pos -= len;
1334 next->t.maxoff += len;
1335 recalc_block_recursive(next);
1336
1337 /* Shorten the original block */
1338 block->t.maxoff -= len;
1339 recalc_block_recursive(block);
1340 return len;
1341 }
1342
1343 /* Search for an existing data object within the same physical block
1344 * as @curs, and having the given @state flags.
1345 */
1346 static struct hed_block_data *
1347 search_data(struct file_priv *file, const hed_cursor_t *curs, long state)
1348 {
1349 struct hed_block *block;
1350 hed_uoff_t physpos;
1351
1352 physpos = FILE_BLOCK_ROUND(curs->block->phys_pos + curs->off);
1353 BDEBUG("Search for already loaded data at %llx starting at %llx...",
1354 physpos, curs->block->phys_pos);
1355
1356 /* Search backwards */
1357 block = curs->block;
1358 while (!hed_block_is_terminal(block = prev_block(block))) {
1359 if (block->phys_pos < physpos)
1360 break;
1361 if ((block->flags & STATEMASK_SANS_EOF) == state) {
1362 BDEBUG(" found at %llx\n", block->phys_pos);
1363 assert(block->dataobj);
1364 return block->dataobj;
1365 }
1366 }
1367
1368 /* Search forwards */
1369 block = curs->block;
1370 while (!hed_block_is_terminal(block)) {
1371 block = next_block(block);
1372 if (block->phys_pos >= physpos + FILE_BLOCK_SIZE)
1373 break;
1374 if ((block->flags & STATEMASK_SANS_EOF) == state) {
1375 BDEBUG(" found at %llx\n", block->phys_pos);
1376 assert(block->dataobj);
1377 return block->dataobj;
1378 }
1379 }
1380
1381 BDEBUG(" not found\n");
1382 return NULL;
1383 }
1384
1385 static int
1386 reuse_loaded_data(struct file_priv *file, const hed_cursor_t *curs,
1387 struct hed_block_data *data)
1388 {
1389 struct hed_block *physblock;
1390 struct hed_block *block = curs->block;
1391 hed_uoff_t block_offset = curs->off;
1392 hed_uoff_t physpos = block->phys_pos + block_offset;
1393 size_t part = FILE_BLOCK_OFF(physpos);
1394 size_t len =
1395 FILE_BLOCK_SIZE - part <= hed_block_size(block) - block_offset
1396 ? FILE_BLOCK_SIZE - part
1397 : hed_block_size(block) - block_offset;
1398
1399 if (part > block_offset)
1400 part = block_offset;
1401 physpos -= part;
1402 len += part;
1403 block_offset -= part;
1404
1405 if (! (physblock = new_data_block(file, physpos, len, data)) )
1406 return -1;
1407
1408 BDEBUG("Add physical block at %llx, length %llx\n",
1409 physblock->phys_pos, hed_block_size(physblock));
1410 if (replace_chunk(file, block, block_offset, physblock)) {
1411 file_free_block(file, physblock);
1412 return -1;
1413 }
1414
1415 dump_blocks(file);
1416 return 0;
1417 }
1418
1419 /* Replace a part of a virtual block with content loaded
1420 * from disk. The amount of data loaded from the disk depends
1421 * on various factors with the goal to choose the most efficient
1422 * ratio. The only guarantee is that the byte at @curs will
1423 * be in a non-virtual block when this function returns 0.
1424 */
1425 static int
1426 devirtualize_clean(struct file_priv *file, const hed_cursor_t *curs)
1427 {
1428 struct hed_block *block = curs->block;
1429 hed_uoff_t block_offset = curs->off;
1430 hed_uoff_t remain = hed_block_size(block) - block_offset;
1431 struct hed_block_data *data;
1432
1433 BDEBUG("punch a clean hole at %llx into %llx:%llx\n", block_offset,
1434 block_offset(block), hed_block_size(block));
1435 assert(hed_block_is_virtual(block));
1436
1437 /* Check if we can combine with a neighbouring block */
1438 if (shrink_at_begin(block, hed_block_size(block), 0) > block_offset
1439 || shrink_at_end(block, hed_block_size(block), 0) >= remain) {
1440 kill_block_if_empty(file, block);
1441 dump_blocks(file);
1442 return 0;
1443 }
1444
1445 /* Check if the block is already loaded elsewhere */
1446 data = search_data(file, curs, 0);
1447 return data
1448 ? reuse_loaded_data(file, curs, data)
1449 : load_blocks(file, curs);
1450 }
1451
1452 /* Unles the block at @curs is already dirty, replace at most
1453 * @len bytes at @curs with a newly allocated out-of-cache block.
1454 * The block is marked dirty and its data is left uninitialized.
1455 * Note that this function may devirtualize less than @len bytes.
1456 * In the worst case only 1 byte at @curs will be available.
1457 */
1458 static int
1459 prepare_modify(struct file_priv *file, hed_cursor_t *curs, size_t len)
1460 {
1461 struct hed_block *block = curs->block;
1462 hed_uoff_t block_offset = curs->off;
1463 hed_uoff_t remain = hed_block_size(block) - block_offset;
1464 long newstate = HED_BLOCK_DIRTY | (block->flags & HED_BLOCK_EOF);
1465 struct hed_block *newblock;
1466
1467 if (hed_block_is_dirty(block))
1468 return 0;
1469
1470 if (len > remain)
1471 len = remain;
1472
1473 BDEBUG("punch a dirty hole at %llx:%lx into %llx:%llx\n",
1474 block_offset, len,
1475 block_offset(block), hed_block_size(block));
1476
1477 /* Check if we can combine with a neighbouring block */
1478 if ((block_offset == 0 &&
1479 shrink_at_begin(block, len, newstate)) ||
1480 (remain == len &&
1481 shrink_at_end(block, len, newstate) >= len)) {
1482 kill_block_if_empty(file, block);
1483 dump_blocks(file);
1484 return 0;
1485 }
1486
1487 /* Initialize a new block */
1488 newblock = new_block(file, HED_BLOCK_EXCACHE | newstate);
1489 if (!newblock)
1490 goto out_err;
1491
1492 /* Allocate data */
1493 if ( (newblock->dataobj = search_data(file, curs, HED_BLOCK_DIRTY)) )
1494 cache_get(newblock->dataobj);
1495 else if (! (newblock->dataobj = block_data_new(file->cache,
1496 FILE_BLOCK_SIZE)) )
1497 goto out_err_free;
1498
1499 newblock->phys_pos = block->phys_pos + block_offset;
1500 newblock->dataoff = FILE_BLOCK_OFF(newblock->phys_pos);
1501 if (len > FILE_BLOCK_SIZE - newblock->dataoff)
1502 len = FILE_BLOCK_SIZE - newblock->dataoff;
1503 newblock->t.maxoff = len - 1;
1504
1505 if (replace_chunk(file, block, block_offset, newblock))
1506 goto out_err_free;
1507
1508 dump_blocks(file);
1509 return 0;
1510
1511 out_err_free:
1512 file_free_block(file, newblock);
1513 out_err:
1514 return -1;
1515 }
1516
1517 /* Ensure that @curs points to an up-to-date non-virtual block.
1518 * Load the data from disk if necessary, return zero on failure. */
1519 size_t
1520 hed_prepare_read(struct hed_file *f, const hed_cursor_t *curs, size_t len)
1521 {
1522 struct file_priv *file = file_private(f);
1523 struct hed_block *block = curs->block;
1524 if (block_is_loadable(block) &&
1525 devirtualize_clean(file, curs) < 0)
1526 return 0;
1527
1528 return hed_cursor_chunk_len(curs, len);
1529 }
1530
1531 /* Move the block pointer to the next block */
1532 static struct hed_block *
1533 cursor_next_block(hed_cursor_t *curs)
1534 {
1535 struct hed_block *block = next_nonzero_block(curs->block);
1536
1537 if (block) {
1538 curs->block = block;
1539 curs->off = 0;
1540 list_move(&curs->list, &block->refs);
1541 }
1542 return block;
1543 }
1544
1545 /* Copy in @count bytes from @pos.
1546 * Returns the number of bytes that were not read (i.e. zero on success).
1547 * The @pos cursor is moved by the amount of data read.
1548 * CAUTION: If you read up to MAX_OFF, then @pos points one byte
1549 * beyond the EOF block upon return.
1550 */
1551 static size_t
1552 copy_in(struct file_priv *file, void *buf, size_t count, hed_cursor_t *pos)
1553 {
1554 size_t cpylen;
1555
1556 pos->pos += count;
1557 while (count && (cpylen = hed_prepare_read(&file->f, pos, count))) {
1558 if (hed_block_is_bad(pos->block))
1559 break;
1560 else if (hed_block_is_virtual(pos->block))
1561 memset(buf, 0, cpylen);
1562 else
1563 memcpy(buf, hed_cursor_data(pos), cpylen);
1564
1565 buf += cpylen;
1566 count -= cpylen;
1567 if ( (pos->off += cpylen) >= hed_block_size(pos->block) )
1568 if (!cursor_next_block(pos))
1569 break;
1570 }
1571 pos->pos -= count;
1572 return count;
1573 }
1574
1575 size_t
1576 hed_file_cpin(struct hed_file *file, void *buf, size_t count,
1577 const hed_cursor_t *pos)
1578 {
1579 hed_cursor_t mypos;
1580 size_t ret;
1581
1582 hed_dup_cursor(pos, &mypos);
1583 ret = copy_in(file_private(file), buf, count, &mypos);
1584 put_cursor(&mypos);
1585 return ret;
1586 }
1587
1588 /* Set the modified flag */
1589 static inline void
1590 set_modified(struct file_priv *file)
1591 {
1592 file->f.modified = true;
1593 }
1594
1595 /* Clear the modified flag */
1596 static inline void
1597 clear_modified(struct file_priv *file)
1598 {
1599 file->f.modified = false;
1600 }
1601
1602 int
1603 hed_file_set_byte(struct hed_file *f, hed_cursor_t *curs, unsigned char byte)
1604 {
1605 struct file_priv *file = file_private(f);
1606
1607 if (prepare_modify(file, curs, 1))
1608 return -1;
1609 set_modified(file);
1610
1611 hed_block_data(curs->block)[curs->off] = byte;
1612
1613 if (hed_block_is_terminal(next_block(curs->block)))
1614 file->f.size = curs->pos + 1;
1615
1616 return 0;
1617 }
1618
1619 size_t
1620 hed_file_set_block(struct hed_file *f, hed_cursor_t *curs,
1621 unsigned char *buf, size_t len)
1622 {
1623 struct file_priv *file = file_private(f);
1624 while (len) {
1625 size_t span;
1626
1627 if (prepare_modify(file, curs, len))
1628 break;
1629 set_modified(file);
1630
1631 span = hed_cursor_chunk_len(curs, len);
1632 memcpy(hed_cursor_data(curs), buf, span);
1633 buf += span;
1634 len -= span;
1635 move_rel_fast(curs, span);
1636 }
1637
1638 if (hed_block_is_terminal(curs->block))
1639 file->f.size = curs->pos;
1640
1641 return len;
1642 }
1643
1644 hed_uoff_t
1645 hed_file_set_bytes(struct hed_file *f, hed_cursor_t *curs,
1646 unsigned char byte, hed_uoff_t rep)
1647 {
1648 struct file_priv *file = file_private(f);
1649 while (rep) {
1650 size_t span;
1651
1652 if (prepare_modify(file, curs, rep))
1653 break;
1654 set_modified(file);
1655
1656 span = hed_cursor_chunk_len(curs, rep);
1657 memset(hed_cursor_data(curs), byte, span);
1658 rep -= span;
1659 move_rel_fast(curs, span);
1660 }
1661
1662 if (hed_block_is_terminal(curs->block))
1663 file->f.size = curs->pos;
1664
1665 return rep;
1666 }
1667
1668 static int
1669 file_erase_continuous(struct file_priv *file, hed_cursor_t *curs, size_t len)
1670 {
1671 struct hed_block *block = curs->block;
1672 hed_uoff_t block_offset = curs->off;
1673
1674 /* Find the new position */
1675 hed_move_relative(curs, len);
1676
1677 /* Move all other cursors in the erased range to the new position */
1678 assert(len > 0);
1679 move_cursors_abs(block, block_offset,
1680 block_offset + len - 1, curs);
1681
1682 if (!block_offset) {
1683 block->dataoff += len;
1684 if (!hed_block_is_inserted(block))
1685 block->phys_pos += len;
1686 } else if (block_offset + len <= block->t.maxoff) {
1687 block = split_block(file, block, block_offset + len);
1688 if (!block)
1689 return -1;
1690 }
1691
1692 move_cursors(block, block, block_offset, UOFF_MAX, -(hed_uoff_t)len);
1693
1694 block->t.maxoff -= len;
1695 recalc_block_recursive(block);
1696
1697 kill_block_if_empty(file, block);
1698 return 0;
1699 }
1700
1701 size_t
1702 hed_file_erase_block(struct hed_file *f, hed_cursor_t *curs, hed_uoff_t len)
1703 {
1704 struct file_priv *file = file_private(f);
1705 hed_uoff_t todo;
1706
1707 todo = len;
1708 while (!hed_block_is_terminal(curs->block) && todo) {
1709 size_t span = hed_cursor_chunk_len(curs, todo);
1710
1711 if (file_erase_continuous(file, curs, span))
1712 break;
1713
1714 todo -= span;
1715 }
1716 len -= todo;
1717
1718 file->f.size -= len;
1719 set_modified(file);
1720
1721 file->terminal_block.t.maxoff += len;
1722 recalc_block_recursive(&file->terminal_block);
1723
1724 struct hed_block *slideblock = prev_block(curs->block);
1725 if (hed_block_is_terminal(slideblock))
1726 slideblock = curs->block;
1727 slide_cursors(slideblock, curs->pos, -len);
1728
1729 return hed_block_is_terminal(curs->block) ? 0 : todo;
1730 }
1731
1732 /* Note that @curs may be detached from the block reference list
1733 * with put_cursor(). Only the pos, block and off fields are used.
1734 * This is an implementation detail currently required by
1735 * hed_file_insert_block(), which sets @curs and @curs_ins to the
1736 * same value. Other users of the library must not rely on it.
1737 */
1738 int
1739 hed_file_insert_begin(struct hed_file *f, const hed_cursor_t *curs,
1740 hed_cursor_t *curs_ins)
1741 {
1742 struct file_priv *file = file_private(f);
1743 struct hed_block *newblock;
1744
1745 BDEBUG("Starting insert at %llx\n", curs->pos);
1746
1747 newblock = new_block(file, (HED_BLOCK_EXCACHE |
1748 HED_BLOCK_INSERTED | HED_BLOCK_DIRTY |
1749 (curs->block->flags & HED_BLOCK_EOF)));
1750 if (!newblock)
1751 return -1;
1752
1753 newblock->t.maxoff = (hed_uoff_t)-1;
1754 newblock->phys_pos = hed_cursor_phys_pos(curs);
1755 newblock->dataobj = block_data_new(file->cache, FILE_BLOCK_SIZE);
1756 if (!newblock->dataobj) {
1757 file_free_block(file, newblock);
1758 return -1;
1759 }
1760
1761 if (curs->off && !split_block(file, curs->block, curs->off)) {
1762 file_free_block(file, newblock);
1763 return -1;
1764 }
1765
1766 chain_block(hed_file_blocks(file), newblock, curs->block);
1767
1768 curs_ins->pos = curs->pos;
1769 curs_ins->off = 0;
1770 curs_ins->block = newblock;
1771 list_add(&curs_ins->list, &newblock->refs);
1772
1773 dump_blocks(file);
1774 return 0;
1775 }
1776
1777 void
1778 hed_file_insert_end(struct hed_file *f, hed_cursor_t *curs_ins)
1779 {
1780 struct file_priv *file = file_private(f);
1781 struct hed_block *block = curs_ins->block;
1782
1783 BDEBUG("End insert at %llx\n", curs_ins->pos);
1784
1785 curs_ins->block = NULL;
1786 list_del(&curs_ins->list);
1787 if (!kill_block_if_empty(file, block))
1788 block_data_shrink(file->cache, block->dataobj,
1789 block->dataoff + hed_block_size(block));
1790
1791 dump_blocks(file);
1792 }
1793
1794 static void
1795 insert_block(struct file_priv *file, hed_cursor_t *curs,
1796 unsigned char *buf, size_t len)
1797 {
1798 struct hed_block *block = curs->block;
1799 hed_uoff_t offset = curs->pos;
1800
1801 assert(hed_block_is_excache(block));
1802 assert(hed_block_is_dirty(block));
1803 set_modified(file);
1804
1805 memcpy(hed_block_data(block) + curs->off, buf, len);
1806 block->t.maxoff += len;
1807 recalc_block_recursive(block);
1808 curs->off += len;
1809 curs->pos += len;
1810
1811 slide_cursors(next_block(block), offset, len);
1812 }
1813
1814 size_t
1815 hed_file_insert_block(struct hed_file *f, hed_cursor_t *curs,
1816 unsigned char *buf, size_t len)
1817 {
1818 struct file_priv *file = file_private(f);
1819 size_t todo = len;
1820 while (todo) {
1821 struct hed_block *block = curs->block;
1822 size_t remain;
1823
1824 remain = block->dataobj->size - block->dataoff - curs->off;
1825 if (!remain) {
1826 put_cursor(curs);
1827 curs->block = next_block(block);
1828 curs->off = 0;
1829
1830 if (hed_file_insert_begin(&file->f, curs, curs))
1831 break;
1832
1833 continue;
1834 }
1835
1836 if (remain > todo)
1837 remain = todo;
1838
1839 BDEBUG("Append %ld bytes to the insert block\n",
1840 (long) remain);
1841 insert_block(file, curs, buf, remain);
1842 buf += remain;
1843 todo -= remain;
1844 }
1845 len -= todo;
1846
1847 if (curs->pos > file->f.size)
1848 file->f.size = curs->pos;
1849 else
1850 file->f.size += len;
1851
1852 file->terminal_block.t.maxoff -= len;
1853 recalc_block_recursive(&file->terminal_block);
1854
1855 return todo;
1856 }
1857
1858 int
1859 hed_file_insert_byte(struct hed_file *file, hed_cursor_t *curs,
1860 unsigned char byte)
1861 {
1862 return hed_file_insert_block(file, curs, &byte, 1);
1863 }
1864
1865 size_t
1866 hed_file_insert_once(struct hed_file *file, hed_cursor_t *curs,
1867 unsigned char *buf, size_t len)
1868 {
1869 hed_cursor_t insert;
1870
1871 if (!hed_file_insert_begin(file, curs, &insert)) {
1872 len = hed_file_insert_block(file, &insert, buf, len);
1873 hed_file_insert_end(file, &insert);
1874 }
1875 return len;
1876 }
1877
1878 struct commit_control {
1879 struct file_priv *file;
1880 int wfd; /* file descriptor for writing */
1881 hed_cursor_t begoff, endoff;
1882 void *buffer; /* write buffer (one block) */
1883 };
1884
1885 static ssize_t
1886 commit_write(struct commit_control *cc, hed_uoff_t pos, ssize_t len)
1887 {
1888 BDEBUG(" -> write %lx bytes at %llx\n",
1889 (unsigned long)len, pos);
1890 return pwrite(cc->wfd, cc->buffer, len, pos);
1891 }
1892
1893 /* Commit forwards. */
1894 static int
1895 commit_forwards(struct commit_control *cc)
1896 {
1897 int ret = 0;
1898
1899 BDEBUG("Writing forwards %llx-%llx\n",
1900 cc->begoff.pos, cc->endoff.pos);
1901
1902 while (cc->begoff.pos < cc->endoff.pos) {
1903 size_t left;
1904 ssize_t written;
1905
1906 left = copy_in(cc->file, cc->buffer,
1907 FILE_BLOCK_SIZE, &cc->begoff);
1908 if (left) {
1909 move_rel_fast(&cc->begoff, left);
1910 ret = -1;
1911 continue;
1912 }
1913
1914 written = commit_write(cc, cc->begoff.pos - FILE_BLOCK_SIZE,
1915 FILE_BLOCK_SIZE);
1916 if (written < FILE_BLOCK_SIZE)
1917 ret = -1;
1918 }
1919
1920 return ret;
1921 }
1922
1923 /* Commit backwards. */
1924 static int
1925 commit_backwards(struct commit_control *cc)
1926 {
1927 hed_cursor_t curs;
1928 int ret = 0;
1929
1930 BDEBUG("Writing backwards %llx-%llx\n",
1931 cc->begoff.pos, cc->endoff.pos);
1932
1933 hed_dup_cursor(&cc->endoff, &curs);
1934 while (curs.pos > cc->begoff.pos) {
1935 size_t left;
1936 ssize_t written;
1937
1938 move_rel_fast(&curs, -FILE_BLOCK_SIZE);
1939 left = hed_file_cpin(&cc->file->f, cc->buffer,
1940 FILE_BLOCK_SIZE, &curs);
1941 if (left) {
1942 ret = -1;
1943 continue;
1944 }
1945
1946 written = commit_write(cc, curs.pos, FILE_BLOCK_SIZE);
1947 if (written < FILE_BLOCK_SIZE)
1948 ret = -1;
1949 }
1950 hed_put_cursor(&curs);
1951
1952 return ret;
1953 }
1954
1955 /* Return the number of clean bytes following @curs.
1956 * Usage note: the caller must ensure that the starting position
1957 * is clean.
1958 */
1959 static hed_uoff_t
1960 clean_span(hed_cursor_t *curs)
1961 {
1962 hed_uoff_t next_pos;
1963 struct hed_block *block = curs->block;
1964 hed_uoff_t ret = -curs->off;
1965
1966 assert(!hed_block_is_dirty(block));
1967
1968 do {
1969 ret += hed_block_size(block);
1970 next_pos = block->phys_pos + hed_block_size(block);
1971 block = next_nonzero_block(block);
1972 } while (block->phys_pos == next_pos && /* no insertions, deletions */
1973 !hed_block_is_dirty(block) && /* no modifications */
1974 !hed_block_is_terminal(block));
1975 return ret;
1976 }
1977
1978 static void
1979 undirty_blocks(struct file_priv *file)
1980 {
1981 struct hed_block *block, *next;
1982 hed_uoff_t pos = 0;
1983
1984 BDEBUG("Undirtying blocks:\n");
1985 dump_blocks(file);
1986
1987 next = first_block(file);
1988 while (!hed_block_is_terminal(next)) {
1989 block = next;
1990 next = next_block(block);
1991
1992 if (kill_block_if_empty(file, block))
1993 continue;
1994
1995 if (!hed_block_is_virtual(block)) {
1996 cache_put(file->cache, block->dataobj);
1997 block->dataobj = NULL;
1998 list_del_init(&block->lru);
1999 block->flags = HED_BLOCK_EXCACHE | HED_BLOCK_VIRTUAL;
2000 }
2001
2002 block->phys_pos = pos;
2003 pos += hed_block_size(block);
2004 }
2005
2006 block = first_block(file);
2007 while (!hed_block_is_terminal(block)) {
2008 next = next_block(block);
2009 kill_block(file, block);
2010 block = next;
2011 }
2012
2013 BDEBUG("After undirtying\n");
2014 dump_blocks(file);
2015 }
2016
2017 static int
2018 commit_init(struct commit_control *cc, struct file_priv *file)
2019 {
2020 cc->file = file;
2021 cc->buffer = malloc(FILE_BLOCK_SIZE);
2022 if (!cc->buffer)
2023 goto err;
2024
2025 if (file->fd < 0) {
2026 file->fd = open(file->f.name, O_RDONLY | O_CREAT, 0666);
2027 if (file->fd < 0)
2028 goto err_free;
2029 }
2030
2031 cc->wfd = open(file->f.name, O_WRONLY);
2032 if (cc->wfd < 0)
2033 goto err_free;
2034
2035 return 0;
2036
2037 err_free:
2038 free(cc->buffer);
2039 err:
2040 return -1;
2041 }
2042
2043 int
2044 hed_file_commit(struct hed_file *f)
2045 {
2046 struct file_priv *file = file_private(f);
2047 struct commit_control cc;
2048 hed_off_t shift;
2049 int ret = 0;
2050
2051 if (commit_init(&cc, file))
2052 return -1;
2053
2054 dump_blocks(file);
2055
2056 get_cursor(file, 0,&cc.begoff);
2057 hed_dup_cursor(&cc.begoff, &cc.endoff);
2058 shift = -cc.begoff.block->phys_pos;
2059 while(!hed_block_is_terminal(cc.endoff.block)) {
2060 hed_uoff_t skip;
2061 hed_off_t newshift;
2062
2063 if (!shift && !hed_block_is_dirty(cc.endoff.block)) {
2064 skip = FILE_BLOCK_ROUND(clean_span(&cc.endoff));
2065 if (skip) {
2066 ret |= commit_forwards(&cc);
2067
2068 BDEBUG("Skipping %llx-%llx\n",
2069 cc.endoff.pos, cc.endoff.pos + skip);
2070 hed_move_relative(&cc.endoff, skip);
2071 hed_dup2_cursor(&cc.endoff, &cc.begoff);
2072 continue;
2073 }
2074 }
2075
2076 skip = FILE_BLOCK_ROUND(hed_cursor_span(&cc.endoff));
2077 hed_move_relative(&cc.endoff, skip ?: FILE_BLOCK_SIZE);
2078
2079 newshift = !hed_block_is_eof(cc.endoff.block)
2080 ? cc.endoff.pos - hed_cursor_phys_pos(&cc.endoff)
2081 : 0;
2082
2083 if (shift <= 0 && newshift > 0) {
2084 move_rel_fast(&cc.endoff, -FILE_BLOCK_SIZE);
2085 ret |= commit_forwards(&cc);
2086 hed_dup2_cursor(&cc.endoff, &cc.begoff);
2087 } else if (shift > 0 && newshift <= 0) {
2088 ret |= commit_backwards(&cc);
2089 hed_dup2_cursor(&cc.endoff, &cc.begoff);
2090 }
2091 shift = newshift;
2092 }
2093 assert(cc.endoff.pos >= hed_file_size(&file->f));
2094
2095 ret |= commit_forwards(&cc);
2096 put_cursor(&cc.begoff);
2097 put_cursor(&cc.endoff);
2098
2099 ftruncate(cc.wfd, hed_file_size(&file->f));
2100 file->f.phys_size = hed_file_size(&file->f);
2101
2102 ret |= close(cc.wfd);
2103 free(cc.buffer);
2104
2105 undirty_blocks(file);
2106
2107 if (!ret)
2108 clear_modified(file);
2109
2110 return ret;
2111 }
2112
2113 #ifdef HED_CONFIG_SWAP
2114 int
2115 hed_file_write_swap(struct hed_file *file)
2116 {
2117 return swp_write(file_swp(file_private(file)));
2118 }
2119
2120 static int
2121 do_read_swap(struct file_priv *file, struct swp_file *swp, hed_cursor_t *pos)
2122 {
2123 struct file_priv *swpfile = swp_private(swp);
2124 struct hed_block *cur, block;
2125 hed_uoff_t phys_pos;
2126
2127 if (file_stat(swpfile)->st_size != file_stat(file)->st_size ||
2128 file_stat(swpfile)->st_mtime != file_stat(file)->st_mtime) {
2129 fprintf(stderr, "stat info mismatch (you modified the file since hed ran on it; refusing to touch it)\n");
2130 return -1;
2131 }
2132
2133 BDEBUG("Swap header match\n");
2134
2135 phys_pos = 0;
2136 cur = first_block(swpfile);
2137 do {
2138 struct hed_block_data dataobj;
2139 size_t (*mergefn)(struct hed_file*, hed_cursor_t*,
2140 unsigned char*, size_t);
2141 void *data;
2142 size_t res;
2143
2144 if (swp_cpin(swp, &block, cur, sizeof(struct hed_block))) {
2145 perror("Cannot read block descriptor");
2146 return -1;
2147 }
2148 BDEBUG("BLOCK %p: flags %02lx phys 0x%02llx size 0x%llx\n",
2149 cur, block.flags, (long long)block.phys_pos,
2150 (long long)hed_block_size(&block));
2151
2152 if (block.phys_pos - phys_pos) {
2153 if (hed_file_erase_block(&file->f, pos,
2154 block.phys_pos - phys_pos)) {
2155 perror("Cannot erase");
2156 return -1;
2157 }
2158 phys_pos = block.phys_pos;
2159 }
2160
2161 if (!hed_block_is_inserted(&block))
2162 phys_pos += hed_block_size(&block);
2163
2164 if (!hed_block_is_dirty(&block)) {
2165 hed_move_relative(pos, hed_block_size(&block));
2166 continue;
2167 }
2168
2169 if (swp_cpin(swp, &dataobj, block.dataobj,
2170 sizeof(struct hed_block_data))) {
2171 perror("Cannot read data descriptor");
2172 return -1;
2173 }
2174 BDEBUG("DATA %p: size 0x%lx\n",
2175 block.dataobj, (long)dataobj.size);
2176
2177 if (! (data = malloc(hed_block_size(&block))) ) {
2178 perror("Cannot allocate data");
2179 return -1;
2180 }
2181
2182 if (swp_cpin(swp, data, dataobj.data + block.dataoff,
2183 hed_block_size(&block))) {
2184 perror("Cannot read data");
2185 return -1;
2186 }
2187
2188 mergefn = hed_block_is_inserted(&block)
2189 ? hed_file_insert_once
2190 : hed_file_set_block;
2191 res = mergefn(&file->f, pos, data, hed_block_size(&block));
2192 free(data);
2193 if (res) {
2194 perror("Cannot merge data");
2195 return -1;
2196 }
2197 } while (cur = next_block(&block), !hed_block_is_terminal(&block));
2198
2199 dump_blocks(file);
2200 return 0;
2201 }
2202
2203 int
2204 hed_file_read_swap(struct hed_file *f)
2205 {
2206 struct file_priv *file = file_private(f);
2207 struct swp_file *swp;
2208 hed_cursor_t pos;
2209 int ret;
2210
2211 if (! (swp = swp_init_read(file->swpname)) )
2212 return -1;
2213
2214 get_cursor(file, 0, &pos);
2215 ret = do_read_swap(file, swp, &pos);
2216 put_cursor(&pos);
2217
2218 swp_done(swp);
2219 return ret;
2220 }
2221
2222 #else
2223
2224 int
2225 hed_file_write_swap(struct hed_file *file)
2226 {
2227 return 0;
2228 }
2229
2230 int
2231 hed_file_read_swap(struct hed_file *file)
2232 {
2233 return -1;
2234 }
2235
2236 #endif /* HED_CONFIG_SWAP */
2237
2238 /* Check if the search string is all zero */
2239 static bool
2240 is_allzero(unsigned char *s, size_t len)
2241 {
2242 while (len--)
2243 if (*s++)
2244 return false;
2245 return true;
2246 }
2247
2248 static void
2249 reverse(unsigned char *p, size_t len)
2250 {
2251 unsigned char *q = p + len;
2252 while (p < q) {
2253 unsigned char x = *p;
2254 *p++ = *--q;
2255 *q = x;
2256 }
2257 }
2258
2259 static void
2260 compute_badchar(ssize_t *badchar, const unsigned char *s, ssize_t len)
2261 {
2262 size_t i = 1;
2263 while (i < len)
2264 badchar[*s++] = i++;
2265 }
2266
2267 static void
2268 compute_sfx(ssize_t *sfx, const unsigned char *s, ssize_t len)
2269 {
2270 ssize_t f, g, i;
2271
2272 sfx[len - 1] = len;
2273 f = 0; /* bogus assignment to silence a warning */
2274 g = len - 1;
2275 for (i = len - 2; i >= 0; --i) {
2276 if (i > g && sfx[i + len - 1 - f] < i - g)
2277 sfx[i] = sfx[i + len - 1 - f];
2278 else {
2279 if (i < g)
2280 g = i;
2281 f = i;
2282 while (g >= 0 && s[g] == s[g + len - 1 - f])
2283 --g;
2284 sfx[i] = f - g;
2285 }
2286 }
2287 }
2288
2289 static void
2290 compute_goodsfx(ssize_t *goodsfx, const unsigned char *s, ssize_t len)
2291 {
2292 ssize_t i, j, *sfx = goodsfx + len;
2293
2294 compute_sfx(sfx, s, len);
2295
2296 for (i = 0; i < len; ++i)
2297 goodsfx[i] = len;
2298 j = 0;
2299 for (i = len - 1; i >= 0; --i)
2300 if (sfx[i] == i + 1)
2301 for (; j < len - 1 - i; ++j)
2302 if (goodsfx[j] == len)
2303 goodsfx[j] = len - 1 - i;
2304 for (i = 0; i <= len - 2; ++i)
2305 goodsfx[len - 1 - sfx[i]] = len - 1 - i;
2306 }
2307
2308 /* Search for a constant byte string using the Boyer-Moore algorithm. */
2309 static inline unsigned char*
2310 search_buf(unsigned char *buf, size_t buflen, unsigned char *needle,
2311 size_t maxidx, ssize_t *badchar, ssize_t *goodsfx)
2312 {
2313 if (!maxidx)
2314 return memchr(buf, *needle, buflen);
2315
2316 while (buflen > maxidx) {
2317 unsigned char *p;
2318 size_t i;
2319 ssize_t shift;
2320
2321 for (p = buf + maxidx, i = maxidx; p >= buf; --p, --i)
2322 if (needle[i] != *p)
2323 break;
2324 if (p < buf)
2325 return buf;
2326
2327 shift = i + 1 - badchar[*p];
2328 if (shift < goodsfx[i])
2329 shift = goodsfx[i];
2330
2331 buf += shift;
2332 buflen -= shift;
2333 }
2334 return NULL;
2335 }
2336
2337 /* Search for a constant byte string backwards. */
2338 static inline unsigned char*
2339 search_buf_rev(unsigned char *buf, size_t buflen, unsigned char *needle,
2340 size_t maxidx, ssize_t *badchar, ssize_t *goodsfx)
2341 {
2342 if (!maxidx)
2343 return memrchr(buf, *needle, buflen);
2344
2345 buf += buflen - maxidx - 1;
2346 while (buflen > maxidx) {
2347 unsigned char *p;
2348 size_t i;
2349 ssize_t shift;
2350
2351 for (p = buf, i = maxidx; p <= buf + maxidx; ++p, --i)
2352 if (needle[i] != *p)
2353 break;
2354 if (p > buf + maxidx)
2355 return buf;
2356
2357 shift = i + 1 - badchar[*p];
2358 if (shift < goodsfx[i])
2359 shift = goodsfx[i];
2360
2361 buf -= shift;
2362 buflen -= shift;
2363 }
2364 return NULL;
2365 }
2366
2367 /* Search for a constant byte string using the Boyer-Moore algorithm. */
2368 static int
2369 find_bytestr(struct file_priv *file, hed_cursor_t *from, int dir,
2370 unsigned char *needle, size_t len)
2371 {
2372 void *dynalloc;
2373 ssize_t *badchar, *goodsfx;
2374 unsigned char *readbuf;
2375 unsigned char *p, *q;
2376 size_t remain;
2377 bool allzero;
2378 int ret;
2379
2380 if (len > 1) {
2381 dynalloc = calloc(sizeof(ssize_t) * (256 + 2*len)
2382 + 2*(len-1), 1);
2383 if (!dynalloc)
2384 return HED_FINDOFF_ERROR;
2385 badchar = dynalloc;
2386 goodsfx = badchar + 256;
2387 readbuf = dynalloc + sizeof(ssize_t) * (256 + 2*len);
2388
2389 if (dir < 0)
2390 reverse(needle, len);
2391 compute_badchar(badchar, needle, len);
2392 compute_goodsfx(goodsfx, needle, len);
2393 } else {
2394 dynalloc = NULL;
2395 badchar = goodsfx = NULL;
2396 readbuf = NULL;
2397 }
2398
2399 assert(!hed_block_is_terminal(from->block));
2400
2401 allzero = is_allzero(needle, len);
2402 --len; /* simplify offset computing */
2403
2404 ret = HED_FINDOFF_NO_MATCH;
2405 if (dir < 0) {
2406 remain = -len;
2407 while (move_rel_fast(from, -remain),
2408 ret && from->pos >= len) {
2409
2410 if (!hed_prepare_read(&file->f, from, SIZE_MAX)) {
2411 ret = HED_FINDOFF_ERROR;
2412 break;
2413 }
2414 remain = from->off;
2415
2416 if (remain < len) {
2417 remain += len;
2418 if (remain > from->pos)
2419 remain = from->pos;
2420 move_rel_fast(from, -remain);
2421 ++remain;
2422 if (hed_file_cpin(&file->f, readbuf,
2423 remain, from)) {
2424 remain = -len + 1;
2425 continue;
2426 }
2427 p = readbuf;
2428 } else if (!hed_block_is_virtual(from->block)) {
2429 p = from->block->dataobj->data +
2430 from->block->dataoff;
2431 from->off -= remain;
2432 from->pos -= remain;
2433 ++remain;
2434 } else if (!hed_block_is_bad(from->block) && allzero) {
2435 ret = 0;
2436 remain = len;
2437 continue;
2438 } else {
2439 ++remain;
2440 continue;
2441 }
2442
2443 q = search_buf_rev(p, remain, needle, len,
2444 badchar, goodsfx);
2445 if (q) {
2446 ret = 0;
2447 remain = p - q;
2448 } else
2449 remain = -len + 1;
2450 }
2451 } else {
2452 for ( ; ret && !hed_block_is_terminal(from->block);
2453 move_rel_fast(from, remain)) {
2454
2455 remain = hed_prepare_read(&file->f, from, SIZE_MAX);
2456 if (!remain) {
2457 ret = HED_FINDOFF_ERROR;
2458 break;
2459 }
2460
2461 if (remain <= len) {
2462 remain += len;
2463 remain = copy_in(file, readbuf, remain, from);
2464 if (remain) {
2465 remain -= len;
2466 continue;
2467 }
2468 p = readbuf;
2469 } else if (!hed_block_is_virtual(from->block)) {
2470 p = from->block->dataobj->data +
2471 from->block->dataoff + from->off;
2472 from->off += remain;
2473 from->pos += remain;
2474 } else if (!hed_block_is_bad(from->block) && allzero) {
2475 ret = 0;
2476 remain = 0;
2477 continue;
2478 } else {
2479 remain -= len;
2480 continue;
2481 }
2482
2483 q = search_buf(p, remain, needle, len,
2484 badchar, goodsfx);
2485 if (q) {
2486 ret = 0;
2487 remain = q - p - remain;
2488 } else
2489 remain = -len;
2490 }
2491 }
2492
2493 if (dynalloc)
2494 free(dynalloc);
2495 return ret;
2496 }
2497
2498 static int
2499 find_expr(struct file_priv *file, hed_cursor_t *from, int dir,
2500 struct hed_expr *expr)
2501 {
2502 size_t len = hed_expr_len(expr);
2503 unsigned char *buf;
2504
2505 if (!len)
2506 return HED_FINDOFF_NO_MATCH;
2507
2508 for (;;) {
2509 hed_cursor_t match;
2510 size_t remain;
2511 unsigned char *p;
2512 size_t pos;
2513
2514 if (hed_expr_eval(expr) & HED_AEF_ERROR)
2515 return HED_FINDOFF_ERROR;
2516 buf = hed_expr_buf(expr);
2517
2518 hed_dup_cursor(from, &match);
2519 p = NULL; /* bogus assignment to silence a warning */
2520 remain = 0;
2521 for (pos = 0; pos < len; pos++) {
2522 if (!remain) {
2523 remain = hed_prepare_read(&file->f, &match,
2524 SIZE_MAX);
2525 if (!remain ||
2526 hed_block_is_bad(match.block))
2527 break;
2528 p = hed_cursor_data(&match);
2529 cursor_next_block(&match);
2530 }
2531 if ((p ? *p++ : 0) != buf[pos])
2532 break;
2533 remain--;
2534 }
2535 put_cursor(&match);
2536
2537 if (pos == len)
2538 return 0;
2539 if (!remain)
2540 return HED_FINDOFF_ERROR;
2541
2542 if (dir < 0 && hed_block_is_terminal(from->block)) {
2543 from->pos -= from->off;
2544 from->off = 0;
2545 }
2546 move_rel_fast(from, dir);
2547 if (hed_block_is_terminal(from->block))
2548 break;
2549
2550 if (! (hed_expr_flags(expr) & HED_AEF_DYNAMIC) )
2551 return find_bytestr(file, from, dir, buf, len);
2552 }
2553
2554 return HED_FINDOFF_NO_MATCH;
2555 }
2556
2557 int
2558 hed_file_find_expr(struct hed_file *f, hed_cursor_t *pos, int dir,
2559 struct hed_expr *expr)
2560 {
2561 struct file_priv *file = file_private(f);
2562 int res;
2563
2564 assert(dir == 1 || dir == -1);
2565
2566 set_readahead(file, dir > 0 ? HED_RA_FORWARD : HED_RA_BACKWARD);
2567 res = find_expr(file, pos, dir, expr);
2568 set_readahead(file, HED_RA_NONE);
2569
2570 return res;
2571 }
Fast hexadecimal editor