1 /*
2 libparted - a library for manipulating disk partitions
3 Copyright (C) 2004, 2005, 2007 Free Software Foundation, Inc.
4
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; either version 3 of the License, or
8 (at your option) any later version.
9
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
14
15 You should have received a copy of the GNU General Public License
16 along with this program. If not, see <http://www.gnu.org/licenses/>.
17 */
18
19 #ifndef DISCOVER_ONLY
20
21 #include <config.h>
22
23 #include <parted/parted.h>
24 #include <parted/endian.h>
25 #include <parted/debug.h>
26 #include <stdint.h>
27
28 #if ENABLE_NLS
29 # include <libintl.h>
30 # define _(String) dgettext (PACKAGE, String)
31 #else
32 # define _(String) (String)
33 #endif /* ENABLE_NLS */
34
35 #include "hfs.h"
36 #include "file.h"
37
38 #include "advfs.h"
39
40 /* - if a < b, 0 if a == b, + if a > b */
41 /* Comparaison is done in the following order : */
42 /* CNID, then fork type, then start block */
43 /* Note that HFS implementation in linux has a bug */
44 /* in this function */
45 static int
46 hfs_extent_key_cmp(HfsPrivateGenericKey* a, HfsPrivateGenericKey* b)
47 {
48 HfsExtentKey* key1 = (HfsExtentKey*) a;
49 HfsExtentKey* key2 = (HfsExtentKey*) b;
50
51 /* do NOT use a substraction, because */
52 /* 0xFFFFFFFF - 1 = 0xFFFFFFFE so this */
53 /* would return -2, despite the fact */
54 /* 0xFFFFFFFF > 1 !!! (this is the 2.4 bug) */
55 if (key1->file_ID != key2->file_ID)
56 return PED_BE32_TO_CPU(key1->file_ID) <
57 PED_BE32_TO_CPU(key2->file_ID) ?
58 -1 : +1;
59
60 if (key1->type != key2->type)
61 return (int)(key1->type - key2->type);
62
63 if (key1->start == key2->start)
64 return 0;
65 /* the whole thing wont work with 16 bits ints */
66 /* anyway */
67 return (int)( PED_BE16_TO_CPU(key1->start) -
68 PED_BE16_TO_CPU(key2->start) );
69 }
70
71 /* do a B-Tree lookup */
72 /* read the first record immediatly inferior or egal to the given key */
73 /* return 0 on error */
74 /* record_out _must_ be large enough to receive record_size bytes */
75 /* WARNING : the compare function called only handle Extents BTree */
76 /* so modify this function if you want to do lookup in */
77 /* other BTrees has well */
78 int
79 hfs_btree_search (HfsPrivateFile* b_tree_file, HfsPrivateGenericKey* key,
80 void *record_out, unsigned int record_size,
81 HfsCPrivateLeafRec* record_ref)
82 {
83 uint8_t node[PED_SECTOR_SIZE_DEFAULT];
84 HfsHeaderRecord* header;
85 HfsNodeDescriptor* desc = (HfsNodeDescriptor*) node;
86 HfsPrivateGenericKey* record_key = NULL;
87 unsigned int node_number, record_number;
88 int i;
89
90 /* Read the header node */
91 if (!hfs_file_read_sector(b_tree_file, node, 0))
92 return 0;
93 header = ((HfsHeaderRecord*) (node + PED_BE16_TO_CPU(*((uint16_t *)
94 (node+(PED_SECTOR_SIZE_DEFAULT-2))))));
95
96 /* Get the node number of the root */
97 node_number = PED_BE32_TO_CPU(header->root_node);
98 if (!node_number)
99 return 0;
100
101 /* Read the root node */
102 if (!hfs_file_read_sector(b_tree_file, node, node_number))
103 return 0;
104
105 /* Follow the white rabbit */
106 while (1) {
107 record_number = PED_BE16_TO_CPU (desc->rec_nb);
108 for (i = record_number; i; i--) {
109 record_key = (HfsPrivateGenericKey*)
110 (node + PED_BE16_TO_CPU(*((uint16_t *)
111 (node+(PED_SECTOR_SIZE_DEFAULT - 2*i)))));
112 /* check for obvious error in FS */
113 if (((uint8_t*)record_key - node < HFS_FIRST_REC)
114 || ((uint8_t*)record_key - node
115 >= PED_SECTOR_SIZE_DEFAULT
116 - 2 * (signed)(record_number+1))) {
117 ped_exception_throw (
118 PED_EXCEPTION_ERROR,
119 PED_EXCEPTION_CANCEL,
120 _("The file system contains errors."));
121 return 0;
122 }
123 if (hfs_extent_key_cmp(record_key, key) <= 0)
124 break;
125 }
126 if (!i) return 0;
127 if (desc->type == HFS_IDX_NODE) {
128 unsigned int skip;
129
130 skip = (1 + record_key->key_length + 1) & ~1;
131 node_number = PED_BE32_TO_CPU (*((uint32_t *)
132 (((uint8_t *) record_key) + skip)));
133 if (!hfs_file_read_sector(b_tree_file, node,
134 node_number))
135 return 0;
136 } else
137 break;
138 }
139
140 /* copy the result if needed */
141 if (record_size)
142 memcpy (record_out, record_key, record_size);
143
144 /* send record reference if needed */
145 if (record_ref) {
146 record_ref->node_size = 1; /* in sectors */
147 record_ref->node_number = node_number;
148 record_ref->record_pos = (uint8_t*)record_key - node;
149 record_ref->record_number = i;
150 }
151
152 /* success */
153 return 1;
154 }
155
156 /* free the bad blocks linked list */
157 void
158 hfs_free_bad_blocks_list(HfsPrivateLinkExtent* first)
159 {
160 HfsPrivateLinkExtent* next;
161
162 while (first) {
163 next = first->next;
164 ped_free (first);
165 first = next;
166 }
167 }
168
169 /* This function reads bad blocks extents in the extents file
170 and store it in f.s. specific data of fs */
171 int
172 hfs_read_bad_blocks (const PedFileSystem *fs)
173 {
174 HfsPrivateFSData* priv_data = (HfsPrivateFSData*)
175 fs->type_specific;
176
177 if (priv_data->bad_blocks_loaded)
178 return 1;
179
180 {
181 uint8_t record[sizeof (HfsExtentKey)
182 + sizeof (HfsExtDataRec)];
183 HfsExtentKey search;
184 HfsExtentKey* ret_key = (HfsExtentKey*) record;
185 HfsExtDescriptor* ret_cache = (HfsExtDescriptor*)
186 (record + sizeof (HfsExtentKey));
187 unsigned int block, last_start, first_pass = 1;
188
189 search.key_length = sizeof (HfsExtentKey) - 1;
190 search.type = HFS_DATA_FORK;
191 search.file_ID = PED_CPU_TO_BE32 (HFS_BAD_BLOCK_ID);
192
193 last_start = -1; block = 0;
194 while (1) {
195 int i;
196
197 search.start = PED_CPU_TO_BE16 (block);
198 if (!hfs_btree_search (priv_data->extent_file,
199 (HfsPrivateGenericKey*) &search,
200 record, sizeof (record), NULL)
201 || ret_key->file_ID != search.file_ID
202 || ret_key->type != search.type) {
203 if (first_pass)
204 break;
205 else
206 goto errbb;
207 }
208 if (PED_BE16_TO_CPU (ret_key->start) == last_start)
209 break;
210
211 last_start = PED_BE16_TO_CPU (ret_key->start);
212 for (i = 0; i < HFS_EXT_NB; i++) {
213 if (ret_cache[i].block_count) {
214 HfsPrivateLinkExtent* new_xt =
215 (HfsPrivateLinkExtent*) ped_malloc (
216 sizeof (HfsPrivateLinkExtent));
217 if (!new_xt)
218 goto errbb;
219 new_xt->next = priv_data->bad_blocks_xtent_list;
220 memcpy(&(new_xt->extent), ret_cache+i,
221 sizeof (HfsExtDescriptor));
222 priv_data->bad_blocks_xtent_list = new_xt;
223 priv_data->bad_blocks_xtent_nb++;
224 block += PED_BE16_TO_CPU (
225 ret_cache[i].block_count);
226 }
227 }
228 first_pass = 0;
229 }
230
231 priv_data->bad_blocks_loaded = 1;
232 return 1;}
233
234 errbb: hfs_free_bad_blocks_list(priv_data->bad_blocks_xtent_list);
235 priv_data->bad_blocks_xtent_list=NULL;
236 priv_data->bad_blocks_xtent_nb=0;
237 return 0;
238 }
239
240 /* This function check if fblock is a bad block */
241 int
242 hfs_is_bad_block (const PedFileSystem *fs, unsigned int fblock)
243 {
244 HfsPrivateFSData* priv_data = (HfsPrivateFSData*)
245 fs->type_specific;
246 HfsPrivateLinkExtent* walk;
247
248 for (walk = priv_data->bad_blocks_xtent_list; walk; walk = walk->next) {
249 /* Won't compile without the strange cast ! gcc bug ? */
250 /* or maybe C subtilties... */
251 if ((fblock >= PED_BE16_TO_CPU (walk->extent.start_block)) &&
252 (fblock < (unsigned int) (PED_BE16_TO_CPU (
253 walk->extent.start_block)
254 + PED_BE16_TO_CPU (
255 walk->extent.block_count))))
256 return 1;
257 }
258
259 return 0;
260 }
261
262 /* This function returns the first sector of the last free block of an
263 HFS volume we can get after a hfs_pack_free_space_from_block call */
264 /* On error this function returns 0 */
265 PedSector
266 hfs_get_empty_end (const PedFileSystem *fs)
267 {
268 HfsPrivateFSData* priv_data = (HfsPrivateFSData*)
269 fs->type_specific;
270 HfsMasterDirectoryBlock* mdb = priv_data->mdb;
271 HfsPrivateLinkExtent* link;
272 unsigned int block, last_bad, end_free_blocks;
273
274 /* find the next block to the last bad block of the volume */
275 if (!hfs_read_bad_blocks (fs))
276 return 0;
277
278 last_bad = 0;
279 for (link = priv_data->bad_blocks_xtent_list; link; link = link->next) {
280 if ((unsigned int) PED_BE16_TO_CPU (link->extent.start_block)
281 + PED_BE16_TO_CPU (link->extent.block_count) > last_bad)
282 last_bad = PED_BE16_TO_CPU (link->extent.start_block)
283 + PED_BE16_TO_CPU (link->extent.block_count);
284 }
285
286 /* Count the free blocks from last_bad to the end of the volume */
287 end_free_blocks = 0;
288 for (block = last_bad;
289 block < PED_BE16_TO_CPU (mdb->total_blocks);
290 block++) {
291 if (!TST_BLOC_OCCUPATION(priv_data->alloc_map,block))
292 end_free_blocks++;
293 }
294
295 /* Calculate the block that will by the first free at the
296 end of the volume */
297 block = PED_BE16_TO_CPU (mdb->total_blocks) - end_free_blocks;
298
299 return (PedSector) PED_BE16_TO_CPU (mdb->start_block)
300 + (PedSector) block * (PED_BE32_TO_CPU (mdb->block_size)
301 / PED_SECTOR_SIZE_DEFAULT);
302 }
303
304 /* return the block which should be used to pack data to have at
305 least free fblock blocks at the end of the volume */
306 unsigned int
307 hfs_find_start_pack (const PedFileSystem *fs, unsigned int fblock)
308 {
309 HfsPrivateFSData* priv_data = (HfsPrivateFSData*)
310 fs->type_specific;
311 unsigned int block;
312
313 for (block = PED_BE16_TO_CPU (priv_data->mdb->total_blocks) - 1;
314 block && fblock;
315 block--) {
316 if (!TST_BLOC_OCCUPATION(priv_data->alloc_map,block))
317 fblock--;
318 }
319
320 while (block && !TST_BLOC_OCCUPATION(priv_data->alloc_map,block))
321 block--;
322 if (TST_BLOC_OCCUPATION(priv_data->alloc_map,block))
323 block++;
324
325 return block;
326 }
327
328 #endif /* !DISCOVER_ONLY */