1#include <fs/ext2.h>
2#include <stdbool.h>
3#include <stdint.h>
4
5static bool walk_dir(struct ext2_fs *fs, uint32_t block_num,
6 dir_entry_callback callback, void *ctx) {
7
8 struct bcache_entry *ent;
9 uint8_t *dir_buf = ext2_block_read(fs, block_num, out: &ent);
10 if (!dir_buf)
11 return false;
12
13 uint32_t offset = 0;
14 bool modified = false;
15
16 while (offset < fs->block_size) {
17 struct ext2_dir_entry *entry =
18 (struct ext2_dir_entry *) (dir_buf + offset);
19 if (entry->rec_len < 8 || offset + entry->rec_len > fs->block_size)
20 break;
21
22 if (callback(fs, entry, ctx, block_num, entry->inode, offset)) {
23 modified = true;
24 break;
25 }
26
27 offset += entry->rec_len;
28 }
29
30 bcache_ent_release(ent);
31
32 if (modified)
33 ext2_block_write(fs, ent, EXT2_PRIO_DIRENT);
34
35 return modified;
36}
37
38static bool walk_direct_blocks(struct ext2_fs *fs,
39 struct ext2_full_inode *inode,
40 dir_entry_callback cb, void *ctx,
41 bool ff_avail) {
42 for (uint32_t i = 0; i < 12; i++) {
43 if (!inode->node.block[i] && ff_avail) {
44 inode->node.block[i] = *(uint32_t *) ctx;
45 inode->node.blocks += fs->block_size / fs->drive->sector_size;
46 inode->node.size += fs->block_size;
47 ext2_inode_write(fs, inode_num: inode->node.block[i], inode: &inode->node);
48 return true;
49 }
50
51 if (inode->node.block[i] && walk_dir(fs, block_num: inode->node.block[i], callback: cb, ctx))
52 return true;
53 }
54 return false;
55}
56
57static bool walk_indirect(struct ext2_fs *fs, uint32_t block_num, int level,
58 dir_entry_callback cb, void *ctx, bool ff_avail,
59 struct ext2_full_inode *inode) {
60 if (block_num == 0)
61 return false;
62
63 struct bcache_entry *ent;
64 uint32_t *ptrs = (uint32_t *) ext2_block_read(fs, block_num, out: &ent);
65 if (!ptrs)
66 return false;
67
68 for (uint32_t i = 0; i < PTRS_PER_BLOCK; i++) {
69 if (!ptrs[i] && ff_avail) {
70
71 ptrs[i] = *(uint32_t *) ctx;
72
73 inode->node.blocks += fs->block_size / fs->drive->sector_size;
74 inode->node.size += fs->block_size;
75
76 bcache_ent_release(ent);
77 if (!ext2_block_write(fs, ent, EXT2_PRIO_DIRENT))
78 return false;
79 return true;
80 }
81
82 if (!ptrs[i])
83 continue;
84
85 if (level == 1) {
86 if (walk_dir(fs, block_num: ptrs[i], callback: cb, ctx)) {
87 bcache_ent_release(ent);
88 return true;
89 }
90 } else {
91 if (walk_indirect(fs, block_num: ptrs[i], level: level - 1, cb, ctx, ff_avail,
92 inode)) {
93 bcache_ent_release(ent);
94 return true;
95 }
96 }
97 }
98
99 bcache_ent_release(ent);
100 return false;
101}
102
103static bool do_walk_dir(struct ext2_fs *fs, struct ext2_full_inode *dir_inode,
104 dir_entry_callback cb, void *ctx, bool ff_avail) {
105 if (!fs || !dir_inode || !cb)
106 return false;
107
108 if (walk_direct_blocks(fs, inode: dir_inode, cb, ctx, ff_avail))
109 return true;
110
111 if (walk_indirect(fs, block_num: dir_inode->node.block[12], level: 1, cb, ctx, ff_avail,
112 inode: dir_inode))
113 return true;
114
115 if (walk_indirect(fs, block_num: dir_inode->node.block[13], level: 2, cb, ctx, ff_avail,
116 inode: dir_inode))
117 return true;
118
119 if (walk_indirect(fs, block_num: dir_inode->node.block[14], level: 3, cb, ctx, ff_avail,
120 inode: dir_inode))
121 return true;
122
123 return false;
124}
125
126static void readahead_blocks(struct ext2_fs *fs, uint32_t *entries,
127 uint32_t count, uint32_t start_index) {
128 for (uint32_t j = 1; j <= 2 && (start_index + j) < count; j++) {
129 uint32_t next = entries[start_index + j];
130 if (next)
131 ext2_prefetch_block(fs, block: next);
132 }
133}
134
135static void traverse_indirect(struct ext2_fs *fs, struct ext2_inode *inode,
136 uint32_t block_num, int depth,
137 ext2_block_visitor visitor, void *user_data,
138 bool readahead) {
139 if (depth <= 0 || block_num == 0)
140 return;
141
142 struct bcache_entry *ent;
143 uint32_t *block = (uint32_t *) ext2_block_read(fs, block_num, out: &ent);
144 if (!block)
145 return;
146
147 uint32_t size = sizeof(uint32_t);
148
149 for (uint32_t i = 0; i < fs->block_size / sizeof(uint32_t); i++) {
150 if (block[i] || depth == 1) {
151 visitor(fs, inode, depth, &block[i], user_data);
152 }
153
154 if (depth > 1 && block[i]) {
155 if (readahead)
156 readahead_blocks(fs, entries: block, count: fs->block_size / size, start_index: i);
157
158 traverse_indirect(fs, inode, block_num: block[i], depth: depth - 1, visitor,
159 user_data, readahead);
160 }
161 }
162
163 bcache_ent_release(ent);
164 ext2_block_write(fs, ent, EXT2_PRIO_DIRENT);
165}
166
167void ext2_traverse_inode_blocks(struct ext2_fs *fs, struct ext2_inode *inode,
168 ext2_block_visitor visitor, void *user_data,
169 bool readahead) {
170 for (int i = 0; i < 12; i++) {
171 if (readahead && inode->block[i])
172 ext2_prefetch_block(fs, block: inode->block[i]);
173
174 visitor(fs, inode, 0, &inode->block[i], user_data);
175 }
176
177 if (inode->block[12])
178 traverse_indirect(fs, inode, block_num: inode->block[12], depth: 1, visitor, user_data,
179 readahead);
180
181 if (inode->block[13])
182 traverse_indirect(fs, inode, block_num: inode->block[13], depth: 2, visitor, user_data,
183 readahead);
184
185 if (inode->block[14])
186 traverse_indirect(fs, inode, block_num: inode->block[14], depth: 3, visitor, user_data,
187 readahead);
188}
189
190bool ext2_walk_dir(struct ext2_fs *fs, struct ext2_full_inode *dir,
191 dir_entry_callback cb, void *ctx) {
192 return do_walk_dir(fs, dir_inode: dir, cb, ctx, false);
193}
194
195MAKE_NOP_CALLBACK;
196
197bool ext2_find_first_available(struct ext2_fs *fs, struct ext2_full_inode *dir,
198 uint32_t *new_block) {
199 return do_walk_dir(fs, dir_inode: dir, cb: nop_callback, ctx: new_block, true);
200}
201