balloc.c 24 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953
  1. /*
  2. * balloc.c
  3. *
  4. * PURPOSE
  5. * Block allocation handling routines for the OSTA-UDF(tm) filesystem.
  6. *
  7. * COPYRIGHT
  8. * This file is distributed under the terms of the GNU General Public
  9. * License (GPL). Copies of the GPL can be obtained from:
  10. * ftp://prep.ai.mit.edu/pub/gnu/GPL
  11. * Each contributing author retains all rights to their own work.
  12. *
  13. * (C) 1999-2001 Ben Fennema
  14. * (C) 1999 Stelias Computing Inc
  15. *
  16. * HISTORY
  17. *
  18. * 02/24/99 blf Created.
  19. *
  20. */
  21. #include "udfdecl.h"
  22. #include <linux/quotaops.h>
  23. #include <linux/buffer_head.h>
  24. #include <linux/bitops.h>
  25. #include "udf_i.h"
  26. #include "udf_sb.h"
  27. #define udf_clear_bit(nr,addr) ext2_clear_bit(nr,addr)
  28. #define udf_set_bit(nr,addr) ext2_set_bit(nr,addr)
  29. #define udf_test_bit(nr, addr) ext2_test_bit(nr, addr)
  30. #define udf_find_first_one_bit(addr, size) find_first_one_bit(addr, size)
  31. #define udf_find_next_one_bit(addr, size, offset) find_next_one_bit(addr, size, offset)
  32. #define leBPL_to_cpup(x) leNUM_to_cpup(BITS_PER_LONG, x)
  33. #define leNUM_to_cpup(x,y) xleNUM_to_cpup(x,y)
  34. #define xleNUM_to_cpup(x,y) (le ## x ## _to_cpup(y))
  35. #define uintBPL_t uint(BITS_PER_LONG)
  36. #define uint(x) xuint(x)
  37. #define xuint(x) __le ## x
  38. static inline int find_next_one_bit (void * addr, int size, int offset)
  39. {
  40. uintBPL_t * p = ((uintBPL_t *) addr) + (offset / BITS_PER_LONG);
  41. int result = offset & ~(BITS_PER_LONG-1);
  42. unsigned long tmp;
  43. if (offset >= size)
  44. return size;
  45. size -= result;
  46. offset &= (BITS_PER_LONG-1);
  47. if (offset)
  48. {
  49. tmp = leBPL_to_cpup(p++);
  50. tmp &= ~0UL << offset;
  51. if (size < BITS_PER_LONG)
  52. goto found_first;
  53. if (tmp)
  54. goto found_middle;
  55. size -= BITS_PER_LONG;
  56. result += BITS_PER_LONG;
  57. }
  58. while (size & ~(BITS_PER_LONG-1))
  59. {
  60. if ((tmp = leBPL_to_cpup(p++)))
  61. goto found_middle;
  62. result += BITS_PER_LONG;
  63. size -= BITS_PER_LONG;
  64. }
  65. if (!size)
  66. return result;
  67. tmp = leBPL_to_cpup(p);
  68. found_first:
  69. tmp &= ~0UL >> (BITS_PER_LONG-size);
  70. found_middle:
  71. return result + ffz(~tmp);
  72. }
  73. #define find_first_one_bit(addr, size)\
  74. find_next_one_bit((addr), (size), 0)
  75. static int read_block_bitmap(struct super_block * sb,
  76. struct udf_bitmap *bitmap, unsigned int block, unsigned long bitmap_nr)
  77. {
  78. struct buffer_head *bh = NULL;
  79. int retval = 0;
  80. kernel_lb_addr loc;
  81. loc.logicalBlockNum = bitmap->s_extPosition;
  82. loc.partitionReferenceNum = UDF_SB_PARTITION(sb);
  83. bh = udf_tread(sb, udf_get_lb_pblock(sb, loc, block));
  84. if (!bh)
  85. {
  86. retval = -EIO;
  87. }
  88. bitmap->s_block_bitmap[bitmap_nr] = bh;
  89. return retval;
  90. }
  91. static int __load_block_bitmap(struct super_block * sb,
  92. struct udf_bitmap *bitmap, unsigned int block_group)
  93. {
  94. int retval = 0;
  95. int nr_groups = bitmap->s_nr_groups;
  96. if (block_group >= nr_groups)
  97. {
  98. udf_debug("block_group (%d) > nr_groups (%d)\n", block_group, nr_groups);
  99. }
  100. if (bitmap->s_block_bitmap[block_group])
  101. return block_group;
  102. else
  103. {
  104. retval = read_block_bitmap(sb, bitmap, block_group, block_group);
  105. if (retval < 0)
  106. return retval;
  107. return block_group;
  108. }
  109. }
  110. static inline int load_block_bitmap(struct super_block * sb,
  111. struct udf_bitmap *bitmap, unsigned int block_group)
  112. {
  113. int slot;
  114. slot = __load_block_bitmap(sb, bitmap, block_group);
  115. if (slot < 0)
  116. return slot;
  117. if (!bitmap->s_block_bitmap[slot])
  118. return -EIO;
  119. return slot;
  120. }
  121. static void udf_bitmap_free_blocks(struct super_block * sb,
  122. struct inode * inode,
  123. struct udf_bitmap *bitmap,
  124. kernel_lb_addr bloc, uint32_t offset, uint32_t count)
  125. {
  126. struct udf_sb_info *sbi = UDF_SB(sb);
  127. struct buffer_head * bh = NULL;
  128. unsigned long block;
  129. unsigned long block_group;
  130. unsigned long bit;
  131. unsigned long i;
  132. int bitmap_nr;
  133. unsigned long overflow;
  134. mutex_lock(&sbi->s_alloc_mutex);
  135. if (bloc.logicalBlockNum < 0 ||
  136. (bloc.logicalBlockNum + count) > UDF_SB_PARTLEN(sb, bloc.partitionReferenceNum))
  137. {
  138. udf_debug("%d < %d || %d + %d > %d\n",
  139. bloc.logicalBlockNum, 0, bloc.logicalBlockNum, count,
  140. UDF_SB_PARTLEN(sb, bloc.partitionReferenceNum));
  141. goto error_return;
  142. }
  143. block = bloc.logicalBlockNum + offset + (sizeof(struct spaceBitmapDesc) << 3);
  144. do_more:
  145. overflow = 0;
  146. block_group = block >> (sb->s_blocksize_bits + 3);
  147. bit = block % (sb->s_blocksize << 3);
  148. /*
  149. * Check to see if we are freeing blocks across a group boundary.
  150. */
  151. if (bit + count > (sb->s_blocksize << 3))
  152. {
  153. overflow = bit + count - (sb->s_blocksize << 3);
  154. count -= overflow;
  155. }
  156. bitmap_nr = load_block_bitmap(sb, bitmap, block_group);
  157. if (bitmap_nr < 0)
  158. goto error_return;
  159. bh = bitmap->s_block_bitmap[bitmap_nr];
  160. for (i=0; i < count; i++)
  161. {
  162. if (udf_set_bit(bit + i, bh->b_data))
  163. {
  164. udf_debug("bit %ld already set\n", bit + i);
  165. udf_debug("byte=%2x\n", ((char *)bh->b_data)[(bit + i) >> 3]);
  166. }
  167. else
  168. {
  169. if (inode)
  170. DQUOT_FREE_BLOCK(inode, 1);
  171. if (UDF_SB_LVIDBH(sb))
  172. {
  173. UDF_SB_LVID(sb)->freeSpaceTable[UDF_SB_PARTITION(sb)] =
  174. cpu_to_le32(le32_to_cpu(UDF_SB_LVID(sb)->freeSpaceTable[UDF_SB_PARTITION(sb)])+1);
  175. }
  176. }
  177. }
  178. mark_buffer_dirty(bh);
  179. if (overflow)
  180. {
  181. block += count;
  182. count = overflow;
  183. goto do_more;
  184. }
  185. error_return:
  186. sb->s_dirt = 1;
  187. if (UDF_SB_LVIDBH(sb))
  188. mark_buffer_dirty(UDF_SB_LVIDBH(sb));
  189. mutex_unlock(&sbi->s_alloc_mutex);
  190. return;
  191. }
  192. static int udf_bitmap_prealloc_blocks(struct super_block * sb,
  193. struct inode * inode,
  194. struct udf_bitmap *bitmap, uint16_t partition, uint32_t first_block,
  195. uint32_t block_count)
  196. {
  197. struct udf_sb_info *sbi = UDF_SB(sb);
  198. int alloc_count = 0;
  199. int bit, block, block_group, group_start;
  200. int nr_groups, bitmap_nr;
  201. struct buffer_head *bh;
  202. mutex_lock(&sbi->s_alloc_mutex);
  203. if (first_block < 0 || first_block >= UDF_SB_PARTLEN(sb, partition))
  204. goto out;
  205. if (first_block + block_count > UDF_SB_PARTLEN(sb, partition))
  206. block_count = UDF_SB_PARTLEN(sb, partition) - first_block;
  207. repeat:
  208. nr_groups = (UDF_SB_PARTLEN(sb, partition) +
  209. (sizeof(struct spaceBitmapDesc) << 3) + (sb->s_blocksize * 8) - 1) / (sb->s_blocksize * 8);
  210. block = first_block + (sizeof(struct spaceBitmapDesc) << 3);
  211. block_group = block >> (sb->s_blocksize_bits + 3);
  212. group_start = block_group ? 0 : sizeof(struct spaceBitmapDesc);
  213. bitmap_nr = load_block_bitmap(sb, bitmap, block_group);
  214. if (bitmap_nr < 0)
  215. goto out;
  216. bh = bitmap->s_block_bitmap[bitmap_nr];
  217. bit = block % (sb->s_blocksize << 3);
  218. while (bit < (sb->s_blocksize << 3) && block_count > 0)
  219. {
  220. if (!udf_test_bit(bit, bh->b_data))
  221. goto out;
  222. else if (DQUOT_PREALLOC_BLOCK(inode, 1))
  223. goto out;
  224. else if (!udf_clear_bit(bit, bh->b_data))
  225. {
  226. udf_debug("bit already cleared for block %d\n", bit);
  227. DQUOT_FREE_BLOCK(inode, 1);
  228. goto out;
  229. }
  230. block_count --;
  231. alloc_count ++;
  232. bit ++;
  233. block ++;
  234. }
  235. mark_buffer_dirty(bh);
  236. if (block_count > 0)
  237. goto repeat;
  238. out:
  239. if (UDF_SB_LVIDBH(sb))
  240. {
  241. UDF_SB_LVID(sb)->freeSpaceTable[partition] =
  242. cpu_to_le32(le32_to_cpu(UDF_SB_LVID(sb)->freeSpaceTable[partition])-alloc_count);
  243. mark_buffer_dirty(UDF_SB_LVIDBH(sb));
  244. }
  245. sb->s_dirt = 1;
  246. mutex_unlock(&sbi->s_alloc_mutex);
  247. return alloc_count;
  248. }
  249. static int udf_bitmap_new_block(struct super_block * sb,
  250. struct inode * inode,
  251. struct udf_bitmap *bitmap, uint16_t partition, uint32_t goal, int *err)
  252. {
  253. struct udf_sb_info *sbi = UDF_SB(sb);
  254. int newbit, bit=0, block, block_group, group_start;
  255. int end_goal, nr_groups, bitmap_nr, i;
  256. struct buffer_head *bh = NULL;
  257. char *ptr;
  258. int newblock = 0;
  259. *err = -ENOSPC;
  260. mutex_lock(&sbi->s_alloc_mutex);
  261. repeat:
  262. if (goal < 0 || goal >= UDF_SB_PARTLEN(sb, partition))
  263. goal = 0;
  264. nr_groups = bitmap->s_nr_groups;
  265. block = goal + (sizeof(struct spaceBitmapDesc) << 3);
  266. block_group = block >> (sb->s_blocksize_bits + 3);
  267. group_start = block_group ? 0 : sizeof(struct spaceBitmapDesc);
  268. bitmap_nr = load_block_bitmap(sb, bitmap, block_group);
  269. if (bitmap_nr < 0)
  270. goto error_return;
  271. bh = bitmap->s_block_bitmap[bitmap_nr];
  272. ptr = memscan((char *)bh->b_data + group_start, 0xFF, sb->s_blocksize - group_start);
  273. if ((ptr - ((char *)bh->b_data)) < sb->s_blocksize)
  274. {
  275. bit = block % (sb->s_blocksize << 3);
  276. if (udf_test_bit(bit, bh->b_data))
  277. {
  278. goto got_block;
  279. }
  280. end_goal = (bit + 63) & ~63;
  281. bit = udf_find_next_one_bit(bh->b_data, end_goal, bit);
  282. if (bit < end_goal)
  283. goto got_block;
  284. ptr = memscan((char *)bh->b_data + (bit >> 3), 0xFF, sb->s_blocksize - ((bit + 7) >> 3));
  285. newbit = (ptr - ((char *)bh->b_data)) << 3;
  286. if (newbit < sb->s_blocksize << 3)
  287. {
  288. bit = newbit;
  289. goto search_back;
  290. }
  291. newbit = udf_find_next_one_bit(bh->b_data, sb->s_blocksize << 3, bit);
  292. if (newbit < sb->s_blocksize << 3)
  293. {
  294. bit = newbit;
  295. goto got_block;
  296. }
  297. }
  298. for (i=0; i<(nr_groups*2); i++)
  299. {
  300. block_group ++;
  301. if (block_group >= nr_groups)
  302. block_group = 0;
  303. group_start = block_group ? 0 : sizeof(struct spaceBitmapDesc);
  304. bitmap_nr = load_block_bitmap(sb, bitmap, block_group);
  305. if (bitmap_nr < 0)
  306. goto error_return;
  307. bh = bitmap->s_block_bitmap[bitmap_nr];
  308. if (i < nr_groups)
  309. {
  310. ptr = memscan((char *)bh->b_data + group_start, 0xFF, sb->s_blocksize - group_start);
  311. if ((ptr - ((char *)bh->b_data)) < sb->s_blocksize)
  312. {
  313. bit = (ptr - ((char *)bh->b_data)) << 3;
  314. break;
  315. }
  316. }
  317. else
  318. {
  319. bit = udf_find_next_one_bit((char *)bh->b_data, sb->s_blocksize << 3, group_start << 3);
  320. if (bit < sb->s_blocksize << 3)
  321. break;
  322. }
  323. }
  324. if (i >= (nr_groups*2))
  325. {
  326. mutex_unlock(&sbi->s_alloc_mutex);
  327. return newblock;
  328. }
  329. if (bit < sb->s_blocksize << 3)
  330. goto search_back;
  331. else
  332. bit = udf_find_next_one_bit(bh->b_data, sb->s_blocksize << 3, group_start << 3);
  333. if (bit >= sb->s_blocksize << 3)
  334. {
  335. mutex_unlock(&sbi->s_alloc_mutex);
  336. return 0;
  337. }
  338. search_back:
  339. for (i=0; i<7 && bit > (group_start << 3) && udf_test_bit(bit - 1, bh->b_data); i++, bit--);
  340. got_block:
  341. /*
  342. * Check quota for allocation of this block.
  343. */
  344. if (inode && DQUOT_ALLOC_BLOCK(inode, 1))
  345. {
  346. mutex_unlock(&sbi->s_alloc_mutex);
  347. *err = -EDQUOT;
  348. return 0;
  349. }
  350. newblock = bit + (block_group << (sb->s_blocksize_bits + 3)) -
  351. (sizeof(struct spaceBitmapDesc) << 3);
  352. if (!udf_clear_bit(bit, bh->b_data))
  353. {
  354. udf_debug("bit already cleared for block %d\n", bit);
  355. goto repeat;
  356. }
  357. mark_buffer_dirty(bh);
  358. if (UDF_SB_LVIDBH(sb))
  359. {
  360. UDF_SB_LVID(sb)->freeSpaceTable[partition] =
  361. cpu_to_le32(le32_to_cpu(UDF_SB_LVID(sb)->freeSpaceTable[partition])-1);
  362. mark_buffer_dirty(UDF_SB_LVIDBH(sb));
  363. }
  364. sb->s_dirt = 1;
  365. mutex_unlock(&sbi->s_alloc_mutex);
  366. *err = 0;
  367. return newblock;
  368. error_return:
  369. *err = -EIO;
  370. mutex_unlock(&sbi->s_alloc_mutex);
  371. return 0;
  372. }
  373. static void udf_table_free_blocks(struct super_block * sb,
  374. struct inode * inode,
  375. struct inode * table,
  376. kernel_lb_addr bloc, uint32_t offset, uint32_t count)
  377. {
  378. struct udf_sb_info *sbi = UDF_SB(sb);
  379. uint32_t start, end;
  380. uint32_t nextoffset, oextoffset, elen;
  381. kernel_lb_addr nbloc, obloc, eloc;
  382. struct buffer_head *obh, *nbh;
  383. int8_t etype;
  384. int i;
  385. mutex_lock(&sbi->s_alloc_mutex);
  386. if (bloc.logicalBlockNum < 0 ||
  387. (bloc.logicalBlockNum + count) > UDF_SB_PARTLEN(sb, bloc.partitionReferenceNum))
  388. {
  389. udf_debug("%d < %d || %d + %d > %d\n",
  390. bloc.logicalBlockNum, 0, bloc.logicalBlockNum, count,
  391. UDF_SB_PARTLEN(sb, bloc.partitionReferenceNum));
  392. goto error_return;
  393. }
  394. /* We do this up front - There are some error conditions that could occure,
  395. but.. oh well */
  396. if (inode)
  397. DQUOT_FREE_BLOCK(inode, count);
  398. if (UDF_SB_LVIDBH(sb))
  399. {
  400. UDF_SB_LVID(sb)->freeSpaceTable[UDF_SB_PARTITION(sb)] =
  401. cpu_to_le32(le32_to_cpu(UDF_SB_LVID(sb)->freeSpaceTable[UDF_SB_PARTITION(sb)])+count);
  402. mark_buffer_dirty(UDF_SB_LVIDBH(sb));
  403. }
  404. start = bloc.logicalBlockNum + offset;
  405. end = bloc.logicalBlockNum + offset + count - 1;
  406. oextoffset = nextoffset = sizeof(struct unallocSpaceEntry);
  407. elen = 0;
  408. obloc = nbloc = UDF_I_LOCATION(table);
  409. obh = nbh = NULL;
  410. while (count && (etype =
  411. udf_next_aext(table, &nbloc, &nextoffset, &eloc, &elen, &nbh, 1)) != -1)
  412. {
  413. if (((eloc.logicalBlockNum + (elen >> sb->s_blocksize_bits)) ==
  414. start))
  415. {
  416. if ((0x3FFFFFFF - elen) < (count << sb->s_blocksize_bits))
  417. {
  418. count -= ((0x3FFFFFFF - elen) >> sb->s_blocksize_bits);
  419. start += ((0x3FFFFFFF - elen) >> sb->s_blocksize_bits);
  420. elen = (etype << 30) | (0x40000000 - sb->s_blocksize);
  421. }
  422. else
  423. {
  424. elen = (etype << 30) |
  425. (elen + (count << sb->s_blocksize_bits));
  426. start += count;
  427. count = 0;
  428. }
  429. udf_write_aext(table, obloc, &oextoffset, eloc, elen, obh, 1);
  430. }
  431. else if (eloc.logicalBlockNum == (end + 1))
  432. {
  433. if ((0x3FFFFFFF - elen) < (count << sb->s_blocksize_bits))
  434. {
  435. count -= ((0x3FFFFFFF - elen) >> sb->s_blocksize_bits);
  436. end -= ((0x3FFFFFFF - elen) >> sb->s_blocksize_bits);
  437. eloc.logicalBlockNum -=
  438. ((0x3FFFFFFF - elen) >> sb->s_blocksize_bits);
  439. elen = (etype << 30) | (0x40000000 - sb->s_blocksize);
  440. }
  441. else
  442. {
  443. eloc.logicalBlockNum = start;
  444. elen = (etype << 30) |
  445. (elen + (count << sb->s_blocksize_bits));
  446. end -= count;
  447. count = 0;
  448. }
  449. udf_write_aext(table, obloc, &oextoffset, eloc, elen, obh, 1);
  450. }
  451. if (nbh != obh)
  452. {
  453. i = -1;
  454. obloc = nbloc;
  455. udf_release_data(obh);
  456. atomic_inc(&nbh->b_count);
  457. obh = nbh;
  458. oextoffset = 0;
  459. }
  460. else
  461. oextoffset = nextoffset;
  462. }
  463. if (count)
  464. {
  465. /* NOTE: we CANNOT use udf_add_aext here, as it can try to allocate
  466. a new block, and since we hold the super block lock already
  467. very bad things would happen :)
  468. We copy the behavior of udf_add_aext, but instead of
  469. trying to allocate a new block close to the existing one,
  470. we just steal a block from the extent we are trying to add.
  471. It would be nice if the blocks were close together, but it
  472. isn't required.
  473. */
  474. int adsize;
  475. short_ad *sad = NULL;
  476. long_ad *lad = NULL;
  477. struct allocExtDesc *aed;
  478. eloc.logicalBlockNum = start;
  479. elen = EXT_RECORDED_ALLOCATED |
  480. (count << sb->s_blocksize_bits);
  481. if (UDF_I_ALLOCTYPE(table) == ICBTAG_FLAG_AD_SHORT)
  482. adsize = sizeof(short_ad);
  483. else if (UDF_I_ALLOCTYPE(table) == ICBTAG_FLAG_AD_LONG)
  484. adsize = sizeof(long_ad);
  485. else
  486. {
  487. udf_release_data(obh);
  488. udf_release_data(nbh);
  489. goto error_return;
  490. }
  491. if (nextoffset + (2 * adsize) > sb->s_blocksize)
  492. {
  493. char *sptr, *dptr;
  494. int loffset;
  495. udf_release_data(obh);
  496. obh = nbh;
  497. obloc = nbloc;
  498. oextoffset = nextoffset;
  499. /* Steal a block from the extent being free'd */
  500. nbloc.logicalBlockNum = eloc.logicalBlockNum;
  501. eloc.logicalBlockNum ++;
  502. elen -= sb->s_blocksize;
  503. if (!(nbh = udf_tread(sb,
  504. udf_get_lb_pblock(sb, nbloc, 0))))
  505. {
  506. udf_release_data(obh);
  507. goto error_return;
  508. }
  509. aed = (struct allocExtDesc *)(nbh->b_data);
  510. aed->previousAllocExtLocation = cpu_to_le32(obloc.logicalBlockNum);
  511. if (nextoffset + adsize > sb->s_blocksize)
  512. {
  513. loffset = nextoffset;
  514. aed->lengthAllocDescs = cpu_to_le32(adsize);
  515. sptr = UDF_I_DATA(inode) + nextoffset -
  516. udf_file_entry_alloc_offset(inode) +
  517. UDF_I_LENEATTR(inode) - adsize;
  518. dptr = nbh->b_data + sizeof(struct allocExtDesc);
  519. memcpy(dptr, sptr, adsize);
  520. nextoffset = sizeof(struct allocExtDesc) + adsize;
  521. }
  522. else
  523. {
  524. loffset = nextoffset + adsize;
  525. aed->lengthAllocDescs = cpu_to_le32(0);
  526. sptr = (obh)->b_data + nextoffset;
  527. nextoffset = sizeof(struct allocExtDesc);
  528. if (obh)
  529. {
  530. aed = (struct allocExtDesc *)(obh)->b_data;
  531. aed->lengthAllocDescs =
  532. cpu_to_le32(le32_to_cpu(aed->lengthAllocDescs) + adsize);
  533. }
  534. else
  535. {
  536. UDF_I_LENALLOC(table) += adsize;
  537. mark_inode_dirty(table);
  538. }
  539. }
  540. if (UDF_SB_UDFREV(sb) >= 0x0200)
  541. udf_new_tag(nbh->b_data, TAG_IDENT_AED, 3, 1,
  542. nbloc.logicalBlockNum, sizeof(tag));
  543. else
  544. udf_new_tag(nbh->b_data, TAG_IDENT_AED, 2, 1,
  545. nbloc.logicalBlockNum, sizeof(tag));
  546. switch (UDF_I_ALLOCTYPE(table))
  547. {
  548. case ICBTAG_FLAG_AD_SHORT:
  549. {
  550. sad = (short_ad *)sptr;
  551. sad->extLength = cpu_to_le32(
  552. EXT_NEXT_EXTENT_ALLOCDECS |
  553. sb->s_blocksize);
  554. sad->extPosition = cpu_to_le32(nbloc.logicalBlockNum);
  555. break;
  556. }
  557. case ICBTAG_FLAG_AD_LONG:
  558. {
  559. lad = (long_ad *)sptr;
  560. lad->extLength = cpu_to_le32(
  561. EXT_NEXT_EXTENT_ALLOCDECS |
  562. sb->s_blocksize);
  563. lad->extLocation = cpu_to_lelb(nbloc);
  564. break;
  565. }
  566. }
  567. if (obh)
  568. {
  569. udf_update_tag(obh->b_data, loffset);
  570. mark_buffer_dirty(obh);
  571. }
  572. else
  573. mark_inode_dirty(table);
  574. }
  575. if (elen) /* It's possible that stealing the block emptied the extent */
  576. {
  577. udf_write_aext(table, nbloc, &nextoffset, eloc, elen, nbh, 1);
  578. if (!nbh)
  579. {
  580. UDF_I_LENALLOC(table) += adsize;
  581. mark_inode_dirty(table);
  582. }
  583. else
  584. {
  585. aed = (struct allocExtDesc *)nbh->b_data;
  586. aed->lengthAllocDescs =
  587. cpu_to_le32(le32_to_cpu(aed->lengthAllocDescs) + adsize);
  588. udf_update_tag(nbh->b_data, nextoffset);
  589. mark_buffer_dirty(nbh);
  590. }
  591. }
  592. }
  593. udf_release_data(nbh);
  594. udf_release_data(obh);
  595. error_return:
  596. sb->s_dirt = 1;
  597. mutex_unlock(&sbi->s_alloc_mutex);
  598. return;
  599. }
  600. static int udf_table_prealloc_blocks(struct super_block * sb,
  601. struct inode * inode,
  602. struct inode *table, uint16_t partition, uint32_t first_block,
  603. uint32_t block_count)
  604. {
  605. struct udf_sb_info *sbi = UDF_SB(sb);
  606. int alloc_count = 0;
  607. uint32_t extoffset, elen, adsize;
  608. kernel_lb_addr bloc, eloc;
  609. struct buffer_head *bh;
  610. int8_t etype = -1;
  611. if (first_block < 0 || first_block >= UDF_SB_PARTLEN(sb, partition))
  612. return 0;
  613. if (UDF_I_ALLOCTYPE(table) == ICBTAG_FLAG_AD_SHORT)
  614. adsize = sizeof(short_ad);
  615. else if (UDF_I_ALLOCTYPE(table) == ICBTAG_FLAG_AD_LONG)
  616. adsize = sizeof(long_ad);
  617. else
  618. return 0;
  619. mutex_lock(&sbi->s_alloc_mutex);
  620. extoffset = sizeof(struct unallocSpaceEntry);
  621. bloc = UDF_I_LOCATION(table);
  622. bh = NULL;
  623. eloc.logicalBlockNum = 0xFFFFFFFF;
  624. while (first_block != eloc.logicalBlockNum && (etype =
  625. udf_next_aext(table, &bloc, &extoffset, &eloc, &elen, &bh, 1)) != -1)
  626. {
  627. udf_debug("eloc=%d, elen=%d, first_block=%d\n",
  628. eloc.logicalBlockNum, elen, first_block);
  629. ; /* empty loop body */
  630. }
  631. if (first_block == eloc.logicalBlockNum)
  632. {
  633. extoffset -= adsize;
  634. alloc_count = (elen >> sb->s_blocksize_bits);
  635. if (inode && DQUOT_PREALLOC_BLOCK(inode, alloc_count > block_count ? block_count : alloc_count))
  636. alloc_count = 0;
  637. else if (alloc_count > block_count)
  638. {
  639. alloc_count = block_count;
  640. eloc.logicalBlockNum += alloc_count;
  641. elen -= (alloc_count << sb->s_blocksize_bits);
  642. udf_write_aext(table, bloc, &extoffset, eloc, (etype << 30) | elen, bh, 1);
  643. }
  644. else
  645. udf_delete_aext(table, bloc, extoffset, eloc, (etype << 30) | elen, bh);
  646. }
  647. else
  648. alloc_count = 0;
  649. udf_release_data(bh);
  650. if (alloc_count && UDF_SB_LVIDBH(sb))
  651. {
  652. UDF_SB_LVID(sb)->freeSpaceTable[partition] =
  653. cpu_to_le32(le32_to_cpu(UDF_SB_LVID(sb)->freeSpaceTable[partition])-alloc_count);
  654. mark_buffer_dirty(UDF_SB_LVIDBH(sb));
  655. sb->s_dirt = 1;
  656. }
  657. mutex_unlock(&sbi->s_alloc_mutex);
  658. return alloc_count;
  659. }
  660. static int udf_table_new_block(struct super_block * sb,
  661. struct inode * inode,
  662. struct inode *table, uint16_t partition, uint32_t goal, int *err)
  663. {
  664. struct udf_sb_info *sbi = UDF_SB(sb);
  665. uint32_t spread = 0xFFFFFFFF, nspread = 0xFFFFFFFF;
  666. uint32_t newblock = 0, adsize;
  667. uint32_t extoffset, goal_extoffset, elen, goal_elen = 0;
  668. kernel_lb_addr bloc, goal_bloc, eloc, goal_eloc;
  669. struct buffer_head *bh, *goal_bh;
  670. int8_t etype;
  671. *err = -ENOSPC;
  672. if (UDF_I_ALLOCTYPE(table) == ICBTAG_FLAG_AD_SHORT)
  673. adsize = sizeof(short_ad);
  674. else if (UDF_I_ALLOCTYPE(table) == ICBTAG_FLAG_AD_LONG)
  675. adsize = sizeof(long_ad);
  676. else
  677. return newblock;
  678. mutex_lock(&sbi->s_alloc_mutex);
  679. if (goal < 0 || goal >= UDF_SB_PARTLEN(sb, partition))
  680. goal = 0;
  681. /* We search for the closest matching block to goal. If we find a exact hit,
  682. we stop. Otherwise we keep going till we run out of extents.
  683. We store the buffer_head, bloc, and extoffset of the current closest
  684. match and use that when we are done.
  685. */
  686. extoffset = sizeof(struct unallocSpaceEntry);
  687. bloc = UDF_I_LOCATION(table);
  688. goal_bh = bh = NULL;
  689. while (spread && (etype =
  690. udf_next_aext(table, &bloc, &extoffset, &eloc, &elen, &bh, 1)) != -1)
  691. {
  692. if (goal >= eloc.logicalBlockNum)
  693. {
  694. if (goal < eloc.logicalBlockNum + (elen >> sb->s_blocksize_bits))
  695. nspread = 0;
  696. else
  697. nspread = goal - eloc.logicalBlockNum -
  698. (elen >> sb->s_blocksize_bits);
  699. }
  700. else
  701. nspread = eloc.logicalBlockNum - goal;
  702. if (nspread < spread)
  703. {
  704. spread = nspread;
  705. if (goal_bh != bh)
  706. {
  707. udf_release_data(goal_bh);
  708. goal_bh = bh;
  709. atomic_inc(&goal_bh->b_count);
  710. }
  711. goal_bloc = bloc;
  712. goal_extoffset = extoffset - adsize;
  713. goal_eloc = eloc;
  714. goal_elen = (etype << 30) | elen;
  715. }
  716. }
  717. udf_release_data(bh);
  718. if (spread == 0xFFFFFFFF)
  719. {
  720. udf_release_data(goal_bh);
  721. mutex_unlock(&sbi->s_alloc_mutex);
  722. return 0;
  723. }
  724. /* Only allocate blocks from the beginning of the extent.
  725. That way, we only delete (empty) extents, never have to insert an
  726. extent because of splitting */
  727. /* This works, but very poorly.... */
  728. newblock = goal_eloc.logicalBlockNum;
  729. goal_eloc.logicalBlockNum ++;
  730. goal_elen -= sb->s_blocksize;
  731. if (inode && DQUOT_ALLOC_BLOCK(inode, 1))
  732. {
  733. udf_release_data(goal_bh);
  734. mutex_unlock(&sbi->s_alloc_mutex);
  735. *err = -EDQUOT;
  736. return 0;
  737. }
  738. if (goal_elen)
  739. udf_write_aext(table, goal_bloc, &goal_extoffset, goal_eloc, goal_elen, goal_bh, 1);
  740. else
  741. udf_delete_aext(table, goal_bloc, goal_extoffset, goal_eloc, goal_elen, goal_bh);
  742. udf_release_data(goal_bh);
  743. if (UDF_SB_LVIDBH(sb))
  744. {
  745. UDF_SB_LVID(sb)->freeSpaceTable[partition] =
  746. cpu_to_le32(le32_to_cpu(UDF_SB_LVID(sb)->freeSpaceTable[partition])-1);
  747. mark_buffer_dirty(UDF_SB_LVIDBH(sb));
  748. }
  749. sb->s_dirt = 1;
  750. mutex_unlock(&sbi->s_alloc_mutex);
  751. *err = 0;
  752. return newblock;
  753. }
  754. inline void udf_free_blocks(struct super_block * sb,
  755. struct inode * inode,
  756. kernel_lb_addr bloc, uint32_t offset, uint32_t count)
  757. {
  758. uint16_t partition = bloc.partitionReferenceNum;
  759. if (UDF_SB_PARTFLAGS(sb, partition) & UDF_PART_FLAG_UNALLOC_BITMAP)
  760. {
  761. return udf_bitmap_free_blocks(sb, inode,
  762. UDF_SB_PARTMAPS(sb)[partition].s_uspace.s_bitmap,
  763. bloc, offset, count);
  764. }
  765. else if (UDF_SB_PARTFLAGS(sb, partition) & UDF_PART_FLAG_UNALLOC_TABLE)
  766. {
  767. return udf_table_free_blocks(sb, inode,
  768. UDF_SB_PARTMAPS(sb)[partition].s_uspace.s_table,
  769. bloc, offset, count);
  770. }
  771. else if (UDF_SB_PARTFLAGS(sb, partition) & UDF_PART_FLAG_FREED_BITMAP)
  772. {
  773. return udf_bitmap_free_blocks(sb, inode,
  774. UDF_SB_PARTMAPS(sb)[partition].s_fspace.s_bitmap,
  775. bloc, offset, count);
  776. }
  777. else if (UDF_SB_PARTFLAGS(sb, partition) & UDF_PART_FLAG_FREED_TABLE)
  778. {
  779. return udf_table_free_blocks(sb, inode,
  780. UDF_SB_PARTMAPS(sb)[partition].s_fspace.s_table,
  781. bloc, offset, count);
  782. }
  783. else
  784. return;
  785. }
  786. inline int udf_prealloc_blocks(struct super_block * sb,
  787. struct inode * inode,
  788. uint16_t partition, uint32_t first_block, uint32_t block_count)
  789. {
  790. if (UDF_SB_PARTFLAGS(sb, partition) & UDF_PART_FLAG_UNALLOC_BITMAP)
  791. {
  792. return udf_bitmap_prealloc_blocks(sb, inode,
  793. UDF_SB_PARTMAPS(sb)[partition].s_uspace.s_bitmap,
  794. partition, first_block, block_count);
  795. }
  796. else if (UDF_SB_PARTFLAGS(sb, partition) & UDF_PART_FLAG_UNALLOC_TABLE)
  797. {
  798. return udf_table_prealloc_blocks(sb, inode,
  799. UDF_SB_PARTMAPS(sb)[partition].s_uspace.s_table,
  800. partition, first_block, block_count);
  801. }
  802. else if (UDF_SB_PARTFLAGS(sb, partition) & UDF_PART_FLAG_FREED_BITMAP)
  803. {
  804. return udf_bitmap_prealloc_blocks(sb, inode,
  805. UDF_SB_PARTMAPS(sb)[partition].s_fspace.s_bitmap,
  806. partition, first_block, block_count);
  807. }
  808. else if (UDF_SB_PARTFLAGS(sb, partition) & UDF_PART_FLAG_FREED_TABLE)
  809. {
  810. return udf_table_prealloc_blocks(sb, inode,
  811. UDF_SB_PARTMAPS(sb)[partition].s_fspace.s_table,
  812. partition, first_block, block_count);
  813. }
  814. else
  815. return 0;
  816. }
  817. inline int udf_new_block(struct super_block * sb,
  818. struct inode * inode,
  819. uint16_t partition, uint32_t goal, int *err)
  820. {
  821. if (UDF_SB_PARTFLAGS(sb, partition) & UDF_PART_FLAG_UNALLOC_BITMAP)
  822. {
  823. return udf_bitmap_new_block(sb, inode,
  824. UDF_SB_PARTMAPS(sb)[partition].s_uspace.s_bitmap,
  825. partition, goal, err);
  826. }
  827. else if (UDF_SB_PARTFLAGS(sb, partition) & UDF_PART_FLAG_UNALLOC_TABLE)
  828. {
  829. return udf_table_new_block(sb, inode,
  830. UDF_SB_PARTMAPS(sb)[partition].s_uspace.s_table,
  831. partition, goal, err);
  832. }
  833. else if (UDF_SB_PARTFLAGS(sb, partition) & UDF_PART_FLAG_FREED_BITMAP)
  834. {
  835. return udf_bitmap_new_block(sb, inode,
  836. UDF_SB_PARTMAPS(sb)[partition].s_fspace.s_bitmap,
  837. partition, goal, err);
  838. }
  839. else if (UDF_SB_PARTFLAGS(sb, partition) & UDF_PART_FLAG_FREED_TABLE)
  840. {
  841. return udf_table_new_block(sb, inode,
  842. UDF_SB_PARTMAPS(sb)[partition].s_fspace.s_table,
  843. partition, goal, err);
  844. }
  845. else
  846. {
  847. *err = -EIO;
  848. return 0;
  849. }
  850. }