← Back to branch summary

~ubuntu-branches/ubuntu/vivid/parted/vivid

« back to all changes in this revision

Viewing changes to libparted/fs/r/hfs/advfs.c

  • Committer: Package Import Robot
  • Author(s): Colin Watson
  • Date: 2014-07-21 10:23:16 UTC
  • mfrom: (7.2.32 sid)
  • Revision ID: package-import@ubuntu.com-20140721102316-jsyv3yzmbo8vlde5
Tags: 3.1-3
Upload to unstable.

Show diffs side-by-side

added added

removed removed

Lines of Context:
libparted/fs/r/hfs/advfs.c
 
1
/*
 
2
    libparted - a library for manipulating disk partitions
 
3
    Copyright (C) 2004-2005, 2007, 2009-2012 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
                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
        unsigned int            block, last_bad, end_free_blocks;
 
272
 
 
273
        /* find the next block to the last bad block of the volume */
 
274
        if (!hfs_read_bad_blocks (fs))
 
275
                return 0;
 
276
 
 
277
        HfsPrivateLinkExtent*   l;
 
278
        last_bad = 0;
 
279
        for (l = priv_data->bad_blocks_xtent_list; l; l = l->next) {
 
280
                if ((unsigned int) PED_BE16_TO_CPU (l->extent.start_block)
 
281
                    + PED_BE16_TO_CPU (l->extent.block_count) > last_bad)
 
282
                        last_bad = PED_BE16_TO_CPU (l->extent.start_block)
 
283
                                   + PED_BE16_TO_CPU (l->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 */