15a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner/* 25a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner * Copyright (C) 2010 The Android Open Source Project 35a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner * 45a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner * Licensed under the Apache License, Version 2.0 (the "License"); 55a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner * you may not use this file except in compliance with the License. 65a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner * You may obtain a copy of the License at 75a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner * 85a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner * http://www.apache.org/licenses/LICENSE-2.0 95a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner * 105a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner * Unless required by applicable law or agreed to in writing, software 115a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner * distributed under the License is distributed on an "AS IS" BASIS, 125a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 135a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner * See the License for the specific language governing permissions and 145a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner * limitations under the License. 155a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner */ 165a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 175a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner#include "ext4_utils.h" 185a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner#include "allocate.h" 195a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 205a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner#include <sparse/sparse.h> 215a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 225a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner#include <stdio.h> 235a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner#include <stdlib.h> 245a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 255a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turnerstruct region_list { 265a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner struct region *first; 275a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner struct region *last; 285a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner struct region *iter; 295a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner u32 partial_iter; 305a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner}; 315a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 325a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turnerstruct block_allocation { 335a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner struct region_list list; 345a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner struct region_list oob_list; 355a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner}; 365a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 375a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turnerstruct region { 385a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner u32 block; 395a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner u32 len; 405a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner int bg; 415a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner struct region *next; 425a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner struct region *prev; 435a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner}; 445a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 455a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turnerstruct block_group_info { 465a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner u32 first_block; 475a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner int header_blocks; 485a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner int data_blocks_used; 495a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner int has_superblock; 505a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner u8 *bitmaps; 515a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner u8 *block_bitmap; 525a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner u8 *inode_bitmap; 535a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner u8 *inode_table; 545a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner u32 free_blocks; 555a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner u32 first_free_block; 565a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner u32 free_inodes; 575a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner u32 first_free_inode; 585a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner u16 flags; 595a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner u16 used_dirs; 605a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner}; 615a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 625a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turnerstruct xattr_list_element { 635a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner struct ext4_inode *inode; 645a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner struct ext4_xattr_header *header; 655a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner struct xattr_list_element *next; 665a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner}; 675a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 685a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turnerstruct block_allocation *create_allocation() 695a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner{ 705a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner struct block_allocation *alloc = malloc(sizeof(struct block_allocation)); 715a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner alloc->list.first = NULL; 725a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner alloc->list.last = NULL; 735a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner alloc->oob_list.first = NULL; 745a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner alloc->oob_list.last = NULL; 755a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner alloc->list.iter = NULL; 765a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner alloc->list.partial_iter = 0; 775a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner alloc->oob_list.iter = NULL; 785a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner alloc->oob_list.partial_iter = 0; 795a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return alloc; 805a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner} 815a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 825a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turnerstatic struct ext4_xattr_header *xattr_list_find(struct ext4_inode *inode) 835a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner{ 845a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner struct xattr_list_element *element; 855a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner for (element = aux_info.xattrs; element != NULL; element = element->next) { 865a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner if (element->inode == inode) 875a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return element->header; 885a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner } 895a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return NULL; 905a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner} 915a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 925a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turnerstatic void xattr_list_insert(struct ext4_inode *inode, struct ext4_xattr_header *header) 935a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner{ 945a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner struct xattr_list_element *element = malloc(sizeof(struct xattr_list_element)); 955a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner element->inode = inode; 965a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner element->header = header; 975a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner element->next = aux_info.xattrs; 985a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner aux_info.xattrs = element; 995a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner} 1005a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 1015a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turnerstatic void region_list_remove(struct region_list *list, struct region *reg) 1025a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner{ 1035a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner if (reg->prev) 1045a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner reg->prev->next = reg->next; 1055a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 1065a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner if (reg->next) 1075a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner reg->next->prev = reg->prev; 1085a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 1095a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner if (list->first == reg) 1105a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner list->first = reg->next; 1115a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 1125a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner if (list->last == reg) 1135a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner list->last = reg->prev; 1145a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 1155a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner reg->next = NULL; 1165a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner reg->prev = NULL; 1175a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner} 1185a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 1195a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turnerstatic void region_list_append(struct region_list *list, struct region *reg) 1205a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner{ 1215a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner if (list->first == NULL) { 1225a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner list->first = reg; 1235a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner list->last = reg; 1245a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner list->iter = reg; 1255a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner list->partial_iter = 0; 1265a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner reg->prev = NULL; 1275a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner } else { 1285a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner list->last->next = reg; 1295a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner reg->prev = list->last; 1305a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner list->last = reg; 1315a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner } 1325a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner reg->next = NULL; 1335a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner} 1345a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 1355a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner#if 0 1365a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turnerstatic void dump_starting_from(struct region *reg) 1375a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner{ 1385a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner for (; reg; reg = reg->next) { 1395a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner printf("%p: Blocks %d-%d (%d)\n", reg, 1405a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner reg->bg * info.blocks_per_group + reg->block, 1415a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner reg->bg * info.blocks_per_group + reg->block + reg->len - 1, 1425a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner reg->len); 1435a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner } 1445a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner} 1455a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 1465a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turnerstatic void dump_region_lists(struct block_allocation *alloc) { 1475a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 1485a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner printf("Main list:\n"); 1495a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner dump_starting_from(alloc->list.first); 1505a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 1515a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner printf("OOB list:\n"); 1525a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner dump_starting_from(alloc->oob_list.first); 1535a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner} 1545a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner#endif 1555a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 1565a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turnervoid append_region(struct block_allocation *alloc, 1575a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner u32 block, u32 len, int bg_num) 1585a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner{ 1595a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner struct region *reg; 1605a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner reg = malloc(sizeof(struct region)); 1615a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner reg->block = block; 1625a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner reg->len = len; 1635a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner reg->bg = bg_num; 1645a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner reg->next = NULL; 1655a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 1665a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner region_list_append(&alloc->list, reg); 1675a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner} 1685a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 1695a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turnerstatic void allocate_bg_inode_table(struct block_group_info *bg) 1705a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner{ 1715a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner if (bg->inode_table != NULL) 1725a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return; 1735a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 1745a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner u32 block = bg->first_block + 2; 1755a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 1765a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner if (bg->has_superblock) 1775a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner block += aux_info.bg_desc_blocks + info.bg_desc_reserve_blocks + 1; 1785a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 1795a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner bg->inode_table = calloc(aux_info.inode_table_blocks, info.block_size); 1805a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner if (bg->inode_table == NULL) 1815a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner critical_error_errno("calloc"); 1825a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 1835a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner sparse_file_add_data(ext4_sparse_file, bg->inode_table, 1845a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner aux_info.inode_table_blocks * info.block_size, block); 1855a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 1865a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner bg->flags &= ~EXT4_BG_INODE_UNINIT; 1875a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner} 1885a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 1895a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turnerstatic int bitmap_set_bit(u8 *bitmap, u32 bit) 1905a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner{ 1915a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner if (bitmap[bit / 8] & 1 << (bit % 8)) 1925a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return 1; 1935a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 1945a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner bitmap[bit / 8] |= 1 << (bit % 8); 1955a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return 0; 1965a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner} 1975a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 1985a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turnerstatic int bitmap_set_8_bits(u8 *bitmap, u32 bit) 1995a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner{ 2005a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner int ret = bitmap[bit / 8]; 2015a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner bitmap[bit / 8] = 0xFF; 2025a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return ret; 2035a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner} 2045a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 2055a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner/* Marks a the first num_blocks blocks in a block group as used, and accounts 2065a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner for them in the block group free block info. */ 2075a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turnerstatic int reserve_blocks(struct block_group_info *bg, u32 start, u32 num) 2085a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner{ 2095a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner unsigned int i = 0; 2105a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 2115a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner u32 block = start; 2125a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner if (num > bg->free_blocks) 2135a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return -1; 2145a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 2155a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner for (i = 0; i < num && block % 8 != 0; i++, block++) { 2165a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner if (bitmap_set_bit(bg->block_bitmap, block)) { 2175a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner error("attempted to reserve already reserved block"); 2185a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return -1; 2195a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner } 2205a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner } 2215a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 2225a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner for (; i + 8 <= (num & ~7); i += 8, block += 8) { 2235a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner if (bitmap_set_8_bits(bg->block_bitmap, block)) { 2245a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner error("attempted to reserve already reserved block"); 2255a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return -1; 2265a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner } 2275a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner } 2285a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 2295a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner for (; i < num; i++, block++) { 2305a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner if (bitmap_set_bit(bg->block_bitmap, block)) { 2315a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner error("attempted to reserve already reserved block"); 2325a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return -1; 2335a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner } 2345a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner } 2355a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 2365a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner bg->free_blocks -= num; 2375a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner if (start == bg->first_free_block) 2385a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner bg->first_free_block = start + num; 2395a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 2405a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return 0; 2415a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner} 2425a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 2435a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turnerstatic void free_blocks(struct block_group_info *bg, u32 num_blocks) 2445a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner{ 2455a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner unsigned int i; 2465a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner u32 block = bg->first_free_block - 1; 2475a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner for (i = 0; i < num_blocks; i++, block--) 2485a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner bg->block_bitmap[block / 8] &= ~(1 << (block % 8)); 2495a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner bg->free_blocks += num_blocks; 2505a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner bg->first_free_block -= num_blocks; 2515a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner} 2525a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 2535a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner/* Reduces an existing allocation by len blocks by return the last blocks 2545a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner to the free pool in their block group. Assumes that the blocks being 2555a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner returned were the last ones allocated out of the block group */ 2565a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turnervoid reduce_allocation(struct block_allocation *alloc, u32 len) 2575a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner{ 2585a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner while (len) { 2595a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner struct region *last_reg = alloc->list.last; 2605a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 2615a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner if (last_reg->len > len) { 2625a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner free_blocks(&aux_info.bgs[last_reg->bg], len); 2635a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner last_reg->len -= len; 2645a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner len = 0; 2655a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner } else { 2665a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner struct region *reg = alloc->list.last->prev; 2675a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner free_blocks(&aux_info.bgs[last_reg->bg], last_reg->len); 2685a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner len -= last_reg->len; 2695a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner if (reg) { 2705a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner reg->next = NULL; 2715a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner } else { 2725a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner alloc->list.first = NULL; 2735a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner alloc->list.last = NULL; 2745a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner alloc->list.iter = NULL; 2755a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner alloc->list.partial_iter = 0; 2765a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner } 2775a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner free(last_reg); 2785a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner } 2795a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner } 2805a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner} 2815a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 2825a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turnerstatic void init_bg(struct block_group_info *bg, unsigned int i) 2835a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner{ 2845a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner int header_blocks = 2 + aux_info.inode_table_blocks; 2855a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 2865a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner bg->has_superblock = ext4_bg_has_super_block(i); 2875a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 2885a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner if (bg->has_superblock) 2895a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner header_blocks += 1 + aux_info.bg_desc_blocks + info.bg_desc_reserve_blocks; 2905a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 2915a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner bg->bitmaps = calloc(info.block_size, 2); 2925a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner bg->block_bitmap = bg->bitmaps; 2935a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner bg->inode_bitmap = bg->bitmaps + info.block_size; 2945a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 2955a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner bg->header_blocks = header_blocks; 2965a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner bg->first_block = aux_info.first_data_block + i * info.blocks_per_group; 2975a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 2985a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner u32 block = bg->first_block; 2995a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner if (bg->has_superblock) 3005a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner block += 1 + aux_info.bg_desc_blocks + info.bg_desc_reserve_blocks; 3015a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner sparse_file_add_data(ext4_sparse_file, bg->bitmaps, 2 * info.block_size, 3025a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner block); 3035a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 3045a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner bg->data_blocks_used = 0; 3055a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner bg->free_blocks = info.blocks_per_group; 3065a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner bg->first_free_block = 0; 3075a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner bg->free_inodes = info.inodes_per_group; 3085a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner bg->first_free_inode = 1; 3095a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner bg->flags = EXT4_BG_INODE_UNINIT; 3105a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 3115a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner if (reserve_blocks(bg, bg->first_free_block, bg->header_blocks) < 0) 3125a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner error("failed to reserve %u blocks in block group %u\n", bg->header_blocks, i); 3135a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 3145a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner if (bg->first_block + info.blocks_per_group > aux_info.len_blocks) { 3155a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner u32 overrun = bg->first_block + info.blocks_per_group - aux_info.len_blocks; 3165a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner reserve_blocks(bg, info.blocks_per_group - overrun, overrun); 3175a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner } 3185a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner} 3195a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 3205a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turnervoid block_allocator_init() 3215a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner{ 3225a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner unsigned int i; 3235a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 3245a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner aux_info.bgs = calloc(sizeof(struct block_group_info), aux_info.groups); 3255a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner if (aux_info.bgs == NULL) 3265a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner critical_error_errno("calloc"); 3275a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 3285a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner for (i = 0; i < aux_info.groups; i++) 3295a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner init_bg(&aux_info.bgs[i], i); 3305a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner} 3315a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 3325a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turnervoid block_allocator_free() 3335a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner{ 3345a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner unsigned int i; 3355a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 3365a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner for (i = 0; i < aux_info.groups; i++) { 3375a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner free(aux_info.bgs[i].bitmaps); 3385a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner free(aux_info.bgs[i].inode_table); 3395a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner } 3405a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner free(aux_info.bgs); 3415a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner} 3425a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 3435a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turnerstatic u32 ext4_allocate_blocks_from_block_group(u32 len, int bg_num) 3445a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner{ 3455a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner if (get_free_blocks(bg_num) < len) 3465a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return EXT4_ALLOCATE_FAILED; 3475a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 3485a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner u32 block = aux_info.bgs[bg_num].first_free_block; 3495a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner struct block_group_info *bg = &aux_info.bgs[bg_num]; 3505a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner if (reserve_blocks(bg, bg->first_free_block, len) < 0) { 3515a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner error("failed to reserve %u blocks in block group %u\n", len, bg_num); 3525a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return EXT4_ALLOCATE_FAILED; 3535a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner } 3545a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 3555a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner aux_info.bgs[bg_num].data_blocks_used += len; 3565a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 3575a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return bg->first_block + block; 3585a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner} 3595a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 3605a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner/* Allocate a single block and return its block number */ 3615a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turneru32 allocate_block() 3625a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner{ 3635a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner unsigned int i; 3645a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner for (i = 0; i < aux_info.groups; i++) { 3655a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner u32 block = ext4_allocate_blocks_from_block_group(1, i); 3665a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 3675a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner if (block != EXT4_ALLOCATE_FAILED) 3685a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return block; 3695a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner } 3705a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 3715a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return EXT4_ALLOCATE_FAILED; 3725a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner} 3735a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 3745a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turnerstatic struct region *ext4_allocate_best_fit_partial(u32 len) 3755a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner{ 3765a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner unsigned int i; 3775a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner unsigned int found_bg = 0; 3785a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner u32 found_bg_len = 0; 3795a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 3805a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner for (i = 0; i < aux_info.groups; i++) { 3815a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner u32 bg_len = aux_info.bgs[i].free_blocks; 3825a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 3835a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner if ((len <= bg_len && (found_bg_len == 0 || bg_len < found_bg_len)) || 3845a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner (len > found_bg_len && bg_len > found_bg_len)) { 3855a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner found_bg = i; 3865a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner found_bg_len = bg_len; 3875a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner } 3885a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner } 3895a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 3905a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner if (found_bg_len) { 3915a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner u32 allocate_len = min(len, found_bg_len); 3925a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner struct region *reg; 3935a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner u32 block = ext4_allocate_blocks_from_block_group(allocate_len, found_bg); 3945a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner if (block == EXT4_ALLOCATE_FAILED) { 3955a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner error("failed to allocate %d blocks in block group %d", allocate_len, found_bg); 3965a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return NULL; 3975a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner } 3985a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner reg = malloc(sizeof(struct region)); 3995a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner reg->block = block; 4005a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner reg->len = allocate_len; 4015a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner reg->next = NULL; 4025a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner reg->prev = NULL; 4035a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner reg->bg = found_bg; 4045a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return reg; 4055a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner } else { 4065a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner error("failed to allocate %u blocks, out of space?", len); 4075a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner } 4085a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 4095a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return NULL; 4105a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner} 4115a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 4125a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turnerstatic struct region *ext4_allocate_best_fit(u32 len) 4135a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner{ 4145a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner struct region *first_reg = NULL; 4155a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner struct region *prev_reg = NULL; 4165a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner struct region *reg; 4175a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 4185a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner while (len > 0) { 4195a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner reg = ext4_allocate_best_fit_partial(len); 4205a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner if (reg == NULL) 4215a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return NULL; 4225a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 4235a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner if (first_reg == NULL) 4245a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner first_reg = reg; 4255a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 4265a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner if (prev_reg) { 4275a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner prev_reg->next = reg; 4285a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner reg->prev = prev_reg; 4295a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner } 4305a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 4315a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner prev_reg = reg; 4325a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner len -= reg->len; 4335a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner } 4345a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 4355a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return first_reg; 4365a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner} 4375a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 4385a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner/* Allocate len blocks. The blocks may be spread across multiple block groups, 4395a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner and are returned in a linked list of the blocks in each block group. The 4405a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner allocation algorithm is: 4415a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 1. If the remaining allocation is larger than any available contiguous region, 4425a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner allocate the largest contiguous region and loop 4435a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 2. Otherwise, allocate the smallest contiguous region that it fits in 4445a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner*/ 4455a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turnerstruct block_allocation *allocate_blocks(u32 len) 4465a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner{ 4475a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner struct region *reg = ext4_allocate_best_fit(len); 4485a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 4495a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner if (reg == NULL) 4505a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return NULL; 4515a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 4525a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner struct block_allocation *alloc = create_allocation(); 4535a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner alloc->list.first = reg; 4545a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner alloc->list.last = reg; 4555a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner alloc->list.iter = alloc->list.first; 4565a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner alloc->list.partial_iter = 0; 4575a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return alloc; 4585a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner} 4595a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 4605a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner/* Returns the number of discontiguous regions used by an allocation */ 4615a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turnerint block_allocation_num_regions(struct block_allocation *alloc) 4625a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner{ 4635a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner unsigned int i; 4645a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner struct region *reg = alloc->list.first; 4655a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 4665a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner for (i = 0; reg != NULL; reg = reg->next) 4675a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner i++; 4685a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 4695a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return i; 4705a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner} 4715a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 4725a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turnerint block_allocation_len(struct block_allocation *alloc) 4735a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner{ 4745a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner unsigned int i; 4755a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner struct region *reg = alloc->list.first; 4765a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 4775a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner for (i = 0; reg != NULL; reg = reg->next) 4785a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner i += reg->len; 4795a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 4805a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return i; 4815a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner} 4825a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 4835a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner/* Returns the block number of the block'th block in an allocation */ 4845a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turneru32 get_block(struct block_allocation *alloc, u32 block) 4855a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner{ 4865a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner struct region *reg = alloc->list.iter; 4875a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner block += alloc->list.partial_iter; 4885a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 4895a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner for (; reg; reg = reg->next) { 4905a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner if (block < reg->len) 4915a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return reg->block + block; 4925a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner block -= reg->len; 4935a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner } 4945a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return EXT4_ALLOCATE_FAILED; 4955a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner} 4965a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 4975a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turneru32 get_oob_block(struct block_allocation *alloc, u32 block) 4985a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner{ 4995a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner struct region *reg = alloc->oob_list.iter; 5005a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner block += alloc->oob_list.partial_iter; 5015a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 5025a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner for (; reg; reg = reg->next) { 5035a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner if (block < reg->len) 5045a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return reg->block + block; 5055a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner block -= reg->len; 5065a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner } 5075a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return EXT4_ALLOCATE_FAILED; 5085a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner} 5095a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 5105a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner/* Gets the starting block and length in blocks of the first region 5115a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner of an allocation */ 5125a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turnervoid get_region(struct block_allocation *alloc, u32 *block, u32 *len) 5135a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner{ 5145a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner *block = alloc->list.iter->block; 5155a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner *len = alloc->list.iter->len - alloc->list.partial_iter; 5165a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner} 5175a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 5185a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner/* Move to the next region in an allocation */ 5195a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turnervoid get_next_region(struct block_allocation *alloc) 5205a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner{ 5215a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner alloc->list.iter = alloc->list.iter->next; 5225a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner alloc->list.partial_iter = 0; 5235a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner} 5245a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 5255a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner/* Returns the number of free blocks in a block group */ 5265a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turneru32 get_free_blocks(u32 bg) 5275a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner{ 5285a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return aux_info.bgs[bg].free_blocks; 5295a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner} 5305a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 5315a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turnerint last_region(struct block_allocation *alloc) 5325a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner{ 5335a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return (alloc->list.iter == NULL); 5345a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner} 5355a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 5365a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turnervoid rewind_alloc(struct block_allocation *alloc) 5375a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner{ 5385a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner alloc->list.iter = alloc->list.first; 5395a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner alloc->list.partial_iter = 0; 5405a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner} 5415a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 5425a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turnerstatic struct region *do_split_allocation(struct block_allocation *alloc, u32 len) 5435a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner{ 5445a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner struct region *reg = alloc->list.iter; 5455a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner struct region *new; 5465a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner struct region *tmp; 5475a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 5485a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner while (reg && len >= reg->len) { 5495a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner len -= reg->len; 5505a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner reg = reg->next; 5515a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner } 5525a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 5535a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner if (reg == NULL && len > 0) 5545a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return NULL; 5555a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 5565a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner if (len > 0) { 5575a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner new = malloc(sizeof(struct region)); 5585a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 5595a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner new->bg = reg->bg; 5605a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner new->block = reg->block + len; 5615a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner new->len = reg->len - len; 5625a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner new->next = reg->next; 5635a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner new->prev = reg; 5645a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 5655a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner reg->next = new; 5665a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner reg->len = len; 5675a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 5685a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner tmp = alloc->list.iter; 5695a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner alloc->list.iter = new; 5705a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return tmp; 5715a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner } else { 5725a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return reg; 5735a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner } 5745a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner} 5755a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 5765a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner/* Splits an allocation into two allocations. The returned allocation will 5775a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner point to the first half, and the original allocation ptr will point to the 5785a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner second half. */ 5795a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turnerstatic struct region *split_allocation(struct block_allocation *alloc, u32 len) 5805a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner{ 5815a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner /* First make sure there is a split at the current ptr */ 5825a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner do_split_allocation(alloc, alloc->list.partial_iter); 5835a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 5845a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner /* Then split off len blocks */ 5855a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner struct region *middle = do_split_allocation(alloc, len); 5865a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner alloc->list.partial_iter = 0; 5875a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return middle; 5885a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner} 5895a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 5905a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner/* Reserve the next blocks for oob data (indirect or extent blocks) */ 5915a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turnerint reserve_oob_blocks(struct block_allocation *alloc, int blocks) 5925a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner{ 5935a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner struct region *oob = split_allocation(alloc, blocks); 5945a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner struct region *next; 5955a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 5965a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner if (oob == NULL) 5975a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return -1; 5985a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 5995a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner while (oob && oob != alloc->list.iter) { 6005a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner next = oob->next; 6015a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner region_list_remove(&alloc->list, oob); 6025a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner region_list_append(&alloc->oob_list, oob); 6035a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner oob = next; 6045a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner } 6055a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 6065a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return 0; 6075a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner} 6085a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 6095a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turnerstatic int advance_list_ptr(struct region_list *list, int blocks) 6105a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner{ 6115a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner struct region *reg = list->iter; 6125a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 6135a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner while (reg != NULL && blocks > 0) { 6145a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner if (reg->len > list->partial_iter + blocks) { 6155a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner list->partial_iter += blocks; 6165a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return 0; 6175a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner } 6185a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 6195a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner blocks -= (reg->len - list->partial_iter); 6205a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner list->partial_iter = 0; 6215a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner reg = reg->next; 6225a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner } 6235a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 6245a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner if (blocks > 0) 6255a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return -1; 6265a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 6275a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return 0; 6285a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner} 6295a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 6305a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner/* Move the allocation pointer forward */ 6315a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turnerint advance_blocks(struct block_allocation *alloc, int blocks) 6325a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner{ 6335a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return advance_list_ptr(&alloc->list, blocks); 6345a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner} 6355a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 6365a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turnerint advance_oob_blocks(struct block_allocation *alloc, int blocks) 6375a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner{ 6385a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return advance_list_ptr(&alloc->oob_list, blocks); 6395a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner} 6405a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 6415a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turnerint append_oob_allocation(struct block_allocation *alloc, u32 len) 6425a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner{ 6435a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner struct region *reg = ext4_allocate_best_fit(len); 6445a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 6455a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner if (reg == NULL) { 6465a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner error("failed to allocate %d blocks", len); 6475a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return -1; 6485a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner } 6495a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 6505a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner for (; reg; reg = reg->next) 6515a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner region_list_append(&alloc->oob_list, reg); 6525a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 6535a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return 0; 6545a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner} 6555a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 6565a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner/* Returns an ext4_inode structure for an inode number */ 6575a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turnerstruct ext4_inode *get_inode(u32 inode) 6585a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner{ 6595a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner inode -= 1; 6605a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner int bg = inode / info.inodes_per_group; 6615a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner inode %= info.inodes_per_group; 6625a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 6635a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner allocate_bg_inode_table(&aux_info.bgs[bg]); 6645a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return (struct ext4_inode *)(aux_info.bgs[bg].inode_table + inode * 6655a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner info.inode_size); 6665a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner} 6675a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 6685a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turnerstruct ext4_xattr_header *get_xattr_block_for_inode(struct ext4_inode *inode) 6695a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner{ 6705a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner struct ext4_xattr_header *block = xattr_list_find(inode); 6715a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner if (block != NULL) 6725a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return block; 6735a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 6745a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner u32 block_num = allocate_block(); 6755a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner block = calloc(info.block_size, 1); 6765a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner if (block == NULL) { 6775a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner error("get_xattr: failed to allocate %d", info.block_size); 6785a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return NULL; 6795a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner } 6805a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 6815a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner block->h_magic = cpu_to_le32(EXT4_XATTR_MAGIC); 6825a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner block->h_refcount = cpu_to_le32(1); 6835a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner block->h_blocks = cpu_to_le32(1); 6845a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner inode->i_blocks_lo = cpu_to_le32(le32_to_cpu(inode->i_blocks_lo) + (info.block_size / 512)); 6855a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner inode->i_file_acl_lo = cpu_to_le32(block_num); 6865a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 6875a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner int result = sparse_file_add_data(ext4_sparse_file, block, info.block_size, block_num); 6885a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner if (result != 0) { 6895a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner error("get_xattr: sparse_file_add_data failure %d", result); 6905a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner free(block); 6915a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return NULL; 6925a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner } 6935a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner xattr_list_insert(inode, block); 6945a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return block; 6955a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner} 6965a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 6975a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner/* Mark the first len inodes in a block group as used */ 6985a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turneru32 reserve_inodes(int bg, u32 num) 6995a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner{ 7005a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner unsigned int i; 7015a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner u32 inode; 7025a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 7035a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner if (get_free_inodes(bg) < num) 7045a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return EXT4_ALLOCATE_FAILED; 7055a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 7065a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner for (i = 0; i < num; i++) { 7075a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner inode = aux_info.bgs[bg].first_free_inode + i - 1; 7085a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner aux_info.bgs[bg].inode_bitmap[inode / 8] |= 1 << (inode % 8); 7095a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner } 7105a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 7115a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner inode = aux_info.bgs[bg].first_free_inode; 7125a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 7135a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner aux_info.bgs[bg].first_free_inode += num; 7145a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner aux_info.bgs[bg].free_inodes -= num; 7155a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 7165a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return inode; 7175a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner} 7185a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 7195a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner/* Returns the first free inode number 7205a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner TODO: Inodes should be allocated in the block group of the data? */ 7215a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turneru32 allocate_inode() 7225a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner{ 7235a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner unsigned int bg; 7245a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner u32 inode; 7255a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 7265a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner for (bg = 0; bg < aux_info.groups; bg++) { 7275a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner inode = reserve_inodes(bg, 1); 7285a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner if (inode != EXT4_ALLOCATE_FAILED) 7295a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return bg * info.inodes_per_group + inode; 7305a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner } 7315a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 7325a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return EXT4_ALLOCATE_FAILED; 7335a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner} 7345a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 7355a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner/* Returns the number of free inodes in a block group */ 7365a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turneru32 get_free_inodes(u32 bg) 7375a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner{ 7385a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return aux_info.bgs[bg].free_inodes; 7395a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner} 7405a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 7415a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner/* Increments the directory count of the block group that contains inode */ 7425a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turnervoid add_directory(u32 inode) 7435a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner{ 7445a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner int bg = (inode - 1) / info.inodes_per_group; 7455a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner aux_info.bgs[bg].used_dirs += 1; 7465a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner} 7475a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 7485a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner/* Returns the number of inodes in a block group that are directories */ 7495a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turneru16 get_directories(int bg) 7505a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner{ 7515a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return aux_info.bgs[bg].used_dirs; 7525a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner} 7535a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 7545a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner/* Returns the flags for a block group */ 7555a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turneru16 get_bg_flags(int bg) 7565a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner{ 7575a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner return aux_info.bgs[bg].flags; 7585a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner} 7595a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 7605a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner/* Frees the memory used by a linked list of allocation regions */ 7615a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turnervoid free_alloc(struct block_allocation *alloc) 7625a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner{ 7635a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner struct region *reg; 7645a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 7655a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner reg = alloc->list.first; 7665a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner while (reg) { 7675a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner struct region *next = reg->next; 7685a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner free(reg); 7695a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner reg = next; 7705a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner } 7715a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 7725a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner reg = alloc->oob_list.first; 7735a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner while (reg) { 7745a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner struct region *next = reg->next; 7755a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner free(reg); 7765a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner reg = next; 7775a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner } 7785a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner 7795a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner free(alloc); 7805a60dc51ef5c2b97db192244e79b12ad03ee885eDavid 'Digit' Turner} 781