/* $NetBSD$ */ /* * File "udf_bmap.c" is part of the UDFclient toolkit. * File $Id: udf_bmap.c,v 1.22 2007/11/06 18:35:27 reinoud Exp $ $Name: $ * * Copyright (c) 2003, 2004, 2005, 2006 Reinoud Zandijk * All rights reserved. * * The UDFclient toolkit is distributed under the Clarified Artistic Licence. * A copy of the licence is included in the distribution as * `LICENCE.clearified.artistic' and a copy of the licence can also be * requested at the GNU foundantion's website. * * Visit the UDFclient toolkit homepage http://www.13thmonkey.org/udftoolkit/ * * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. * */ /* XXX strip list to bare minimum XXX */ #include #include #include #include #include #include #include #include #include #include #include #include #include #include "uscsilib.h" /* for locals */ #include "udf.h" #include "udf_bswap.h" #include "udf_discop.h" #include "uio.h" #include #ifndef MAX # define MAX(a,b) ((a)>(b)?(a):(b)) # define MIN(a,b) ((a)<(b)?(a):(b)) #endif /* #define DEBUG(a) { a; } */ #define DEBUG(a) if (0) { a; } void udf_dump_allocentry_queue(char *msg, struct udf_alloc_entries *queue, uint32_t lb_size); /****************************************************************************************** * * Get and release free logical blocks from the free space tables * ******************************************************************************************/ /* * TODO calculate granularity and blk_len from disc size */ /* expirimental: granularity of metadata */ #define UDF_METADATA_GRANULARITY (32*1024 * lb_size) #define UDF_METADATA_BLK_LEN (32* 128 * lb_size) /* * simple metadata distribution algorithm; first part of each block is * metadata followed by data; the offset this blocking can be tweaked by * part_offset. */ static int udf_allocate_lbs_on_rewritables(struct udf_partition *udf_partition, uint64_t part_offset, uint32_t lb_size, uint64_t req_size, int content, uint32_t *res_start_lb, uint32_t *res_num_lbs) { struct udf_allocentry *alloc_entry, *chosen; struct udf_alloc_entries *queue; uint64_t start; uint64_t chosen_offset; uint64_t size; uint64_t part_start, part_length; int error, is_meta; /* allways unalloc_space_queue ? */ queue = &udf_partition->unalloc_space_queue; /* TODO this is a simplification; no multiple queues yet XXX */ is_meta = (content != UDF_C_USERDATA); /* start from the beginning of the unallocated space queue */ alloc_entry = TAILQ_FIRST(queue); start = alloc_entry->lb_num; assert(start == 0); chosen = NULL; chosen_offset = 0; part_start = lb_size * udf_rw32(udf_partition->partition->start_loc); part_length = lb_size * udf_rw32(udf_partition->partition->part_len); size = 0; TAILQ_FOREACH(alloc_entry, queue, next_alloc) { /* we can only start on lb_size (extra sanity check) */ assert(start % lb_size == 0); /* piecewise if nessisary */ size = MIN(alloc_entry->len, req_size); size = lb_size * (size / lb_size); if (size == 0) continue; /* we can only give out on lb_size boundaries */ assert(size % lb_size == 0); if (alloc_entry->flags == UDF_SPACE_FREE) { DEBUG(printf("got free entry from %"PRIu64" + %"PRIu64"\n", start / lb_size, (start + alloc_entry->len)/lb_size)); if (is_meta) { if (start + req_size + part_offset <= UDF_METADATA_GRANULARITY) { chosen = alloc_entry; chosen_offset = 0; } } else { chosen_offset = 0; if (start + part_offset < UDF_METADATA_GRANULARITY) { chosen_offset = UDF_METADATA_GRANULARITY - (start + part_offset); } if (chosen_offset + size <= alloc_entry->len) { chosen = alloc_entry; } } DEBUG(if (chosen && (size > 0)) printf("chosen\n")); } if (size <= 0) chosen = NULL; if (chosen) break; /* foreach */ start = start + alloc_entry->len; } /* FOREACH */ if (!chosen) return ENOSPC; assert(size > 0); assert(size % lb_size == 0); assert(chosen->len % lb_size == 0); assert(start + chosen_offset + size <= start + chosen->len); start += chosen_offset; *res_start_lb = start / lb_size; *res_num_lbs = size / lb_size; error = udf_mark_allocentry_queue(queue, lb_size, start, size, UDF_SPACE_ALLOCATED, NULL, NULL); return error; } /* get at most req_lbs from the partition and mark the area used */ static int udf_allocate_lbs_on_partition(struct udf_log_vol *udf_log_vol, uint16_t vpart_num, uint32_t req_lbs, int content, uint32_t *res_start_lb, uint32_t *res_num_lbs) { struct udf_partition *udf_partition; struct udf_part_mapping *udf_part_mapping; struct udf_alloc_entries *queue; uint64_t part_offset; uint32_t lb_size, num_lbs; uint64_t req_size; int error, cnt; assert(udf_log_vol); lb_size = udf_log_vol->lb_size; error = udf_logvol_vpart_to_partition(udf_log_vol, vpart_num, &udf_part_mapping, &udf_partition); if (error) return error; req_size = (uint64_t) lb_size * req_lbs; /* lock against corruption with free */ UDF_MUTEX_LOCK(&udf_partition->partition_space_mutex); switch (udf_part_mapping->udf_part_mapping_type) { case UDF_PART_MAPPING_PHYSICAL : case UDF_PART_MAPPING_SPARABLE : /* sparable is just like the physical mapping */ /* allways unalloc_space_queue ? */ queue = &udf_partition->unalloc_space_queue; udf_merge_allocentry_queue(queue, lb_size); DEBUG(udf_dump_allocentry_queue("Alloc ", queue, lb_size)); part_offset = 0; for (cnt = 0; cnt <= (UDF_METADATA_GRANULARITY / UDF_METADATA_BLK_LEN); cnt++) { num_lbs = 0; error = udf_allocate_lbs_on_rewritables(udf_partition, part_offset, lb_size, req_size, content, res_start_lb, &num_lbs); if (error) { assert(error == ENOSPC); /* disc is most likely getting full with (meta) data; shift window */ part_offset += UDF_METADATA_BLK_LEN; num_lbs = 0; } else { assert(num_lbs >= 1); udf_partition->free_unalloc_space -= num_lbs * lb_size; udf_log_vol->free_space -= num_lbs * lb_size; break; /* for */ } } *res_num_lbs = num_lbs; break; case UDF_PART_MAPPING_VIRTUAL : /* strict increasing virtual adress giveout */ printf("UDF: get lbs from virtual partition mapping not implemented yet\n"); return EBADF; case UDF_PART_MAPPING_META : /* select blobs from the metadata file */ if (udf_part_mapping->meta_bitmap_file == NULL) return EROFS; printf("UDF: get lbs from metadata partition mapping not implemented yet\n"); break; case UDF_PART_MAPPING_PSEUDO_RW : /* strict increasing adress giveout from the pseudo over. track */ printf("UDF: get lbs from pseudo overwritable partition not implemented yet\n"); break; } /* sanity */ if (*res_num_lbs == 0) *res_start_lb = 0; /* release partition unalloced and freed space again */ UDF_MUTEX_UNLOCK(&udf_partition->partition_space_mutex); return error; } /****************************************************************************************** * * Upper level free space allocation and releasing. * ******************************************************************************************/ int udf_allocate_lbs(struct udf_log_vol *udf_log_vol, int content, uint32_t req_lbs, char *what, uint16_t *res_vpart_num, uint32_t *res_start_lb, uint32_t *res_num_lbs) { struct udf_partition *udf_partition; struct udf_part_mapping *udf_part_mapping; uint32_t lb_size, num_lbs; uint16_t vpart_num; int is_meta, ok; int error; assert(udf_log_vol); num_lbs = 0; /* shutup gcc */ lb_size = udf_log_vol->lb_size; /* select udf partition to write to depending on the contents */ is_meta = ((content == UDF_C_FIDS) || (content == UDF_C_NODE)); vpart_num = is_meta ? udf_log_vol->metadata_vpart : udf_log_vol->data_vpart; /* TODO what about when space is freed in an earlier partition ? reset the vpart's ? */ DEBUG(printf("UDF allocate %d lbs for node `%s`\n", req_lbs, what)); do { DEBUG(printf("do: vpart_num = %d\n", vpart_num)); error = udf_logvol_vpart_to_partition(udf_log_vol, vpart_num, &udf_part_mapping, &udf_partition); ok = (udf_partition != NULL) && (udf_part_mapping != NULL); if (ok && !is_meta) ok = udf_part_mapping->data_writable; if (ok && is_meta) ok = udf_part_mapping->metadata_writable; if (ok) { /* try to snoop from this vpart */ error = udf_allocate_lbs_on_partition(udf_log_vol, vpart_num, req_lbs, content, res_start_lb, &num_lbs); if (!error) { *res_vpart_num = vpart_num; if (res_num_lbs) *res_num_lbs = num_lbs; } ok = !error; } if (!ok) { DEBUG(printf("advance vpart\n")); vpart_num = is_meta ? ++(udf_log_vol->metadata_vpart) : ++(udf_log_vol->data_vpart); if (vpart_num >= udf_log_vol->num_part_mappings) { udf_log_vol->metadata_vpart = udf_log_vol->data_vpart = 0; printf("UDF: logvol discs full ?\n"); return ENOSPC; } } } while (!ok); DEBUG(printf("udf_allocate_lbs: got space on vpart_num = %d; req %d, got %d\n", vpart_num, req_lbs, num_lbs)); assert((*res_start_lb != 0) && (num_lbs != 0)); return 0; } int udf_node_allocate_lbs(struct udf_node *udf_node, int req_lbs, uint16_t *res_vpart_num, uint32_t *res_start_lb, uint32_t *res_num_lbs) { char *what; int content; /* content can be USERDATA or FID stream here; checking on udf filetype */ switch (udf_node->udf_filetype) { case UDF_ICB_FILETYPE_DIRECTORY : case UDF_ICB_FILETYPE_STREAMDIR : content = UDF_C_FIDS; what = "FID stream"; break; default : content = UDF_C_USERDATA; what = "file content"; break; } return udf_allocate_lbs(udf_node->udf_log_vol, content, req_lbs, what, res_vpart_num, res_start_lb, res_num_lbs); } /* returns non zero if space is available */ int udf_confirm_freespace(struct udf_log_vol *udf_log_vol, int content, uint32_t size) { /* generic check for now */ if (udf_log_vol->free_space >= udf_log_vol->await_alloc_space + size + UDF_MINFREE_LOGVOL) { return 1; } return 0; } int udf_release_lbs(struct udf_log_vol *udf_log_vol, uint16_t vpart_num, uint32_t lb_num, uint64_t size) { struct udf_partition *udf_partition; struct udf_part_mapping *udf_part_mapping; struct udf_alloc_entries *queue; uint32_t lb_size; int error; if (!udf_log_vol) return 0; lb_size = udf_log_vol->lb_size; error = udf_logvol_vpart_to_partition(udf_log_vol, vpart_num, &udf_part_mapping, &udf_partition); if (error) return error; /* space can only be freed in lb_size chuncks by definition */ size = lb_size * ((size + lb_size -1) / lb_size); switch (udf_part_mapping->udf_part_mapping_type) { case UDF_PART_MAPPING_PHYSICAL : case UDF_PART_MAPPING_SPARABLE : /* sparable is just like the physical mapping */ queue = &udf_partition->unalloc_space_queue; /* TODO freed- for non sequential MO media */ UDF_MUTEX_LOCK(&udf_partition->partition_space_mutex); error = udf_mark_allocentry_queue(queue, lb_size, (uint64_t) lb_num * lb_size, size, UDF_SPACE_FREE, NULL, NULL); udf_partition->free_unalloc_space += size; udf_log_vol->free_space += size; UDF_MUTEX_UNLOCK(&udf_partition->partition_space_mutex); return error; case UDF_PART_MAPPING_VIRTUAL : /* freeing is not applicable */ return 0; case UDF_PART_MAPPING_META : /* free blobs in the metadata file */ printf("UDF: freeing lbs from metadata partition mapping not implemented yet\n"); break; case UDF_PART_MAPPING_PSEUDO_RW : /* do we have to keep a space bitmap? */ printf("UDF: freeing lbs from pseudo rewritable partition mapping not implemented yet\n"); break; } return 0; } /* !!! needs to be called with alloc entry mutex held !!! */ int udf_node_release_extent(struct udf_node *udf_node, uint64_t from, uint64_t to) { struct udf_allocentry *from_ae, *to_ae, *alloc_entry, *last_alloc_entry; uint32_t lb_size, lbnum, len; uint16_t vpart; int error, flags; assert(udf_node->alloc_mutex.locked); assert(udf_node->udf_log_vol); lb_size = udf_node->udf_log_vol->lb_size; error = udf_splitup_allocentry_queue(&udf_node->alloc_entries, lb_size, from, to-from, &from_ae, &to_ae); if (!error) { alloc_entry = from_ae; last_alloc_entry = TAILQ_NEXT(to_ae, next_alloc); while (alloc_entry != last_alloc_entry) { vpart = alloc_entry->vpart_num; lbnum = alloc_entry->lb_num; flags = alloc_entry->flags; len = alloc_entry->len; if (flags == UDF_SPACE_ALLOCATED) { error = udf_release_lbs(udf_node->udf_log_vol, vpart, lbnum, len); assert(!error); alloc_entry->flags = UDF_SPACE_FREE; /* WORM: or freed? */ } else { DEBUG(printf("udf_filepart_free_extent :freeing a non allocated piece : flags = %d\n", flags)); } alloc_entry = TAILQ_NEXT(alloc_entry, next_alloc); } } else { fprintf(stderr, "udf_filepart_free_extent: splitup failed\n"); } return 0; } /* end of udf_bmap.c */