1 /* $NetBSD$ */
2
3 /*
4 * File "udf_allocentries.c" is part of the UDFclient toolkit.
5 * File $Id: udf_allocentries.c,v 1.13 2016/04/25 21:01:40 reinoud Exp $ $Name: $
6 *
7 * Copyright (c) 2003, 2004, 2005, 2006, 2011
8 * Reinoud Zandijk <reinoud@netbsd.org>
9 * All rights reserved.
10 *
11 * The UDFclient toolkit is distributed under the Clarified Artistic Licence.
12 * A copy of the licence is included in the distribution as
13 * `LICENCE.clearified.artistic' and a copy of the licence can also be
14 * requested at the GNU foundantion's website.
15 *
16 * Visit the UDFclient toolkit homepage http://www.13thmonkey.org/udftoolkit/
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
19 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
20 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
21 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
22 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
23 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
27 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 *
29 */
30
31
32 /* XXX strip list to bare minimum XXX */
33 #include <stdio.h>
34 #include <fcntl.h>
35 #include <stdlib.h>
36 #include <errno.h>
37 #include <sys/types.h>
38 #include <sys/stat.h>
39 #include <unistd.h>
40 #include <assert.h>
41 #include <dirent.h>
42 #include <string.h>
43 #include <strings.h>
44 #include <limits.h>
45 #include <time.h>
46
47 #include "uscsilib.h"
48
49
50 /* for locals */
51 #include "udf.h"
52 #include "udf_bswap.h"
53 #include "udf_discop.h"
54 #include "uio.h"
55 #include <pthread.h>
56
57
58 /* for scsilib */
59 extern const char *dvname;
60
61
62 #ifndef MAX
63 # define MAX(a,b) ((a)>(b)?(a):(b))
64 # define MIN(a,b) ((a)<(b)?(a):(b))
65 #endif
66
67
68 /* #define DEBUG(a) { a; } */
69 #define DEBUG(a) if (0) { a; }
70
71
72 /* XXX TODO support non lb_size splits ?? TODO XXX */
73
74 /******************************************************************************************
75 *
76 * Basic operations on udf_alloc_entries queues
77 *
78 ******************************************************************************************/
79
80
udf_merge_allocentry_queue(struct udf_alloc_entries * queue,uint32_t lb_size)81 void udf_merge_allocentry_queue(struct udf_alloc_entries *queue, uint32_t lb_size) {
82 struct udf_allocentry *alloc_entry, *next_alloc;
83 uint64_t this_end, next_start;
84 int merge;
85
86 TAILQ_FOREACH(alloc_entry, queue, next_alloc) {
87 do {
88 merge = 0;
89
90 /* only non busy ; prolly old cruft? */
91 if (alloc_entry->flags == UDF_SPACE_FREED) break;
92
93 next_alloc = TAILQ_NEXT(alloc_entry, next_alloc);
94 if (next_alloc) {
95 if (next_alloc->flags != alloc_entry->flags) break;
96
97 if (alloc_entry->flags == UDF_SPACE_ALLOCATED) {
98 /* merge on virtual/physical lb_num base; they are automatically adjacent on offset */
99 if (next_alloc->vpart_num != alloc_entry->vpart_num) break;
100 this_end = alloc_entry->lb_num * lb_size + alloc_entry->len;
101 next_start = next_alloc->lb_num * lb_size;
102
103 if (this_end != next_start) break;
104 }
105
106 /* Only merge if merge would result in a legal UDF allocation size */
107 if (((uint64_t) alloc_entry->len + (uint64_t) next_alloc->len) > ((uint64_t) 1<<30)-1) break;
108
109 /* merge! */
110 alloc_entry->len = alloc_entry->len + next_alloc->len;
111 TAILQ_REMOVE(queue, next_alloc, next_alloc);
112 free(next_alloc);
113 merge = 1;
114 }
115 } while (merge);
116 } /* foreach */
117 }
118
119
120 /* Splits up allocated pieces so that there is a break on `offset' */
udf_cut_allocentry_queue(struct udf_alloc_entries * queue,uint32_t lb_size,uint64_t offset)121 int udf_cut_allocentry_queue(struct udf_alloc_entries *queue, uint32_t lb_size, uint64_t offset) {
122 struct udf_allocentry *entry, *new_entry;
123 uint64_t cur_offset;
124 uint64_t total_length, extra_length, max_slot, new_length;
125 uint64_t entry_offset;
126
127 total_length = 0;
128 TAILQ_FOREACH(entry, queue, next_alloc) {
129 total_length += entry->len;
130 }
131
132 /* printf("Cutting up at offset %ld (lb %ld)\n", offset, offset / lb_size); */
133 if (offset < total_length) {
134 /* split */
135 cur_offset = 0;
136 TAILQ_FOREACH(entry, queue, next_alloc) {
137 if ((offset >= cur_offset) && (offset < cur_offset + entry->len)) {
138 /* overlap */
139 entry_offset = offset - cur_offset;
140 entry_offset = (entry_offset / lb_size) * lb_size;
141 assert(entry_offset % lb_size == 0);
142 if (entry_offset == 0) return 0;
143
144 /* clone the current space */
145 new_entry = calloc(1, sizeof(struct udf_allocentry));
146 if (!new_entry) return ENOMEM;
147 memcpy(new_entry, entry, sizeof(struct udf_allocentry));
148
149 /* split! */
150 /* printf("split up lb %d + lb %d due to lb offset = %ld\n", entry->lb_num, entry->len / lb_size, entry_offset); */
151
152 entry->len = entry_offset;
153 new_entry->len -= entry_offset;
154 new_entry->lb_num += entry_offset / lb_size;
155 TAILQ_INSERT_AFTER(queue, entry, new_entry, next_alloc);
156 DEBUG(printf("split up due to lb offset = %d\n", (int) entry_offset));
157 return 0;
158 }
159 cur_offset += entry->len;
160 }
161 printf("Sanity check: i can't be here\n");
162 exit(1);
163 }
164
165 /* no use to do more if we're there */
166 if (offset == total_length) return 0;
167
168 /*
169 * Glue extra piece on the queue (auto-extending)
170 * see if we reached our `goal'; see if we can just extent the last
171 * allocation entry but NEVER more or equal to one block size for that
172 * would alter semantics.
173 */
174 entry = TAILQ_LAST(queue, udf_alloc_entries);
175 if (!TAILQ_EMPTY(queue)) {
176 extra_length = (uint64_t) lb_size*(((uint64_t) entry->len + lb_size -1) / lb_size) - entry->len;
177 extra_length = MIN(extra_length, (offset - total_length));
178 /* keep semantics: only meant for extending upto blocksize */
179 if (extra_length < lb_size) {
180 entry->len += extra_length;
181 total_length += extra_length;
182 }
183 }
184
185 max_slot = ((((uint64_t) 1<<30)-1) / lb_size) * lb_size;
186 while (offset > total_length) {
187 /* grow queue by adding difference as a zero unallocated space */
188 new_length = offset - total_length;
189 new_length = MIN(max_slot, new_length);
190
191 new_entry = calloc(1, sizeof(struct udf_allocentry));
192 if (!new_entry) return ENOMEM;
193
194 new_entry->len = new_length;
195 new_entry->flags = UDF_SPACE_FREE;
196 TAILQ_INSERT_TAIL(queue, new_entry, next_alloc);
197
198 total_length += new_entry->len;
199 } /* while */
200
201 return 0;
202 }
203
204
205 /* Splits up allocated pieces so that there is a break on `data_offset' and on `data_offset + data_length' */
udf_splitup_allocentry_queue(struct udf_alloc_entries * queue,uint32_t lb_size,uint64_t data_offset,uint64_t data_length,struct udf_allocentry ** res_firstae,struct udf_allocentry ** res_lastae)206 int udf_splitup_allocentry_queue(struct udf_alloc_entries *queue, uint32_t lb_size, uint64_t data_offset, uint64_t data_length, struct udf_allocentry **res_firstae, struct udf_allocentry **res_lastae) {
207 struct udf_allocentry *entry, *prev_entry;
208 uint64_t cur_offset, len;
209
210 entry = prev_entry = NULL;
211 #if 0
212 printf("Split %ld + %ld : \n", data_offset, data_length);
213 printf("PRE SPLIT block = lb %d + lb %d (%ld bytes)\n", (int) (data_offset / lb_size), (int) (data_length / lb_size), data_length);
214 TAILQ_FOREACH(entry, queue, next_alloc) {
215 printf("\t(lb %08d + lb %08d[+ %d]) flag %d\n", entry->lb_num, entry->len/lb_size, entry->len % lb_size, entry->flags);
216 }
217 printf("END PRE\n");
218 #endif
219
220 /* cut the string at the specified places */
221 (void) udf_cut_allocentry_queue(queue, lb_size, data_offset);
222 (void) udf_cut_allocentry_queue(queue, lb_size, data_offset + data_length);
223
224 #if 0
225 printf("POST SPLIT\n");
226 TAILQ_FOREACH(entry, queue, next_alloc) {
227 printf("\t(lb %08d + lb %08d[+ %d]) flag %d\n", entry->lb_num, entry->len/lb_size, entry->len % lb_size, entry->flags);
228 }
229 printf("END POST\n\n");
230 #endif
231
232 if ((res_firstae == NULL) && (res_lastae == NULL)) return 0;
233
234 if (res_firstae) *res_firstae = NULL;
235 if (res_lastae) *res_lastae = NULL;
236
237 DEBUG(printf("SEARCH SPLIT block = %"PRIu64" + %"PRIu64"\n", (data_offset / lb_size), (data_length / lb_size)));
238 /* search the element-range this splitting induced */
239 cur_offset = 0;
240 entry = TAILQ_FIRST(queue);
241 while (entry) {
242 len = entry->len;
243
244 DEBUG(printf("\t(%d + %d) flag %d\n", (int) entry->lb_num, (int) entry->len, (int) entry->flags));
245 if (cur_offset + len > data_offset) {
246 if (res_firstae) *res_firstae = entry;
247 DEBUG(printf("\t\tReturned as first\n"));
248 break;
249 }
250 /* advance */
251 cur_offset += len;
252 entry = TAILQ_NEXT(entry, next_alloc);
253 }
254 prev_entry = entry;
255 while (entry) {
256 len = entry->len;
257
258 if (cur_offset + len > data_offset + data_length) {
259 break;
260 }
261 DEBUG(printf("\t(%d + %d) flag %d\n", (int) entry->lb_num, (int) entry->len, (int) entry->flags));
262
263 /* advance */
264 cur_offset += len;
265 prev_entry = entry;
266 entry = TAILQ_NEXT(entry, next_alloc);
267 }
268 if (res_lastae) *res_lastae = prev_entry;
269 DEBUG(printf("\t\tReturned as last\n\t<skip>\n"));
270
271 DEBUG(printf("END POST\n\n"));
272
273 if (res_firstae) assert(*res_firstae);
274 if (res_lastae) assert(*res_lastae);
275
276 return 0;
277 }
278
279
280 /* mark a piece with the specified `mark' with no side-effects */
281 /* tested OK */
udf_mark_allocentry_queue(struct udf_alloc_entries * queue,uint32_t lb_size,uint64_t data_offset,uint64_t data_length,int mark,struct udf_allocentry ** res_firstae,struct udf_allocentry ** res_lastae)282 int udf_mark_allocentry_queue(struct udf_alloc_entries *queue, uint32_t lb_size, uint64_t data_offset, uint64_t data_length, int mark, struct udf_allocentry **res_firstae, struct udf_allocentry **res_lastae) {
283 struct udf_allocentry *alloc_entry, *first_alloc_entry, *last_alloc_entry;
284 int error;
285
286 DEBUG(printf("mark %d\n", mark));
287 /* first split up so we don't have to worry about boundaries */
288 error = udf_splitup_allocentry_queue(queue, lb_size, data_offset, data_length, &first_alloc_entry, &last_alloc_entry);
289 assert(error == 0);
290
291 alloc_entry = first_alloc_entry;
292 /* inclusive last_alloc_entry */
293 last_alloc_entry = TAILQ_NEXT(last_alloc_entry, next_alloc);
294 while (alloc_entry != last_alloc_entry) {
295 DEBUG(printf("marking %d + %d into type %d\n", alloc_entry->lb_num, alloc_entry->len/lb_size, mark);)
296 alloc_entry->flags = mark;
297 alloc_entry = TAILQ_NEXT(alloc_entry, next_alloc);
298 }
299
300 if (res_firstae) *res_firstae = first_alloc_entry;
301 if (res_lastae) *res_lastae = last_alloc_entry;
302
303 return 0;
304 }
305
306
udf_extent_properties(struct udf_alloc_entries * queue,uint32_t lb_size,uint64_t from,uint64_t to,int * res_all_allocated)307 int udf_extent_properties(struct udf_alloc_entries *queue, uint32_t lb_size, uint64_t from, uint64_t to, int *res_all_allocated) {
308 struct udf_allocentry *alloc_entry, *first_alloc_entry, *last_alloc_entry;
309 int all_allocated, error;
310
311 /* first split up so we don't have to worry about boundaries */
312 error = udf_splitup_allocentry_queue(queue, lb_size, from, to-from, &first_alloc_entry, &last_alloc_entry);
313 assert(error == 0);
314
315 /* inclusive last_alloc_entry */
316 alloc_entry = first_alloc_entry;
317 last_alloc_entry = TAILQ_NEXT(last_alloc_entry, next_alloc);
318 all_allocated = 1;
319 while (alloc_entry != last_alloc_entry) {
320 all_allocated = all_allocated && ((alloc_entry->flags == UDF_SPACE_ALLOCATED) || (alloc_entry->flags == UDF_SPACE_ALLOCATED_BUT_NOT_USED));
321 alloc_entry = TAILQ_NEXT(alloc_entry, next_alloc);
322 }
323 if (res_all_allocated) *res_all_allocated = all_allocated;
324
325 return 0;
326 }
327
328
udf_dump_allocentry_queue(char * msg,struct udf_alloc_entries * queue,uint32_t lb_size)329 void udf_dump_allocentry_queue(char *msg, struct udf_alloc_entries *queue, uint32_t lb_size) {
330 struct udf_allocentry *entry;
331 uint64_t offset;
332
333 printf("\n%s :", msg);
334 offset = 0;
335 TAILQ_FOREACH(entry, queue, next_alloc) {
336 printf(" [%d : lb %08d till lb %08d] mapped on (lb %d + %d bytes) ",
337 entry->flags, (uint32_t) (offset/lb_size), (uint32_t) (offset + entry->len)/lb_size-1,
338 (uint32_t) (entry->lb_num/lb_size), (uint32_t) entry->len);
339 offset += entry->len;
340 }
341 printf("\n");
342 }
343
344
345 /* end of udf_allocentries.c */
346
347