4 * hed - Hexadecimal editor
5 * Copyright (C) 2004 Petr Baudis <pasky@ucw.cz>
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.
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.
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
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.
32 /* Feature macros needed for:
47 #include <sys/ioctl.h>
49 #include <linux/fs.h> /* BLKGETSIZE and BLKGETSIZE64 */
52 #include "file_priv.h"
59 /* memrchr() might not be available */
62 #endif /* HAVE_MEMRCHR */
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.'
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. */
76 #define BDEBUG(x...) fprintf(stderr, x)
81 /* Number of blocks in cache */
82 #define CACHE_LENGTH 64
84 /* Blocks for readahead */
85 #define FILE_READAHEAD (CACHE_LENGTH/2)
87 /* Searches for data object don't care about the EOF flag */
88 #define STATEMASK_SANS_EOF (HED_BLOCK_STATEMASK & ~HED_BLOCK_EOF)
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)
95 #define block_offset(b) tree_block_offset(&(b)->t)
97 #define recalc_block_recursive(b) recalc_node_recursive(&(b)->t)
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)); \
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)
108 #define init_block_list(tree,b) init_tree(tree, &(b)->t)
109 #define init_block_link(b) init_node(&(b)->t)
111 #define find_block(tree,o) tree_entry(find_in_tree((tree),(o)),struct hed_block,t)
113 #define block_is_loadable(b) \
114 (((b)->flags & (HED_BLOCK_VIRTUAL | HED_BLOCK_EOF | HED_BLOCK_BAD)) \
115 == HED_BLOCK_VIRTUAL)
117 #ifdef HED_CONFIG_SWAP
119 /* Return the swp file object */
120 static inline struct swp_file
*
121 file_swp(struct file_priv
*file
)
128 /* Provide a stub for the non-swap case */
130 file_swp(struct file_priv
*file
)
137 #ifdef HED_CONFIG_READAHEAD
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)
144 set_readahead(struct file_priv
*file
, int val
)
146 file
->readahead
= val
;
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)
156 #endif /* HED_CONFIG_READAHEAD */
159 hed_file_set_readahead(struct hed_file
*file
, enum hed_readahead val
)
161 set_readahead(file_private(file
), val
);
165 shrink_block(struct hed_block
*block
, hed_uoff_t amount
)
167 block
->t
.maxoff
-= amount
;
168 if (!hed_block_size(block
))
169 hed_block_set_empty(block
);
170 recalc_block_recursive(block
);
173 /* Get the physical offset of the byte immediately following @block. */
174 static inline hed_uoff_t
175 phys_end(const struct hed_block
*block
)
177 return hed_block_is_inserted(block
)
179 : block
->phys_pos
+ hed_block_size(block
);
182 static struct hed_block
*
183 next_nonzero_block(struct hed_block
*block
)
185 while (!hed_block_is_terminal(block
)) {
186 block
= next_block(block
);
187 if (!hed_block_is_empty(block
))
193 static struct hed_block
*
194 prev_nonzero_block(struct hed_block
*block
)
197 block
= prev_block(block
);
198 if (hed_block_is_terminal(block
))
200 } while (hed_block_is_empty(block
));
205 hed_block_is_after_erase(struct hed_block
*block
)
207 struct hed_block
*prev
= prev_nonzero_block(block
);
209 ? block
->phys_pos
> phys_end(prev
)
214 hed_block_is_after_insert(struct hed_block
*block
)
216 struct hed_block
*prev
= prev_nonzero_block(block
);
217 return prev
&& hed_block_is_inserted(prev
);
220 /* Get the blocks tree */
221 static inline struct hed_tree
*
222 hed_file_blocks(struct file_priv
*file
)
224 return &file
->blocks
;
228 # define dump_blocks(file) {}
232 block_phys_size(struct hed_block
*block
)
234 struct hed_block
*next
;
236 if (hed_block_is_terminal(block
))
238 next
= next_block(block
);
239 return next
->phys_pos
- block
->phys_pos
;
243 dump_block(int level
, struct file_priv
*file
, struct hed_tree_node
*node
,
244 hed_uoff_t
*cur_offset
, hed_uoff_t
*cur_poffset
)
246 struct hed_block
*block
= tree_entry(node
, struct hed_block
, t
);
253 dump_block(level
+ 1, file
, node
->left
, cur_offset
, cur_poffset
);
254 p
= hed_block_data(block
);
256 if (p
&& !hed_block_is_empty(block
)) {
257 if (node
->maxoff
>= 0)
258 dp
+= snprintf(dp
, 3, "%02x", p
[0]);
259 if (node
->maxoff
>= 1)
260 dp
+= snprintf(dp
, 3, "%02x", p
[1]);
261 if (node
->maxoff
>= 2)
262 dp
+= snprintf(dp
, 3, "%02x", p
[2]);
263 if (node
->maxoff
>= 3)
264 dp
+= snprintf(dp
, 3, "%02x", p
[3]);
266 memset(dp
, ' ', sizeof(data
) - (dp
- data
));
269 if (level
< 20) t
[level
] = '>'; else t
[19] = '.';
270 fprintf(stderr
, "%s [%06llx] [%06llx] %c%c%c%c%c %05llx %05llx"
271 " {%s} -- %p ^%p [%06llx]\n",
273 (unsigned long long) *cur_offset
,
274 (unsigned long long) *cur_poffset
,
275 hed_block_is_bad(block
) ? 'b' : ' ',
276 hed_block_is_eof(block
) ? 'e' : ' ',
277 hed_block_is_virtual(block
) ? 'v' : ' ',
278 hed_block_is_inserted(block
) ? 'i' : ' ',
279 hed_block_is_dirty(block
) ? '*' : ' ',
280 (unsigned long long) node
->maxoff
+ 1,
281 (unsigned long long) block_phys_size(block
),
284 (unsigned long long) node
->cover_size
286 list_for_each_entry (cur
, &block
->refs
, list
) {
287 fprintf(stderr
, " <%p>: %llx->%p:%llx\n",
288 cur
, (long long)cur
->pos
,
289 cur
->block
, (unsigned long long)cur
->off
);
291 assert(*cur_poffset
== block
->phys_pos
);
292 *cur_offset
+= node
->maxoff
+ 1;
293 *cur_poffset
+= block_phys_size(block
);
295 dump_block(level
+ 1, file
, node
->right
, cur_offset
, cur_poffset
);
296 assert(node
->cover_size
== (node
->left
? node
->left
->cover_size
: 0)
297 + (node
->right
? node
->right
->cover_size
: 0)
301 /* Walk the tree manually here, because foreach_block() does not provide
302 * the tree structure.
303 * TODO: Change this if you plan to debug any other block containers.
306 dump_blocks(struct file_priv
*file
)
308 struct hed_block
*first
= first_block(file
);
309 hed_uoff_t cur_offset
, cur_poffset
;
311 fprintf(stderr
, "-- blocks dump --\n");
313 cur_poffset
= first
->phys_pos
;
314 dump_block(0, file
, hed_file_blocks(file
)->root
,
315 &cur_offset
, &cur_poffset
);
316 fprintf(stderr
, "-- blocks dump end --\n");
321 get_cursor(struct file_priv
*file
, hed_uoff_t offset
, hed_cursor_t
*curs
)
323 struct hed_block
*block
;
325 block
= find_block(hed_file_blocks(file
), offset
);
326 assert(block
!= NULL
);
329 curs
->off
= offset
- block_offset(block
);
330 list_add(&curs
->list
, &block
->refs
);
332 BDEBUG("Mapped %llx to %llx+%llx/%llx\n",
333 offset
, offset
- curs
->off
, curs
->off
, hed_block_size(block
));
337 hed_get_cursor(struct hed_file
*file
, hed_uoff_t offset
, hed_cursor_t
*curs
)
339 get_cursor(file_private(file
), offset
, curs
);
343 put_cursor(hed_cursor_t
*curs
)
345 list_del(&curs
->list
);
349 hed_put_cursor(hed_cursor_t
*curs
)
355 hed_update_cursor(struct hed_file
*file
, hed_uoff_t offset
, hed_cursor_t
*curs
)
358 get_cursor(file_private(file
), offset
, curs
);
362 hed_dup_cursor(const hed_cursor_t
*src
, hed_cursor_t
*dst
)
365 dst
->block
= src
->block
;
367 list_add_tail(&dst
->list
, &src
->block
->refs
);
371 hed_dup2_cursor(const hed_cursor_t
*src
, hed_cursor_t
*dst
)
373 if (hed_is_a_cursor(dst
))
375 hed_dup_cursor(src
, dst
);
378 /* Move cursors from @old to @new, adding @off to their block
379 * offsets to keep them at the same position. */
381 update_cursors(const struct hed_block
*old
, struct hed_block
*new,
386 BDEBUG("Updating cursors from <%p> to <%p>%c%llx\n",
387 old
, new, off
>= 0 ? '+' : '-', off
>= 0 ? off
: -off
);
389 list_for_each_entry(curs
, &old
->refs
, list
) {
395 /* Move cursors in the range <@start;@end> from @old to @new,
396 * adding @off to their block offset, plus moving the reference list. */
398 move_cursors(const struct hed_block
*old
, struct hed_block
*new,
399 hed_uoff_t start
, hed_uoff_t end
, hed_off_t off
)
401 hed_cursor_t
*curs
, *nextcurs
;
403 BDEBUG("Moving cursors from <%p>:%llx:%llx to <%p>%c%llx\n",
404 old
, start
, end
, new,
405 off
>= 0 ? '+' : '-', off
>= 0 ? off
: -off
);
407 list_for_each_entry_safe(curs
, nextcurs
, &old
->refs
, list
)
408 if (curs
->off
>= start
&& curs
->off
<= end
) {
411 list_move(&curs
->list
, &new->refs
);
415 /* Move cursors in the range @block:<@start;@end> to @newpos */
417 move_cursors_abs(const struct hed_block
*block
,
418 hed_uoff_t start
, hed_uoff_t end
,
419 const hed_cursor_t
*newpos
)
421 hed_cursor_t
*curs
, *nextcurs
;
423 BDEBUG("Moving cursors from <%p>:%llx:%llx to <%p>:%llx\n",
424 block
, start
, end
, newpos
->block
, newpos
->off
);
426 list_for_each_entry_safe(curs
, nextcurs
, &block
->refs
, list
)
427 if (curs
->off
>= start
&& curs
->off
<= end
) {
428 curs
->pos
= newpos
->pos
;
429 curs
->block
= newpos
->block
;
430 curs
->off
= newpos
->off
;
431 list_move(&curs
->list
, &newpos
->block
->refs
);
435 /* Update the positions of cursors at and after @start for all
436 * blocks starting at @block */
438 slide_cursors(const struct hed_block
*block
, hed_uoff_t start
, hed_off_t off
)
441 const struct hed_block
*nblock
;
443 BDEBUG("Sliding cursors >= %llx by %c%llx, starting at <%p>\n",
444 start
, off
>= 0 ? '+' : '-', off
>= 0 ? off
: -off
, block
);
448 list_for_each_entry(curs
, &block
->refs
, list
)
449 if (curs
->pos
>= start
)
451 nblock
= next_block(block
);
452 } while (!hed_block_is_terminal(block
));
455 static struct hed_block
*
456 new_block(struct file_priv
*file
, long flags
)
458 struct hed_block
*new;
460 if (! (new = swp_zalloc(file_swp(file
), sizeof(struct hed_block
))) )
464 init_block_link(new);
465 INIT_LIST_HEAD(&new->refs
);
466 if (flags
& HED_BLOCK_EXCACHE
)
467 INIT_LIST_HEAD(&new->lru
);
469 list_add_tail(&new->lru
, &file
->lru
);
474 static struct hed_block
*
475 new_virt_block(struct file_priv
*file
, hed_uoff_t pos
, hed_uoff_t size
,
478 struct hed_block
*new = new_block(file
, (HED_BLOCK_EXCACHE
|
485 new->t
.maxoff
= size
- 1;
487 BDEBUG("Spawned new virtual block [%llx] at %llx\n", size
, pos
);
491 static struct hed_block
*
492 new_data_block(struct file_priv
*file
, hed_uoff_t pos
, hed_uoff_t size
,
493 struct hed_block_data
*dataobj
)
495 struct hed_block
*new = new_block(file
, 0);
500 new->dataobj
= dataobj
;
502 new->t
.maxoff
= size
- 1;
504 new->dataoff
= FILE_BLOCK_OFF(pos
);
505 BDEBUG("Spawned new data block [%llx] at %llx\n", size
, pos
);
510 file_free_block(struct file_priv
*file
, struct hed_block
*block
)
513 cache_put(file
->cache
, block
->dataobj
);
514 list_del(&block
->lru
);
516 swp_free(file_swp(file
), block
);
520 merge_and_free(struct file_priv
*file
, struct hed_block
*block
,
521 struct hed_block
*merger
, hed_off_t off
)
523 /* A bit more efficient than move_cursors() */
524 update_cursors(block
, merger
, off
);
525 list_splice(&block
->refs
, &merger
->refs
);
527 /* Messing with block sizes and unchaining is a bit tricky
528 * since unchain_block() can splay(). So we really need
529 * to recalc_block_recursive() right after we update the size.
530 * If this place turns out to be a hot-spot, we can optimize
531 * the tree operations here. */
532 merger
->t
.maxoff
+= hed_block_size(block
);
533 recalc_block_recursive(merger
);
535 /* Destroy the block */
536 recalc_unchain_block(hed_file_blocks(file
), block
);
537 file_free_block(file
, block
);
540 /* This may kill the previous block as well, if it can be merged
541 * with the next one. It will never kill anything which _follows_. */
543 kill_block(struct file_priv
*file
, struct hed_block
*block
)
545 struct hed_block
*prev
, *next
;
547 assert(!hed_block_is_dirty(block
) || hed_block_is_empty(block
));
549 if (!hed_block_is_virtual(block
)) {
550 /* Convert physical to virtual */
551 assert(block
->dataobj
);
552 cache_put(file
->cache
, block
->dataobj
);
553 block
->dataobj
= NULL
;
555 list_del_init(&block
->lru
); /* unlink the block from LRU */
556 block
->flags
= HED_BLOCK_EXCACHE
| HED_BLOCK_VIRTUAL
|
557 (block
->flags
& (HED_BLOCK_EOF
| HED_BLOCK_EMPTY
));
560 prev
= prev_block(block
);
561 if (prev
->flags
== block
->flags
&&
562 prev
->phys_pos
+ hed_block_size(prev
) == block
->phys_pos
) {
563 merge_and_free(file
, block
, prev
, hed_block_size(prev
));
567 next
= next_block(block
);
568 if (next
->flags
== block
->flags
&&
569 block
->phys_pos
+ hed_block_size(block
) == next
->phys_pos
) {
570 update_cursors(next
, next
, hed_block_size(block
));
571 next
->phys_pos
-= hed_block_size(block
);
572 merge_and_free(file
, block
, next
, 0);
576 if (hed_block_is_empty(block
)) {
577 /* No recalculation needed, zero size. */
578 unchain_block(hed_file_blocks(file
), block
);
579 file_free_block(file
, block
);
584 kill_block_if_empty(struct file_priv
*file
, struct hed_block
*block
)
586 if (!hed_block_is_terminal(block
) && hed_block_is_empty(block
) &&
587 list_empty(&block
->refs
)) {
588 kill_block(file
, block
);
594 static struct hed_block
*
595 split_block(struct file_priv
*file
, struct hed_block
*block
,
596 hed_uoff_t splitpoint
)
598 struct hed_block
*head
;
600 assert(!hed_block_is_empty(block
));
602 head
= new_block(file
, block
->flags
& ~HED_BLOCK_TERMINAL
);
606 if ( (head
->dataobj
= block
->dataobj
) ) {
607 cache_get(head
->dataobj
);
608 head
->dataoff
= block
->dataoff
;
609 block
->dataoff
+= splitpoint
;
611 assert(hed_block_is_virtual(block
));
613 assert(splitpoint
!= 0);
614 head
->t
.maxoff
= splitpoint
- 1;
615 head
->phys_pos
= block
->phys_pos
;
617 if (!hed_block_is_inserted(block
))
618 block
->phys_pos
+= splitpoint
;
619 shrink_block(block
, splitpoint
);
621 recalc_chain_block(hed_file_blocks(file
), head
, block
);
623 move_cursors(block
, head
, 0, splitpoint
- 1, 0);
624 update_cursors(block
, block
, -splitpoint
);
629 /* Replace a chunk in @block with @newblock */
631 replace_chunk(struct file_priv
*file
, struct hed_block
*block
,
632 hed_uoff_t offset
, struct hed_block
*newblock
)
636 assert(offset
<= block
->t
.maxoff
);
637 assert(newblock
->t
.maxoff
<= block
->t
.maxoff
- offset
);
639 /* Re-create the head block if necessary */
640 if (offset
&& !split_block(file
, block
, offset
))
643 /* Move pointers to the new block */
644 len
= hed_block_size(newblock
);
646 move_cursors(block
, newblock
, 0, len
- 1, 0);
648 /* Shorten the tail block */
649 len
= hed_block_size(newblock
);
650 block
->dataoff
+= len
;
651 assert(!hed_block_is_inserted(block
));
652 block
->phys_pos
+= len
;
653 shrink_block(block
, len
);
654 update_cursors(block
, block
, -(hed_off_t
)len
);
656 /* Insert the new block */
657 recalc_chain_block(hed_file_blocks(file
), newblock
, block
);
659 /* Kill the tail block if possible */
660 kill_block_if_empty(file
, block
);
665 #ifdef HED_CONFIG_SWAP
668 swp_filename(const char *filename
)
670 size_t fnlen
= strlen(filename
);
674 if (!(swp
= malloc(fnlen
+ 9)) )
676 strcpy(swp
, filename
);
678 file
= strrchr(swp
, '/');
679 file
= file
? file
+ 1 : swp
;
681 strcpy(stpcpy(file
+ 1, filename
+ (file
-swp
)), ".hedswp");
686 newswp_filename(char *swpname
)
688 char *p
= NULL
; /* bogus assignment to silence a warning */
692 while (!access(ret
, F_OK
)) {
693 if (ret
== swpname
) {
694 if (! (ret
= strdup(swpname
)) )
696 p
= ret
+ strlen(ret
) - 1;
709 hed_file_remove_swap(struct hed_file
*f
)
711 struct file_priv
*file
= file_private(f
);
712 if (remove(file
->swpname
))
714 if (rename(file
->newswpname
, file
->swpname
))
717 free(file
->newswpname
);
718 file
->newswpname
= file
->swpname
;
722 static inline struct file_priv
*
723 file_swp_init(const char *name
)
725 char *swpname
, *newswpname
;
726 struct swp_file
*swp
;
727 struct file_priv
*file
;
729 swpname
= swp_filename(name
);
732 newswpname
= newswp_filename(swpname
);
735 swp
= swp_init_write(newswpname
);
737 goto fail_free_newname
;
739 assert(sizeof(struct swp_header
) + sizeof(struct file_priv
)
741 file
= swp_private(swp
);
742 memset(file
, 0, sizeof *file
);
745 file
->swpname
= swpname
;
746 file
->newswpname
= newswpname
;
753 if (swpname
!= newswpname
)
760 file_swp_done(struct file_priv
*file
)
762 remove(file
->newswpname
);
763 if (file
->newswpname
!= file
->swpname
)
764 free(file
->newswpname
);
766 swp_done(file_swp(file
));
767 /* file was de-allocated automatically with file->swp */
771 hed_file_has_swap(struct hed_file
*f
)
773 struct file_priv
*file
= file_private(f
);
774 return file
->swpname
!= file
->newswpname
;
778 hed_file_swap_name(struct hed_file
*f
)
780 struct file_priv
*file
= file_private(f
);
781 return file
->swpname
;
784 #else /* HED_CONFIG_SWAP */
786 static inline struct file_priv
*
787 file_swp_init(const char *name
)
789 return calloc(1, sizeof(struct file_priv
));
793 file_swp_done(struct file_priv
*file
)
799 hed_file_has_swap(struct hed_file
*file
)
805 hed_file_remove_swap(struct hed_file
*file
)
811 hed_file_swap_name(struct hed_file
*file
)
816 #endif /* HED_CONFIG_SWAP */
818 static inline struct stat
*
819 file_stat(struct file_priv
*file
)
825 hed_file_update_size(struct hed_file
*f
)
827 struct file_priv
*file
= file_private(f
);
828 hed_uoff_t oldsize
= file
->f
.phys_size
;
830 if(fstat(file
->fd
, file_stat(file
)) < 0)
833 if (S_ISBLK(file_stat(file
)->st_mode
)) {
834 if (ioctl(file
->fd
, BLKGETSIZE64
, &file
->f
.phys_size
)) {
835 unsigned long size_in_blocks
;
836 if (ioctl(file
->fd
, BLKGETSIZE
, &size_in_blocks
))
838 file
->f
.phys_size
= (hed_uoff_t
)size_in_blocks
<< 9;
840 } else if (S_ISREG(file_stat(file
)->st_mode
)) {
841 file
->f
.phys_size
= file_stat(file
)->st_size
;
842 } else if (S_ISCHR(file_stat(file
)->st_mode
)) {
843 if (lseek(file
->fd
, 0, SEEK_SET
) < 0)
845 file
->f
.phys_size
= (hed_uoff_t
)OFF_MAX
+ 1;
851 file
->f
.size
+= file
->f
.phys_size
- oldsize
;
856 do_file_open(struct file_priv
*file
)
858 file
->fd
= open(file
->f
.name
, O_RDONLY
);
862 fprintf(stderr
, "Warning: File %s does not exist\n",
864 memset(file_stat(file
), 0, sizeof(struct stat
));
866 } else if (hed_file_update_size(&file
->f
)) {
875 file_setup_blocks(struct file_priv
*file
)
877 hed_uoff_t phys_size
= file
->f
.phys_size
;
878 struct hed_block
*block
;
880 block
= &file
->terminal_block
;
881 block
->flags
= HED_BLOCK_EXCACHE
| HED_BLOCK_VIRTUAL
882 | HED_BLOCK_EOF
| HED_BLOCK_TERMINAL
;
883 INIT_LIST_HEAD(&block
->lru
);
884 INIT_LIST_HEAD(&block
->refs
);
885 block
->t
.maxoff
= OFF_MAX
- phys_size
;
886 block
->phys_pos
= phys_size
;
888 init_block_list(hed_file_blocks(file
), block
);
891 block
= new_virt_block(file
, 0, phys_size
, 0);
894 recalc_chain_block(hed_file_blocks(file
), block
,
895 &file
->terminal_block
);
904 return file_access_init();
908 hed_open(const char *name
)
910 struct file_priv
*file
= file_swp_init(name
);
916 INIT_LIST_HEAD(&file
->lru
);
918 file
->cache
= cache_init(CACHE_LENGTH
, file_swp(file
));
922 if (do_file_open(file
))
925 if (file_setup_blocks(file
))
928 fixup_register(file
);
939 hed_close(struct hed_file
*f
)
941 struct file_priv
*file
= file_private(f
);
944 /* Do not check for errors:
945 * 1. This FD is read-only => no data loss possbile
946 * 2. We're about to exit anyway => no resource leak
951 fixup_deregister(file
);
953 /* No need to free file blocks here, because all data is
954 * allocated either from the cache or from the swap file
955 * and both is going to be destroyed now.
959 cache_done(file
->cache
);
964 /* Adjust a cursor after off gets outside its block */
966 fixup_cursor_slow(hed_cursor_t
*curs
)
968 struct hed_block
*block
= curs
->block
;
969 hed_uoff_t off
= curs
->off
;
972 if ((hed_off_t
)off
< 0) {
973 block
= prev_block(block
);
974 off
+= hed_block_size(block
);
976 off
-= hed_block_size(block
);
977 block
= next_block(block
);
979 } while (!hed_block_is_terminal(block
) && off
> block
->t
.maxoff
);
983 list_move(&curs
->list
, &block
->refs
);
986 /* Adjust a cursor if off gets outside its block.
987 * This is separate from fixup_cursor_slow, because it is supposed
988 * to be small enough to be inlined (which is a win, because most of
989 * the time no fixup has to be done, so the fast inlined path is used).
992 fixup_cursor(hed_cursor_t
*curs
)
994 if (curs
->off
> curs
->block
->t
.maxoff
)
995 fixup_cursor_slow(curs
);
999 hed_move_relative(hed_cursor_t
*curs
, hed_off_t num
)
1001 hed_uoff_t newpos
= curs
->pos
+ num
;
1002 if (num
< 0 && newpos
> curs
->pos
)
1004 else if (num
> 0 && newpos
< curs
->pos
)
1006 num
= newpos
- curs
->pos
;
1013 /* Relative move with no checking (and only by a small amount) */
1015 move_rel_fast(hed_cursor_t
*curs
, ssize_t num
)
1023 alloc_caches(struct file_priv
*file
, struct hed_block_data
**caches
, int n
)
1025 struct remap_control rc
;
1028 BDEBUG("Allocate %d caches (%d free slots available)\n",
1029 n
, file
->cache
->nfree
);
1031 assert(n
<= CACHE_LENGTH
);
1032 while (file
->cache
->nfree
< n
) {
1033 struct hed_block
*block
;
1035 assert(!list_empty(&file
->lru
));
1036 block
= list_entry(file
->lru
.next
, struct hed_block
, lru
);
1037 BDEBUG("Killing block at physical %llx\n", block
->phys_pos
);
1038 kill_block(file
, block
);
1041 for (i
= 0; i
< n
; ++i
) {
1042 caches
[i
] = cache_alloc(file
->cache
);
1047 remap_compact(&rc
, file
->cache
, caches
, n
);
1048 for (i
= 0; i
< n
; ++i
)
1049 remap_add(&rc
, caches
[i
]->data
);
1054 free_caches(struct file_priv
*file
, struct hed_block_data
**preload
, int n
)
1058 for (i
= 0; i
< n
; ++i
)
1060 cache_put(file
->cache
, preload
[i
]);
1064 file_load_data(struct file_priv
*file
,
1065 struct hed_block_data
**caches
, int n
,
1068 struct hed_block_data
*dataobj
= caches
[0];
1069 void *data
= dataobj
->data
;
1070 ssize_t rsize
, total
, segsize
;
1072 segsize
= n
<< FILE_BLOCK_SHIFT
;
1073 for (total
= 0; total
< segsize
; total
+= rsize
) {
1074 rsize
= pread(file
->fd
, data
+ total
,
1075 segsize
- total
, offset
+ total
);
1077 memset(data
+ total
, 0, segsize
- total
);
1081 cache_put(file
->cache
,
1082 caches
[total
>> FILE_BLOCK_SHIFT
]);
1083 caches
[total
>> FILE_BLOCK_SHIFT
] = NULL
;
1084 total
= FILE_BLOCK_ROUND(total
);
1085 rsize
= FILE_BLOCK_SIZE
;
1086 BDEBUG("Error reading block at phys %llx: %s\n",
1087 offset
+ total
, strerror(errno
));
1091 BDEBUG("Loaded data at phys %llx up to %llx\n",
1092 offset
, offset
+ segsize
);
1096 #ifdef HED_CONFIG_MMAP
1099 file_load_data_mmap(struct file_priv
*file
,
1100 struct hed_block_data
**caches
, int n
,
1107 segsize
= n
<< FILE_BLOCK_SHIFT
;
1108 data
= mmap(NULL
, segsize
,
1109 PROT_READ
| PROT_WRITE
,
1110 MAP_PRIVATE
| (file
->fd
< 0 ? MAP_ANONYMOUS
: 0),
1113 if (data
== MAP_FAILED
) {
1114 BDEBUG("mmap failed at %llx: fail over to traditional read\n",
1117 data
= mmap(NULL
, segsize
,
1118 PROT_READ
| PROT_WRITE
,
1119 MAP_PRIVATE
| MAP_ANONYMOUS
,
1121 if (data
== MAP_FAILED
)
1124 for (i
= 0; i
< n
; ++i
)
1125 caches
[i
]->data
= data
+ (i
<< FILE_BLOCK_SHIFT
);
1126 return file_load_data(file
, caches
, n
, offset
);
1129 for (i
= 0; i
< n
; ++i
)
1130 caches
[i
]->data
= data
+ (i
<< FILE_BLOCK_SHIFT
);
1132 BDEBUG("Loaded data at phys %llx up to %llx\n",
1133 offset
, offset
+ segsize
);
1136 # define file_load_data file_load_data_mmap
1140 /* Find the block with the lowest physical position that intersects
1141 * the loaded segment. The search starts at @block.
1143 static struct hed_block
*
1144 first_load_block(struct hed_block
*block
, hed_uoff_t segstart
)
1146 struct hed_block
*prev
= block
;
1149 prev
= prev_block(prev
);
1150 } while (!hed_block_is_terminal(prev
) && phys_end(prev
) > segstart
);
1155 load_blocks(struct file_priv
*file
, const hed_cursor_t
*from
)
1157 hed_uoff_t physpos
, segstart
;
1158 struct hed_block_data
*preload
[FILE_READAHEAD
];
1159 size_t ra_bkw
, ra_fwd
, ra_off
;
1164 segstart
= hed_cursor_phys_pos(from
);
1165 ra_bkw
= FILE_BLOCK_OFF(segstart
);
1166 ra_fwd
= FILE_BLOCK_SIZE
- ra_bkw
;
1168 if (file_ra_forward(file
))
1169 ra_fwd
+= (FILE_READAHEAD
- 1) << FILE_BLOCK_SHIFT
;
1170 else if (file_ra_backward(file
))
1171 ra_bkw
+= (FILE_READAHEAD
- 1) << FILE_BLOCK_SHIFT
;
1173 if (ra_bkw
> segstart
)
1175 if (ra_fwd
> file
->f
.phys_size
- segstart
)
1176 ra_fwd
= file
->f
.phys_size
- segstart
;
1180 pos
.block
= first_load_block(from
->block
, segstart
);
1181 pos
.off
= segstart
>= pos
.block
->phys_pos
1182 ? segstart
- pos
.block
->phys_pos
1185 list_add(&pos
.list
, &pos
.block
->refs
);
1186 nblocks
= ((ra_fwd
- 1) >> FILE_BLOCK_SHIFT
) + 1;
1187 alloc_caches(file
, preload
, nblocks
);
1190 ret
= -1; /* be a pessimist */
1191 if (file_load_data(file
, preload
, nblocks
, segstart
))
1194 while (physpos
= hed_cursor_phys_pos(&pos
),
1195 ra_off
= physpos
- segstart
,
1197 struct hed_block_data
*dataobj
;
1198 struct hed_block
*newblock
;
1201 if (!hed_block_is_virtual(pos
.block
)) {
1202 pos
.block
= next_block(pos
.block
);
1207 datalen
= FILE_BLOCK_SIZE
- FILE_BLOCK_OFF(physpos
);
1208 if (datalen
> hed_block_size(pos
.block
) - pos
.off
)
1209 datalen
= hed_block_size(pos
.block
) - pos
.off
;
1211 dataobj
= preload
[ra_off
>> FILE_BLOCK_SHIFT
];
1213 ? new_data_block(file
, physpos
, datalen
, dataobj
)
1214 : new_virt_block(file
, physpos
, datalen
,
1219 /* Punch the new block */
1220 BDEBUG("Add %s block at %llx, length %llx\n",
1221 hed_block_is_virtual(newblock
) ? "error" : "physical",
1222 newblock
->phys_pos
, hed_block_size(newblock
));
1223 if (replace_chunk(file
, pos
.block
, pos
.off
, newblock
)) {
1224 file_free_block(file
, newblock
);
1228 pos
.block
= next_block(newblock
);
1234 /* All cache objects now have an extra reference from the
1235 * allocation. Drop it. */
1236 free_caches(file
, preload
, nblocks
);
1242 /* Shorten a block at beginning and enlarge the preceding block.
1244 * Re-allocate at most @len bytes from the beginning of @block to the
1245 * end of the preceding block.
1246 * If @block is virtual, this will effectively devirtualize the range.
1247 * If @block is not virtual, this will change the backing store of
1248 * the bytes in the range.
1249 * Returns: the number of bytes actually moved.
1252 shrink_at_begin(struct hed_block
*block
, size_t len
, long state
)
1254 struct hed_block
*prev
;
1257 /* Basic assumptions */
1258 assert(!(state
& HED_BLOCK_VIRTUAL
));
1260 /* The previous block must exist: */
1261 prev
= prev_block(block
);
1262 if (hed_block_is_terminal(prev
))
1265 /* The block flags must match the requested @state: */
1266 if ((prev
->flags
& HED_BLOCK_STATEMASK
) != state
)
1269 /* No deletions at end, or similar: */
1270 if (prev
->phys_pos
+ hed_block_size(prev
) != block
->phys_pos
)
1273 /* Append less bytes than requested if not all are available */
1274 assert(prev
->t
.maxoff
< prev
->dataobj
->size
- prev
->dataoff
);
1275 maxgrow
= prev
->dataobj
->size
- prev
->dataoff
- hed_block_size(prev
);
1281 BDEBUG("Appending 0:%lx to the previous block\n", len
);
1283 /* Move cursors away from the to-be-chopped beginning */
1284 move_cursors(block
, prev
, 0, len
- 1, hed_block_size(prev
));
1286 /* Enlarge the previous block */
1287 prev
->t
.maxoff
+= len
;
1288 recalc_block_recursive(prev
);
1290 /* Shorten the original block */
1291 block
->dataoff
+= len
;
1292 block
->phys_pos
+= len
;
1293 shrink_block(block
, len
);
1298 /* Shorten a block at end and enlarge the following block.
1300 * Re-allocate at most @len bytes from the end of @block to the
1301 * beginning of the following block.
1302 * If @block is virtual, this will effectively devirtualize the range.
1303 * If @block is not virtual, this will change the backing store of
1304 * the bytes in the range.
1305 * Returns: the number of bytes actually moved.
1308 shrink_at_end(struct hed_block
*block
, size_t len
, long state
)
1310 struct hed_block
*next
;
1313 /* Basic assumptions */
1314 assert(!(state
& HED_BLOCK_VIRTUAL
));
1316 /* The next block must exist: */
1317 if (hed_block_is_terminal(block
))
1319 next
= next_block(block
);
1321 /* The block flags must match the requested @state: */
1322 if ((next
->flags
& HED_BLOCK_STATEMASK
) != state
)
1325 /* No deletions at end, or similar: */
1326 if (block
->phys_pos
+ hed_block_size(block
) != next
->phys_pos
)
1329 /* Prepend less bytes than requested if not all are available */
1330 if (len
> next
->dataoff
)
1331 len
= next
->dataoff
;
1334 off
= hed_block_size(block
) - len
;
1336 BDEBUG("Prepending %llx:%lx to the next block\n", off
, len
);
1338 /* Shift cursors in the new physical block */
1339 update_cursors(next
, next
, len
);
1341 /* Move cursors away from the to-be-chopped end */
1342 move_cursors(block
, next
, off
, UOFF_MAX
, -off
);
1344 /* Enlarge the next block */
1345 next
->dataoff
-= len
;
1346 next
->phys_pos
-= len
;
1347 next
->t
.maxoff
+= len
;
1348 recalc_block_recursive(next
);
1350 /* Shorten the original block */
1351 shrink_block(block
, len
);
1356 /* Search for an existing data object within the same physical block
1357 * as @curs, and having the given @state flags.
1359 static struct hed_block_data
*
1360 search_data(struct file_priv
*file
, const hed_cursor_t
*curs
, long state
)
1362 struct hed_block
*block
;
1365 physpos
= FILE_BLOCK_ROUND(curs
->block
->phys_pos
+ curs
->off
);
1366 BDEBUG("Search for already loaded data at %llx starting at %llx...",
1367 physpos
, curs
->block
->phys_pos
);
1369 /* Search backwards */
1370 block
= curs
->block
;
1371 while (!hed_block_is_terminal(block
= prev_block(block
))) {
1372 if (block
->phys_pos
< physpos
)
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
;
1381 /* Search forwards */
1382 block
= curs
->block
;
1383 while (!hed_block_is_terminal(block
)) {
1384 block
= next_block(block
);
1385 if (block
->phys_pos
>= physpos
+ FILE_BLOCK_SIZE
)
1387 if ((block
->flags
& STATEMASK_SANS_EOF
) == state
) {
1388 BDEBUG(" found at %llx\n", block
->phys_pos
);
1389 assert(block
->dataobj
);
1390 return block
->dataobj
;
1394 BDEBUG(" not found\n");
1399 reuse_loaded_data(struct file_priv
*file
, const hed_cursor_t
*curs
,
1400 struct hed_block_data
*data
)
1402 struct hed_block
*physblock
;
1403 struct hed_block
*block
= curs
->block
;
1404 hed_uoff_t block_offset
= curs
->off
;
1405 hed_uoff_t physpos
= block
->phys_pos
+ block_offset
;
1406 size_t part
= FILE_BLOCK_OFF(physpos
);
1408 FILE_BLOCK_SIZE
- part
<= hed_block_size(block
) - block_offset
1409 ? FILE_BLOCK_SIZE
- part
1410 : hed_block_size(block
) - block_offset
;
1412 if (part
> block_offset
)
1413 part
= block_offset
;
1416 block_offset
-= part
;
1418 if (! (physblock
= new_data_block(file
, physpos
, len
, data
)) )
1421 BDEBUG("Add physical block at %llx, length %llx\n",
1422 physblock
->phys_pos
, hed_block_size(physblock
));
1423 if (replace_chunk(file
, block
, block_offset
, physblock
)) {
1424 file_free_block(file
, physblock
);
1432 /* Replace a part of a virtual block with content loaded
1433 * from disk. The amount of data loaded from the disk depends
1434 * on various factors with the goal to choose the most efficient
1435 * ratio. The only guarantee is that the byte at @curs will
1436 * be in a non-virtual block when this function returns 0.
1439 devirtualize_clean(struct file_priv
*file
, const hed_cursor_t
*curs
)
1441 struct hed_block
*block
= curs
->block
;
1442 hed_uoff_t block_offset
= curs
->off
;
1443 hed_uoff_t remain
= hed_block_size(block
) - block_offset
;
1444 struct hed_block_data
*data
;
1446 BDEBUG("punch a clean hole at %llx into %llx:%llx\n", block_offset
,
1447 block_offset(block
), hed_block_size(block
));
1448 assert(hed_block_is_virtual(block
));
1450 /* Check if we can combine with a neighbouring block */
1451 if (shrink_at_begin(block
, hed_block_size(block
), 0) > block_offset
1452 || shrink_at_end(block
, hed_block_size(block
), 0) >= remain
) {
1453 kill_block_if_empty(file
, block
);
1458 /* Check if the block is already loaded elsewhere */
1459 data
= search_data(file
, curs
, 0);
1461 ? reuse_loaded_data(file
, curs
, data
)
1462 : load_blocks(file
, curs
);
1465 /* Unles the block at @curs is already dirty, replace at most
1466 * @len bytes at @curs with a newly allocated out-of-cache block.
1467 * The block is marked dirty and its data is left uninitialized.
1468 * Note that this function may devirtualize less than @len bytes.
1469 * In the worst case only 1 byte at @curs will be available.
1472 prepare_modify(struct file_priv
*file
, hed_cursor_t
*curs
, size_t len
)
1474 struct hed_block
*block
= curs
->block
;
1475 hed_uoff_t block_offset
= curs
->off
;
1476 hed_uoff_t remain
= hed_block_size(block
) - block_offset
;
1477 long newstate
= HED_BLOCK_DIRTY
| (block
->flags
& HED_BLOCK_EOF
);
1478 struct hed_block
*newblock
;
1480 if (hed_block_is_dirty(block
))
1486 BDEBUG("punch a dirty hole at %llx:%lx into %llx:%llx\n",
1488 block_offset(block
), hed_block_size(block
));
1490 /* Check if we can combine with a neighbouring block */
1491 if ((block_offset
== 0 &&
1492 shrink_at_begin(block
, len
, newstate
)) ||
1494 shrink_at_end(block
, len
, newstate
) >= len
)) {
1495 kill_block_if_empty(file
, block
);
1500 /* Initialize a new block */
1501 newblock
= new_block(file
, HED_BLOCK_EXCACHE
| newstate
);
1506 if ( (newblock
->dataobj
= search_data(file
, curs
, HED_BLOCK_DIRTY
)) )
1507 cache_get(newblock
->dataobj
);
1508 else if (! (newblock
->dataobj
= block_data_new(file
->cache
,
1512 newblock
->phys_pos
= block
->phys_pos
+ block_offset
;
1513 newblock
->dataoff
= FILE_BLOCK_OFF(newblock
->phys_pos
);
1514 if (len
> FILE_BLOCK_SIZE
- newblock
->dataoff
)
1515 len
= FILE_BLOCK_SIZE
- newblock
->dataoff
;
1517 newblock
->t
.maxoff
= len
- 1;
1519 if (replace_chunk(file
, block
, block_offset
, newblock
))
1526 file_free_block(file
, newblock
);
1531 /* Ensure that @curs points to an up-to-date non-virtual block.
1532 * Load the data from disk if necessary, return zero on failure. */
1534 hed_prepare_read(struct hed_file
*f
, const hed_cursor_t
*curs
, size_t len
)
1536 struct file_priv
*file
= file_private(f
);
1537 struct hed_block
*block
= curs
->block
;
1538 if (block_is_loadable(block
) &&
1539 devirtualize_clean(file
, curs
) < 0)
1542 return hed_cursor_chunk_len(curs
, len
);
1545 /* Move the block pointer to the next block */
1546 static struct hed_block
*
1547 cursor_next_block(hed_cursor_t
*curs
)
1549 struct hed_block
*block
= next_nonzero_block(curs
->block
);
1552 curs
->block
= block
;
1554 list_move(&curs
->list
, &block
->refs
);
1559 /* Copy in @count bytes from @pos.
1560 * Returns the number of bytes that were not read (i.e. zero on success).
1561 * The @pos cursor is moved by the amount of data read.
1562 * CAUTION: If you read up to MAX_OFF, then @pos points one byte
1563 * beyond the EOF block upon return.
1566 copy_in(struct file_priv
*file
, void *buf
, size_t count
, hed_cursor_t
*pos
)
1571 while (count
&& (cpylen
= hed_prepare_read(&file
->f
, pos
, count
))) {
1572 if (hed_block_is_bad(pos
->block
))
1574 else if (hed_block_is_virtual(pos
->block
))
1575 memset(buf
, 0, cpylen
);
1577 memcpy(buf
, hed_cursor_data(pos
), cpylen
);
1581 if ( (pos
->off
+= cpylen
) >= hed_block_size(pos
->block
) )
1582 if (!cursor_next_block(pos
))
1590 hed_file_cpin(struct hed_file
*file
, void *buf
, size_t count
,
1591 const hed_cursor_t
*pos
)
1596 hed_dup_cursor(pos
, &mypos
);
1597 ret
= copy_in(file_private(file
), buf
, count
, &mypos
);
1602 /* Set the modified flag */
1604 set_modified(struct file_priv
*file
)
1606 file
->f
.modified
= true;
1609 /* Clear the modified flag */
1611 clear_modified(struct file_priv
*file
)
1613 file
->f
.modified
= false;
1617 hed_file_set_byte(struct hed_file
*f
, hed_cursor_t
*curs
, unsigned char byte
)
1619 struct file_priv
*file
= file_private(f
);
1621 if (prepare_modify(file
, curs
, 1))
1625 hed_block_data(curs
->block
)[curs
->off
] = byte
;
1627 if (hed_block_is_terminal(next_block(curs
->block
)))
1628 file
->f
.size
= curs
->pos
+ 1;
1634 hed_file_set_block(struct hed_file
*f
, hed_cursor_t
*curs
,
1635 unsigned char *buf
, size_t len
)
1637 struct file_priv
*file
= file_private(f
);
1641 if (prepare_modify(file
, curs
, len
))
1645 span
= hed_cursor_chunk_len(curs
, len
);
1646 memcpy(hed_cursor_data(curs
), buf
, span
);
1649 move_rel_fast(curs
, span
);
1652 if (hed_block_is_terminal(curs
->block
))
1653 file
->f
.size
= curs
->pos
;
1659 hed_file_set_bytes(struct hed_file
*f
, hed_cursor_t
*curs
,
1660 unsigned char byte
, hed_uoff_t rep
)
1662 struct file_priv
*file
= file_private(f
);
1666 if (prepare_modify(file
, curs
, rep
))
1670 span
= hed_cursor_chunk_len(curs
, rep
);
1671 memset(hed_cursor_data(curs
), byte
, span
);
1673 move_rel_fast(curs
, span
);
1676 if (hed_block_is_terminal(curs
->block
))
1677 file
->f
.size
= curs
->pos
;
1683 file_erase_continuous(struct file_priv
*file
, hed_cursor_t
*curs
, size_t len
)
1685 struct hed_block
*block
= curs
->block
;
1686 hed_uoff_t block_offset
= curs
->off
;
1688 /* Find the new position */
1689 hed_move_relative(curs
, len
);
1691 /* Move all other cursors in the erased range to the new position */
1693 move_cursors_abs(block
, block_offset
,
1694 block_offset
+ len
- 1, curs
);
1696 if (!block_offset
) {
1697 block
->dataoff
+= len
;
1698 if (!hed_block_is_inserted(block
))
1699 block
->phys_pos
+= len
;
1700 } else if (block_offset
+ len
<= block
->t
.maxoff
) {
1701 block
= split_block(file
, block
, block_offset
+ len
);
1706 move_cursors(block
, block
, block_offset
, UOFF_MAX
, -(hed_uoff_t
)len
);
1708 shrink_block(block
, len
);
1709 kill_block_if_empty(file
, block
);
1714 hed_file_erase_block(struct hed_file
*f
, hed_cursor_t
*curs
, hed_uoff_t len
)
1716 struct file_priv
*file
= file_private(f
);
1720 while (!hed_block_is_terminal(curs
->block
) && todo
) {
1721 size_t span
= hed_cursor_chunk_len(curs
, todo
);
1723 if (file_erase_continuous(file
, curs
, span
))
1730 file
->f
.size
-= len
;
1733 file
->terminal_block
.t
.maxoff
+= len
;
1734 recalc_block_recursive(&file
->terminal_block
);
1736 struct hed_block
*slideblock
= prev_block(curs
->block
);
1737 if (hed_block_is_terminal(slideblock
))
1738 slideblock
= curs
->block
;
1739 slide_cursors(slideblock
, curs
->pos
, -len
);
1741 return hed_block_is_terminal(curs
->block
) ? 0 : todo
;
1744 /* Note that @curs may be detached from the block reference list
1745 * with put_cursor(). Only the pos, block and off fields are used.
1746 * This is an implementation detail currently required by
1747 * hed_file_insert_block(), which sets @curs and @curs_ins to the
1748 * same value. Other users of the library must not rely on it.
1751 hed_file_insert_begin(struct hed_file
*f
, const hed_cursor_t
*curs
,
1752 hed_cursor_t
*curs_ins
)
1754 struct file_priv
*file
= file_private(f
);
1755 struct hed_block
*newblock
;
1757 BDEBUG("Starting insert at %llx\n", curs
->pos
);
1759 newblock
= new_block(file
, (HED_BLOCK_EXCACHE
| HED_BLOCK_EMPTY
|
1760 HED_BLOCK_INSERTED
| HED_BLOCK_DIRTY
|
1761 (curs
->block
->flags
& HED_BLOCK_EOF
)));
1765 newblock
->t
.maxoff
= (hed_uoff_t
)-1;
1766 newblock
->phys_pos
= hed_cursor_phys_pos(curs
);
1767 newblock
->dataobj
= block_data_new(file
->cache
, FILE_BLOCK_SIZE
);
1768 if (!newblock
->dataobj
) {
1769 file_free_block(file
, newblock
);
1773 if (curs
->off
&& !split_block(file
, curs
->block
, curs
->off
)) {
1774 file_free_block(file
, newblock
);
1778 chain_block(hed_file_blocks(file
), newblock
, curs
->block
);
1780 curs_ins
->pos
= curs
->pos
;
1782 curs_ins
->block
= newblock
;
1783 list_add(&curs_ins
->list
, &newblock
->refs
);
1790 hed_file_insert_end(struct hed_file
*f
, hed_cursor_t
*curs_ins
)
1792 struct file_priv
*file
= file_private(f
);
1793 struct hed_block
*block
= curs_ins
->block
;
1795 BDEBUG("End insert at %llx\n", curs_ins
->pos
);
1797 curs_ins
->block
= NULL
;
1798 list_del(&curs_ins
->list
);
1799 if (!kill_block_if_empty(file
, block
))
1800 block_data_shrink(file
->cache
, block
->dataobj
,
1801 block
->dataoff
+ hed_block_size(block
));
1807 insert_block(struct file_priv
*file
, hed_cursor_t
*curs
,
1808 unsigned char *buf
, size_t len
)
1810 struct hed_block
*block
= curs
->block
;
1811 hed_uoff_t offset
= curs
->pos
;
1813 assert(hed_block_is_excache(block
));
1814 assert(hed_block_is_dirty(block
));
1817 memcpy(hed_block_data(block
) + curs
->off
, buf
, len
);
1818 block
->t
.maxoff
+= len
;
1820 hed_block_clear_empty(block
);
1821 recalc_block_recursive(block
);
1825 slide_cursors(next_block(block
), offset
, len
);
1829 hed_file_insert_block(struct hed_file
*f
, hed_cursor_t
*curs
,
1830 unsigned char *buf
, size_t len
)
1832 struct file_priv
*file
= file_private(f
);
1835 struct hed_block
*block
= curs
->block
;
1838 remain
= block
->dataobj
->size
- block
->dataoff
- curs
->off
;
1841 curs
->block
= next_block(block
);
1844 if (hed_file_insert_begin(&file
->f
, curs
, curs
))
1853 BDEBUG("Append %ld bytes to the insert block\n",
1855 insert_block(file
, curs
, buf
, remain
);
1861 if (curs
->pos
> file
->f
.size
)
1862 file
->f
.size
= curs
->pos
;
1864 file
->f
.size
+= len
;
1866 file
->terminal_block
.t
.maxoff
-= len
;
1867 recalc_block_recursive(&file
->terminal_block
);
1873 hed_file_insert_byte(struct hed_file
*file
, hed_cursor_t
*curs
,
1876 return hed_file_insert_block(file
, curs
, &byte
, 1);
1880 hed_file_insert_once(struct hed_file
*file
, hed_cursor_t
*curs
,
1881 unsigned char *buf
, size_t len
)
1883 hed_cursor_t insert
;
1885 if (!hed_file_insert_begin(file
, curs
, &insert
)) {
1886 len
= hed_file_insert_block(file
, &insert
, buf
, len
);
1887 hed_file_insert_end(file
, &insert
);
1892 struct commit_control
{
1893 struct file_priv
*file
;
1894 int wfd
; /* file descriptor for writing */
1895 hed_cursor_t begoff
, endoff
;
1896 void *buffer
; /* write buffer (one block) */
1900 commit_write(struct commit_control
*cc
, hed_uoff_t pos
, ssize_t len
)
1902 BDEBUG(" -> write %lx bytes at %llx\n",
1903 (unsigned long)len
, pos
);
1904 return pwrite(cc
->wfd
, cc
->buffer
, len
, pos
);
1907 /* Commit forwards. */
1909 commit_forwards(struct commit_control
*cc
)
1913 BDEBUG("Writing forwards %llx-%llx\n",
1914 cc
->begoff
.pos
, cc
->endoff
.pos
);
1916 while (cc
->begoff
.pos
< cc
->endoff
.pos
) {
1920 left
= copy_in(cc
->file
, cc
->buffer
,
1921 FILE_BLOCK_SIZE
, &cc
->begoff
);
1923 move_rel_fast(&cc
->begoff
, left
);
1928 written
= commit_write(cc
, cc
->begoff
.pos
- FILE_BLOCK_SIZE
,
1930 if (written
< FILE_BLOCK_SIZE
)
1937 /* Commit backwards. */
1939 commit_backwards(struct commit_control
*cc
)
1944 BDEBUG("Writing backwards %llx-%llx\n",
1945 cc
->begoff
.pos
, cc
->endoff
.pos
);
1947 hed_dup_cursor(&cc
->endoff
, &curs
);
1948 while (curs
.pos
> cc
->begoff
.pos
) {
1952 move_rel_fast(&curs
, -FILE_BLOCK_SIZE
);
1953 left
= hed_file_cpin(&cc
->file
->f
, cc
->buffer
,
1954 FILE_BLOCK_SIZE
, &curs
);
1960 written
= commit_write(cc
, curs
.pos
, FILE_BLOCK_SIZE
);
1961 if (written
< FILE_BLOCK_SIZE
)
1964 hed_put_cursor(&curs
);
1969 /* Return the number of clean bytes following @curs.
1970 * Usage note: the caller must ensure that the starting position
1974 clean_span(hed_cursor_t
*curs
)
1976 hed_uoff_t next_pos
;
1977 struct hed_block
*block
= curs
->block
;
1978 hed_uoff_t ret
= -curs
->off
;
1980 assert(!hed_block_is_dirty(block
));
1983 ret
+= hed_block_size(block
);
1984 next_pos
= block
->phys_pos
+ hed_block_size(block
);
1985 block
= next_nonzero_block(block
);
1986 } while (block
->phys_pos
== next_pos
&& /* no insertions, deletions */
1987 !hed_block_is_dirty(block
) && /* no modifications */
1988 !hed_block_is_terminal(block
));
1993 undirty_blocks(struct file_priv
*file
)
1995 struct hed_block
*block
, *next
;
1997 BDEBUG("Undirtying blocks:\n");
2000 next
= first_block(file
);
2002 while (!hed_block_is_terminal(next
)) {
2004 next
= next_block(block
);
2005 next
->phys_pos
= block
->phys_pos
+ hed_block_size(block
);
2007 hed_block_clear_dirty(block
);
2008 hed_block_clear_eof(block
);
2009 kill_block(file
, block
);
2012 BDEBUG("After undirtying\n");
2017 commit_init(struct commit_control
*cc
, struct file_priv
*file
)
2020 cc
->buffer
= malloc(FILE_BLOCK_SIZE
);
2025 file
->fd
= open(file
->f
.name
, O_RDONLY
| O_CREAT
, 0666);
2030 cc
->wfd
= open(file
->f
.name
, O_WRONLY
);
2043 hed_file_commit(struct hed_file
*f
)
2045 struct file_priv
*file
= file_private(f
);
2046 struct commit_control cc
;
2050 if (commit_init(&cc
, file
))
2055 get_cursor(file
, 0,&cc
.begoff
);
2056 hed_dup_cursor(&cc
.begoff
, &cc
.endoff
);
2057 shift
= -cc
.begoff
.block
->phys_pos
;
2058 while(!hed_block_is_terminal(cc
.endoff
.block
)) {
2062 if (!shift
&& !hed_block_is_dirty(cc
.endoff
.block
)) {
2063 skip
= FILE_BLOCK_ROUND(clean_span(&cc
.endoff
));
2065 ret
|= commit_forwards(&cc
);
2067 BDEBUG("Skipping %llx-%llx\n",
2068 cc
.endoff
.pos
, cc
.endoff
.pos
+ skip
);
2069 hed_move_relative(&cc
.endoff
, skip
);
2070 hed_dup2_cursor(&cc
.endoff
, &cc
.begoff
);
2075 skip
= FILE_BLOCK_ROUND(hed_cursor_span(&cc
.endoff
));
2076 hed_move_relative(&cc
.endoff
, skip
?: FILE_BLOCK_SIZE
);
2078 newshift
= !hed_block_is_eof(cc
.endoff
.block
)
2079 ? cc
.endoff
.pos
- hed_cursor_phys_pos(&cc
.endoff
)
2082 if (shift
<= 0 && newshift
> 0) {
2083 move_rel_fast(&cc
.endoff
, -FILE_BLOCK_SIZE
);
2084 ret
|= commit_forwards(&cc
);
2085 hed_dup2_cursor(&cc
.endoff
, &cc
.begoff
);
2086 } else if (shift
> 0 && newshift
<= 0) {
2087 ret
|= commit_backwards(&cc
);
2088 hed_dup2_cursor(&cc
.endoff
, &cc
.begoff
);
2092 assert(cc
.endoff
.pos
>= hed_file_size(&file
->f
));
2094 ret
|= commit_forwards(&cc
);
2095 put_cursor(&cc
.begoff
);
2096 put_cursor(&cc
.endoff
);
2098 ftruncate(cc
.wfd
, hed_file_size(&file
->f
));
2099 file
->f
.phys_size
= hed_file_size(&file
->f
);
2101 ret
|= close(cc
.wfd
);
2104 undirty_blocks(file
);
2107 clear_modified(file
);
2112 #ifdef HED_CONFIG_SWAP
2114 hed_file_write_swap(struct hed_file
*file
)
2116 return swp_write(file_swp(file_private(file
)));
2120 do_read_swap(struct file_priv
*file
, struct swp_file
*swp
, hed_cursor_t
*pos
)
2122 struct file_priv
*swpfile
= swp_private(swp
);
2123 struct hed_block
*cur
, block
;
2124 hed_uoff_t phys_pos
;
2126 if (file_stat(swpfile
)->st_size
!= file_stat(file
)->st_size
||
2127 file_stat(swpfile
)->st_mtime
!= file_stat(file
)->st_mtime
) {
2128 fprintf(stderr
, "stat info mismatch (you modified the file since hed ran on it; refusing to touch it)\n");
2132 BDEBUG("Swap header match\n");
2135 cur
= first_block(swpfile
);
2137 struct hed_block_data dataobj
;
2138 size_t (*mergefn
)(struct hed_file
*, hed_cursor_t
*,
2139 unsigned char*, size_t);
2143 if (swp_cpin(swp
, &block
, cur
, sizeof(struct hed_block
))) {
2144 perror("Cannot read block descriptor");
2147 BDEBUG("BLOCK %p: flags %02lx phys 0x%02llx size 0x%llx\n",
2148 cur
, block
.flags
, (long long)block
.phys_pos
,
2149 (long long)hed_block_size(&block
));
2151 if (block
.phys_pos
- phys_pos
) {
2152 if (hed_file_erase_block(&file
->f
, pos
,
2153 block
.phys_pos
- phys_pos
)) {
2154 perror("Cannot erase");
2157 phys_pos
= block
.phys_pos
;
2160 if (!hed_block_is_inserted(&block
))
2161 phys_pos
+= hed_block_size(&block
);
2163 if (!hed_block_is_dirty(&block
)) {
2164 hed_move_relative(pos
, hed_block_size(&block
));
2168 if (swp_cpin(swp
, &dataobj
, block
.dataobj
,
2169 sizeof(struct hed_block_data
))) {
2170 perror("Cannot read data descriptor");
2173 BDEBUG("DATA %p: size 0x%lx\n",
2174 block
.dataobj
, (long)dataobj
.size
);
2176 if (! (data
= malloc(hed_block_size(&block
))) ) {
2177 perror("Cannot allocate data");
2181 if (swp_cpin(swp
, data
, dataobj
.data
+ block
.dataoff
,
2182 hed_block_size(&block
))) {
2183 perror("Cannot read data");
2187 mergefn
= hed_block_is_inserted(&block
)
2188 ? hed_file_insert_once
2189 : hed_file_set_block
;
2190 res
= mergefn(&file
->f
, pos
, data
, hed_block_size(&block
));
2193 perror("Cannot merge data");
2196 } while (cur
= next_block(&block
), !hed_block_is_terminal(&block
));
2203 hed_file_read_swap(struct hed_file
*f
)
2205 struct file_priv
*file
= file_private(f
);
2206 struct swp_file
*swp
;
2210 if (! (swp
= swp_init_read(file
->swpname
)) )
2213 get_cursor(file
, 0, &pos
);
2214 ret
= do_read_swap(file
, swp
, &pos
);
2224 hed_file_write_swap(struct hed_file
*file
)
2230 hed_file_read_swap(struct hed_file
*file
)
2235 #endif /* HED_CONFIG_SWAP */
2237 /* Check if the search string is all zero */
2239 is_allzero(unsigned char *s
, size_t len
)
2248 reverse(unsigned char *p
, size_t len
)
2250 unsigned char *q
= p
+ len
;
2252 unsigned char x
= *p
;
2259 compute_badchar(ssize_t
*badchar
, const unsigned char *s
, ssize_t len
)
2263 badchar
[*s
++] = i
++;
2267 compute_sfx(ssize_t
*sfx
, const unsigned char *s
, ssize_t len
)
2272 f
= 0; /* bogus assignment to silence a warning */
2274 for (i
= len
- 2; i
>= 0; --i
) {
2275 if (i
> g
&& sfx
[i
+ len
- 1 - f
] < i
- g
)
2276 sfx
[i
] = sfx
[i
+ len
- 1 - f
];
2281 while (g
>= 0 && s
[g
] == s
[g
+ len
- 1 - f
])
2289 compute_goodsfx(ssize_t
*goodsfx
, const unsigned char *s
, ssize_t len
)
2291 ssize_t i
, j
, *sfx
= goodsfx
+ len
;
2293 compute_sfx(sfx
, s
, len
);
2295 for (i
= 0; i
< len
; ++i
)
2298 for (i
= len
- 1; i
>= 0; --i
)
2299 if (sfx
[i
] == i
+ 1)
2300 for (; j
< len
- 1 - i
; ++j
)
2301 if (goodsfx
[j
] == len
)
2302 goodsfx
[j
] = len
- 1 - i
;
2303 for (i
= 0; i
<= len
- 2; ++i
)
2304 goodsfx
[len
- 1 - sfx
[i
]] = len
- 1 - i
;
2307 /* Search for a constant byte string using the Boyer-Moore algorithm. */
2308 static inline unsigned char*
2309 search_buf(unsigned char *buf
, size_t buflen
, unsigned char *needle
,
2310 size_t maxidx
, ssize_t
*badchar
, ssize_t
*goodsfx
)
2313 return memchr(buf
, *needle
, buflen
);
2315 while (buflen
> maxidx
) {
2320 for (p
= buf
+ maxidx
, i
= maxidx
; p
>= buf
; --p
, --i
)
2321 if (needle
[i
] != *p
)
2326 shift
= i
+ 1 - badchar
[*p
];
2327 if (shift
< goodsfx
[i
])
2336 /* Search for a constant byte string backwards. */
2337 static inline unsigned char*
2338 search_buf_rev(unsigned char *buf
, size_t buflen
, unsigned char *needle
,
2339 size_t maxidx
, ssize_t
*badchar
, ssize_t
*goodsfx
)
2342 return memrchr(buf
, *needle
, buflen
);
2344 buf
+= buflen
- maxidx
- 1;
2345 while (buflen
> maxidx
) {
2350 for (p
= buf
, i
= maxidx
; p
<= buf
+ maxidx
; ++p
, --i
)
2351 if (needle
[i
] != *p
)
2353 if (p
> buf
+ maxidx
)
2356 shift
= i
+ 1 - badchar
[*p
];
2357 if (shift
< goodsfx
[i
])
2366 /* Search for a constant byte string using the Boyer-Moore algorithm. */
2368 find_bytestr(struct file_priv
*file
, hed_cursor_t
*from
, int dir
,
2369 unsigned char *needle
, size_t len
)
2372 ssize_t
*badchar
, *goodsfx
;
2373 unsigned char *readbuf
;
2374 unsigned char *p
, *q
;
2380 dynalloc
= calloc(sizeof(ssize_t
) * (256 + 2*len
)
2383 return HED_FINDOFF_ERROR
;
2385 goodsfx
= badchar
+ 256;
2386 readbuf
= dynalloc
+ sizeof(ssize_t
) * (256 + 2*len
);
2389 reverse(needle
, len
);
2390 compute_badchar(badchar
, needle
, len
);
2391 compute_goodsfx(goodsfx
, needle
, len
);
2394 badchar
= goodsfx
= NULL
;
2398 assert(!hed_block_is_terminal(from
->block
));
2400 allzero
= is_allzero(needle
, len
);
2401 --len
; /* simplify offset computing */
2403 ret
= HED_FINDOFF_NO_MATCH
;
2406 while (move_rel_fast(from
, -remain
),
2407 ret
&& from
->pos
>= len
) {
2409 if (!hed_prepare_read(&file
->f
, from
, SIZE_MAX
)) {
2410 ret
= HED_FINDOFF_ERROR
;
2417 if (remain
> from
->pos
)
2419 move_rel_fast(from
, -remain
);
2421 if (hed_file_cpin(&file
->f
, readbuf
,
2427 } else if (!hed_block_is_virtual(from
->block
)) {
2428 p
= from
->block
->dataobj
->data
+
2429 from
->block
->dataoff
;
2430 from
->off
-= remain
;
2431 from
->pos
-= remain
;
2433 } else if (!hed_block_is_bad(from
->block
) && allzero
) {
2442 q
= search_buf_rev(p
, remain
, needle
, len
,
2451 for ( ; ret
&& !hed_block_is_terminal(from
->block
);
2452 move_rel_fast(from
, remain
)) {
2454 remain
= hed_prepare_read(&file
->f
, from
, SIZE_MAX
);
2456 ret
= HED_FINDOFF_ERROR
;
2460 if (remain
<= len
) {
2462 remain
= copy_in(file
, readbuf
, remain
, from
);
2468 } else if (!hed_block_is_virtual(from
->block
)) {
2469 p
= from
->block
->dataobj
->data
+
2470 from
->block
->dataoff
+ from
->off
;
2471 from
->off
+= remain
;
2472 from
->pos
+= remain
;
2473 } else if (!hed_block_is_bad(from
->block
) && allzero
) {
2482 q
= search_buf(p
, remain
, needle
, len
,
2486 remain
= q
- p
- remain
;
2498 find_expr(struct file_priv
*file
, hed_cursor_t
*from
, int dir
,
2499 struct hed_expr
*expr
)
2501 size_t len
= hed_expr_len(expr
);
2505 return HED_FINDOFF_NO_MATCH
;
2513 if (hed_expr_eval(expr
) & HED_AEF_ERROR
)
2514 return HED_FINDOFF_ERROR
;
2515 buf
= hed_expr_buf(expr
);
2517 hed_dup_cursor(from
, &match
);
2518 p
= NULL
; /* bogus assignment to silence a warning */
2520 for (pos
= 0; pos
< len
; pos
++) {
2522 remain
= hed_prepare_read(&file
->f
, &match
,
2525 hed_block_is_bad(match
.block
))
2527 p
= hed_cursor_data(&match
);
2528 cursor_next_block(&match
);
2530 if ((p
? *p
++ : 0) != buf
[pos
])
2539 return HED_FINDOFF_ERROR
;
2541 if (dir
< 0 && hed_block_is_terminal(from
->block
)) {
2542 from
->pos
-= from
->off
;
2545 move_rel_fast(from
, dir
);
2546 if (hed_block_is_terminal(from
->block
))
2549 if (! (hed_expr_flags(expr
) & HED_AEF_DYNAMIC
) )
2550 return find_bytestr(file
, from
, dir
, buf
, len
);
2553 return HED_FINDOFF_NO_MATCH
;
2557 hed_file_find_expr(struct hed_file
*f
, hed_cursor_t
*pos
, int dir
,
2558 struct hed_expr
*expr
)
2560 struct file_priv
*file
= file_private(f
);
2563 assert(dir
== 1 || dir
== -1);
2565 set_readahead(file
, dir
> 0 ? HED_RA_FORWARD
: HED_RA_BACKWARD
);
2566 res
= find_expr(file
, pos
, dir
, expr
);
2567 set_readahead(file
, HED_RA_NONE
);