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
37 #include "cache.h"
38
39 static HfsCPrivateCacheTable*
40 hfsc_new_cachetable(unsigned int size)
41 {
42 HfsCPrivateCacheTable* ret;
43
44 ret = (HfsCPrivateCacheTable*) ped_malloc(sizeof(*ret));
45 if (!ret) return NULL;
46
47 ret->next_cache = NULL;
48 ret->table_size = size;
49 ret->table_first_free = 0;
50
51 ret->table = ped_malloc(sizeof(*ret->table)*size);
52 if (!ret->table) { ped_free(ret); return NULL; }
53 memset(ret->table, 0, sizeof(*ret->table)*size);
54
55 return ret;
56 }
57
58 HfsCPrivateCache*
59 hfsc_new_cache(unsigned int block_number, unsigned int file_number)
60 {
61 unsigned int cachetable_size, i;
62 HfsCPrivateCache* ret;
63
64 ret = (HfsCPrivateCache*) ped_malloc(sizeof(*ret));
65 if (!ret) return NULL;
66 ret->block_number = block_number;
67 /* following code avoid integer overflow */
68 ret->linked_ref_size = block_number > block_number + ((1<<CR_SHIFT)-1) ?
69 ( block_number >> CR_SHIFT ) + 1 :
70 ( block_number + ((1<<CR_SHIFT)-1) ) >> CR_SHIFT
71 ;
72
73 ret->linked_ref = (HfsCPrivateExtent**)
74 ped_malloc( sizeof(*ret->linked_ref)
75 * ret->linked_ref_size );
76 if (!ret->linked_ref) { ped_free(ret); return NULL; }
77
78 cachetable_size = file_number + file_number / CR_OVER_DIV + CR_ADD_CST;
79 if (cachetable_size < file_number) cachetable_size = (unsigned) -1;
80 ret->first_cachetable_size = cachetable_size;
81 ret->table_list = hfsc_new_cachetable(cachetable_size);
82 if (!ret->table_list) {
83 ped_free(ret->linked_ref);
84 ped_free(ret);
85 return NULL;
86 }
87 ret->last_table = ret->table_list;
88
89 for (i = 0; i < ret->linked_ref_size; ++i)
90 ret->linked_ref[i] = NULL;
91
92 ret->needed_alloc_size = 0;
93
94 return ret;
95 }
96
97 static void
98 hfsc_delete_cachetable(HfsCPrivateCacheTable* list)
99 {
100 HfsCPrivateCacheTable* next;
101
102 while (list) {
103 ped_free (list->table);
104 next = list->next_cache;
105 ped_free (list);
106 list = next;
107 }
108 }
109
110 void
111 hfsc_delete_cache(HfsCPrivateCache* cache)
112 {
113 hfsc_delete_cachetable(cache->table_list);
114 ped_free(cache->linked_ref);
115 ped_free(cache);
116 }
117
118 HfsCPrivateExtent*
119 hfsc_cache_add_extent(HfsCPrivateCache* cache, uint32_t start, uint32_t length,
120 uint32_t block, uint16_t offset, uint8_t sbb,
121 uint8_t where, uint8_t ref_index)
122 {
123 HfsCPrivateExtent* ext;
124 unsigned int idx = start >> CR_SHIFT;
125
126 PED_ASSERT(idx < cache->linked_ref_size, return NULL);
127
128 for (ext = cache->linked_ref[idx];
129 ext && start != ext->ext_start;
130 ext = ext->next);
131
132 if (ext) {
133 ped_exception_throw (
134 PED_EXCEPTION_ERROR,
135 PED_EXCEPTION_CANCEL,
136 _("Trying to register an extent starting at block "
137 "0x%X, but another one already exists at this "
138 "position. You should check the file system!"),
139 start);
140 return NULL;
141 }
142
143 if ( cache->last_table->table_first_free
144 == cache->last_table->table_size ) {
145 cache->last_table->next_cache =
146 hfsc_new_cachetable( ( cache->first_cachetable_size
147 / CR_NEW_ALLOC_DIV )
148 + CR_ADD_CST );
149 if (!cache->last_table->next_cache)
150 return NULL;
151 cache->last_table = cache->last_table->next_cache;
152 }
153
154 ext = cache->last_table->table+(cache->last_table->table_first_free++);
155
156 ext->ext_start = start;
157 ext->ext_length = length;
158 ext->ref_block = block;
159 ext->ref_offset = offset;
160 ext->sect_by_block = sbb;
161 ext->where = where;
162 ext->ref_index = ref_index;
163
164 ext->next = cache->linked_ref[idx];
165 cache->linked_ref[idx] = ext;
166
167 cache->needed_alloc_size = cache->needed_alloc_size >
168 (unsigned) PED_SECTOR_SIZE_DEFAULT * sbb ?
169 cache->needed_alloc_size :
170 (unsigned) PED_SECTOR_SIZE_DEFAULT * sbb;
171
172 return ext;
173 }
174
175 HfsCPrivateExtent*
176 hfsc_cache_search_extent(HfsCPrivateCache* cache, uint32_t start)
177 {
178 HfsCPrivateExtent* ret;
179 unsigned int idx = start >> CR_SHIFT;
180
181 PED_ASSERT(idx < cache->linked_ref_size, return NULL);
182
183 for (ret = cache->linked_ref[idx];
184 ret && start != ret->ext_start;
185 ret = ret->next);
186
187 return ret;
188 }
189
190 /* Can't fail if extent begining at old_start exists */
191 /* Returns 0 if no such extent, or on error */
192 HfsCPrivateExtent*
193 hfsc_cache_move_extent(HfsCPrivateCache* cache, uint32_t old_start,
194 uint32_t new_start)
195 {
196 HfsCPrivateExtent** ppext;
197 HfsCPrivateExtent* pext;
198
199 unsigned int idx1 = old_start >> CR_SHIFT;
200 unsigned int idx2 = new_start >> CR_SHIFT;
201
202 PED_ASSERT(idx1 < cache->linked_ref_size, return NULL);
203 PED_ASSERT(idx2 < cache->linked_ref_size, return NULL);
204
205 for (pext = cache->linked_ref[idx2];
206 pext && new_start != pext->ext_start;
207 pext = pext->next);
208
209 if (pext) {
210 ped_exception_throw (
211 PED_EXCEPTION_BUG,
212 PED_EXCEPTION_CANCEL,
213 _("Trying to move an extent from block Ox%X to block "
214 "Ox%X, but another one already exists at this "
215 "position. This should not happen!"),
216 old_start, new_start);
217 return NULL;
218 }
219
220 for (ppext = &(cache->linked_ref[idx1]);
221 (*ppext) && old_start != (*ppext)->ext_start;
222 ppext = &((*ppext)->next));
223
224 if (!(*ppext)) return NULL;
225
226 /* removing the extent from the cache */
227 pext = *ppext;
228 (*ppext) = pext->next;
229
230 /* change ext_start and insert the extent again */
231 pext->ext_start = new_start;
232 pext->next = cache->linked_ref[idx2];
233 cache->linked_ref[idx2] = pext;
234
235 return pext;
236 }
237
238 #endif /* DISCOVER_ONLY */