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
27 #if ENABLE_NLS
28 # include <libintl.h>
29 # define _(String) dgettext (PACKAGE, String)
30 #else
31 # define _(String) (String)
32 #endif /* ENABLE_NLS */
33
34 #include "hfs.h"
35 #include "advfs.h"
36 #include "file_plus.h"
37
38 #include "advfs_plus.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 static int
44 hfsplus_extent_key_cmp(HfsPPrivateGenericKey* a, HfsPPrivateGenericKey* b)
45 {
46 HfsPExtentKey* key1 = (HfsPExtentKey*) a;
47 HfsPExtentKey* key2 = (HfsPExtentKey*) b;
48
49 if (key1->file_ID != key2->file_ID)
50 return PED_BE32_TO_CPU(key1->file_ID) <
51 PED_BE32_TO_CPU(key2->file_ID) ?
52 -1 : +1;
53
54 if (key1->type != key2->type)
55 return (int)(key1->type - key2->type);
56
57 if (key1->start == key2->start)
58 return 0;
59 return PED_BE32_TO_CPU(key1->start) <
60 PED_BE32_TO_CPU(key2->start) ?
61 -1 : +1;
62 }
63
64 /* do a B-Tree lookup */
65 /* read the first record immediatly inferior or egal to the given key */
66 /* return 0 on error */
67 /* record_out _must_ be large enough to receive the whole record (key + data) */
68 /* WARNING : the search function called only handle Extents BTree */
69 /* so modify this function if you want to do lookup in */
70 /* other BTrees has well */
71 int
72 hfsplus_btree_search (HfsPPrivateFile* b_tree_file, HfsPPrivateGenericKey* key,
73 void *record_out, unsigned int record_size,
74 HfsCPrivateLeafRec* record_ref)
75 {
76 uint8_t node_1[PED_SECTOR_SIZE_DEFAULT];
77 uint8_t* node;
78 HfsPHeaderRecord* header;
79 HfsPNodeDescriptor* desc = (HfsPNodeDescriptor*) node_1;
80 HfsPPrivateGenericKey* record_key = NULL;
81 unsigned int node_number, record_number, size, bsize;
82 int i;
83
84 /* Read the header node */
85 if (!hfsplus_file_read_sector(b_tree_file, node_1, 0))
86 return 0;
87 header = (HfsPHeaderRecord*) (node_1 + HFS_FIRST_REC);
88
89 /* Get the node number of the root */
90 node_number = PED_BE32_TO_CPU (header->root_node);
91 if (!node_number)
92 return 0;
93
94 /* Get the size of a node in sectors and allocate buffer */
95 size = (bsize = PED_BE16_TO_CPU (header->node_size)) / PED_SECTOR_SIZE_DEFAULT;
96 node = (uint8_t*) ped_malloc (bsize);
97 if (!node)
98 return 0;
99 desc = (HfsPNodeDescriptor*) node;
100
101 /* Read the root node */
102 if (!hfsplus_file_read (b_tree_file, node,
103 (PedSector) node_number * size, size))
104 return 0;
105
106 /* Follow the white rabbit */
107 while (1) {
108 record_number = PED_BE16_TO_CPU (desc->rec_nb);
109 for (i = record_number; i; i--) {
110 record_key = (HfsPPrivateGenericKey*)
111 (node + PED_BE16_TO_CPU(*((uint16_t *)
112 (node+(bsize - 2*i)))));
113 /* check for obvious error in FS */
114 if (((uint8_t*)record_key - node < HFS_FIRST_REC)
115 || ((uint8_t*)record_key - node
116 >= (signed)bsize
117 - 2 * (signed)(record_number+1))) {
118 ped_exception_throw (
119 PED_EXCEPTION_ERROR,
120 PED_EXCEPTION_CANCEL,
121 _("The file system contains errors."));
122 ped_free (node);
123 return 0;
124 }
125 if (hfsplus_extent_key_cmp(record_key, key) <= 0)
126 break;
127 }
128 if (!i) { ped_free (node); return 0; }
129 if (desc->type == HFS_IDX_NODE) {
130 unsigned int skip;
131
132 skip = ( 2 + PED_BE16_TO_CPU (record_key->key_length)
133 + 1 ) & ~1;
134 node_number = PED_BE32_TO_CPU (*((uint32_t *)
135 (((uint8_t *) record_key) + skip)));
136 if (!hfsplus_file_read(b_tree_file, node,
137 (PedSector) node_number * size,
138 size)) {
139 ped_free (node);
140 return 0;
141 }
142 } else
143 break;
144 }
145
146 /* copy the result if needed */
147 if (record_size)
148 memcpy (record_out, record_key, record_size);
149
150 /* send record reference if needed */
151 if (record_ref) {
152 record_ref->node_size = size; /* in sectors */
153 record_ref->node_number = node_number;
154 record_ref->record_pos = (uint8_t*)record_key - node;
155 record_ref->record_number = i;
156 }
157
158 /* success */
159 ped_free (node);
160 return 1;
161 }
162
163 /* free the bad blocks linked list */
164 void
165 hfsplus_free_bad_blocks_list(HfsPPrivateLinkExtent* first)
166 {
167 HfsPPrivateLinkExtent* next;
168
169 while (first) {
170 next = first->next;
171 ped_free (first);
172 first = next;
173 }
174 }
175
176 /* This function reads bad blocks extents in the extents file
177 and store it in f.s. specific data of fs */
178 int
179 hfsplus_read_bad_blocks (const PedFileSystem *fs)
180 {
181 HfsPPrivateFSData* priv_data = (HfsPPrivateFSData*)
182 fs->type_specific;
183
184 if (priv_data->bad_blocks_loaded)
185 return 1;
186
187 {
188 uint8_t record[sizeof (HfsPExtentKey)
189 + sizeof (HfsPExtDataRec)];
190 HfsPExtentKey search;
191 HfsPExtentKey* ret_key = (HfsPExtentKey*) record;
192 HfsPExtDescriptor* ret_cache = (HfsPExtDescriptor*)
193 (record + sizeof (HfsPExtentKey));
194 int block, first_pass = 1;
195 unsigned int last_start;
196
197 search.key_length = sizeof (HfsExtentKey) - 2;
198 search.type = HFS_DATA_FORK;
199 search.pad = 0;
200 search.file_ID = PED_CPU_TO_BE32 (HFS_BAD_BLOCK_ID);
201
202 last_start = -1; block = 0;
203 while (1) {
204 int i;
205
206 search.start = PED_CPU_TO_BE32 (block);
207 if (!hfsplus_btree_search (priv_data->extents_file,
208 (HfsPPrivateGenericKey*) &search,
209 record, sizeof (record), NULL)
210 || ret_key->file_ID != search.file_ID
211 || ret_key->type != search.type) {
212 if (first_pass)
213 break;
214 else
215 goto errbbp;
216 }
217 if (PED_BE32_TO_CPU (ret_key->start) == last_start)
218 break;
219
220 last_start = PED_BE32_TO_CPU (ret_key->start);
221 for (i = 0; i < HFSP_EXT_NB; i++) {
222 if (ret_cache[i].block_count) {
223 HfsPPrivateLinkExtent* new_xt =
224 (HfsPPrivateLinkExtent*) ped_malloc (
225 sizeof (HfsPPrivateLinkExtent));
226 if (!new_xt)
227 goto errbbp;
228 new_xt->next = priv_data->bad_blocks_xtent_list;
229 memcpy (&(new_xt->extent), ret_cache+i,
230 sizeof (HfsPExtDescriptor));
231 priv_data->bad_blocks_xtent_list = new_xt;
232 priv_data->bad_blocks_xtent_nb++;
233 block += PED_BE32_TO_CPU (
234 ret_cache[i].block_count);
235 }
236 }
237 first_pass = 0;
238 }
239
240 priv_data->bad_blocks_loaded = 1;
241 return 1;}
242
243 errbbp: hfsplus_free_bad_blocks_list(priv_data->bad_blocks_xtent_list);
244 priv_data->bad_blocks_xtent_list=NULL;
245 priv_data->bad_blocks_xtent_nb=0;
246 return 0;
247 }
248
249 /* This function check if fblock is a bad block */
250 int
251 hfsplus_is_bad_block (const PedFileSystem *fs, unsigned int fblock)
252 {
253 HfsPPrivateFSData* priv_data = (HfsPPrivateFSData*)
254 fs->type_specific;
255 HfsPPrivateLinkExtent* walk;
256
257 for (walk = priv_data->bad_blocks_xtent_list; walk; walk = walk->next) {
258 /* Won't compile without the strange cast ! gcc bug ? */
259 /* or maybe C subtilties... */
260 if ((fblock >= PED_BE32_TO_CPU (walk->extent.start_block)) &&
261 (fblock < (unsigned int)(PED_BE32_TO_CPU (
262 walk->extent.start_block)
263 + PED_BE32_TO_CPU (walk->extent.block_count))))
264 return 1;
265 }
266
267 return 0;
268 }
269
270 /* This function returns the first sector of the last free block of
271 an HFS+ volume we can get after a hfsplus_pack_free_space_from_block call */
272 PedSector
273 hfsplus_get_empty_end (const PedFileSystem *fs)
274 {
275 HfsPPrivateFSData* priv_data = (HfsPPrivateFSData*)
276 fs->type_specific;
277 HfsPVolumeHeader* vh = priv_data->vh;
278 HfsPPrivateLinkExtent* link;
279 unsigned int block, last_bad, end_free_blocks;
280
281 /* find the next block to the last bad block of the volume */
282 if (!hfsplus_read_bad_blocks (fs)) {
283 ped_exception_throw (
284 PED_EXCEPTION_ERROR,
285 PED_EXCEPTION_CANCEL,
286 _("Bad blocks could not be read."));
287 return 0;
288 }
289
290 last_bad = 0;
291 for (link = priv_data->bad_blocks_xtent_list; link; link = link->next) {
292 if ((unsigned int) PED_BE32_TO_CPU (link->extent.start_block)
293 + PED_BE32_TO_CPU (link->extent.block_count) > last_bad)
294 last_bad = PED_BE32_TO_CPU (link->extent.start_block)
295 + PED_BE32_TO_CPU (link->extent.block_count);
296 }
297
298 /* Count the free blocks from last_bad to the end of the volume */
299 end_free_blocks = 0;
300 for (block = last_bad;
301 block < PED_BE32_TO_CPU (vh->total_blocks);
302 block++) {
303 if (!TST_BLOC_OCCUPATION(priv_data->alloc_map,block))
304 end_free_blocks++;
305 }
306
307 /* Calculate the block that will by the first free at
308 the end of the volume */
309 block = PED_BE32_TO_CPU (vh->total_blocks) - end_free_blocks;
310
311 return (PedSector) block * ( PED_BE32_TO_CPU (vh->block_size)
312 / PED_SECTOR_SIZE_DEFAULT );
313 }
314
315 /* On error, returns 0 */
316 PedSector
317 hfsplus_get_min_size (const PedFileSystem *fs)
318 {
319 HfsPPrivateFSData* priv_data = (HfsPPrivateFSData*)
320 fs->type_specific;
321 PedSector min_size;
322
323 /* don't need to add anything because every sector
324 can be part of allocation blocks in HFS+, and
325 the last block _must_ be reserved */
326 min_size = hfsplus_get_empty_end(fs);
327 if (!min_size) return 0;
328
329 if (priv_data->wrapper) {
330 HfsPrivateFSData* hfs_priv_data = (HfsPrivateFSData*)
331 priv_data->wrapper->type_specific;
332 unsigned int hfs_sect_block;
333 PedSector hgee;
334 hfs_sect_block =
335 PED_BE32_TO_CPU (hfs_priv_data->mdb->block_size)
336 / PED_SECTOR_SIZE_DEFAULT;
337 /*
338 * if hfs+ is embedded in an hfs wrapper then the new size is :
339 * the new size of the hfs+ volume rounded up to the size
340 * of hfs blocks
341 * + the minimum size of the hfs wrapper without any hfs+
342 * modification
343 * - the current size of the hfs+ volume in the hfs wrapper
344 */
345 hgee = hfs_get_empty_end(priv_data->wrapper);
346 if (!hgee) return 0;
347 min_size = ((min_size + hfs_sect_block - 1) / hfs_sect_block)
348 * hfs_sect_block
349 + hgee + 2
350 - (PedSector) PED_BE16_TO_CPU ( hfs_priv_data->mdb
351 ->old_new.embedded
352 .location.block_count )
353 * hfs_sect_block;
354 }
355
356 return min_size;
357 }
358
359 /* return the block which should be used to pack data to have
360 at least free fblock blocks at the end of the volume */
361 unsigned int
362 hfsplus_find_start_pack (const PedFileSystem *fs, unsigned int fblock)
363 {
364 HfsPPrivateFSData* priv_data = (HfsPPrivateFSData*)
365 fs->type_specific;
366 unsigned int block;
367
368 for (block = PED_BE32_TO_CPU (priv_data->vh->total_blocks) - 1;
369 block && fblock;
370 block--) {
371 if (!TST_BLOC_OCCUPATION(priv_data->alloc_map,block))
372 fblock--;
373 }
374
375 while (block && !TST_BLOC_OCCUPATION(priv_data->alloc_map,block))
376 block--;
377 if (TST_BLOC_OCCUPATION(priv_data->alloc_map,block))
378 block++;
379
380 return block;
381 }
382
383 #endif /* !DISCOVER_ONLY */