alloc.c 11 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456
  1. /*
  2. * linux/fs/hpfs/alloc.c
  3. *
  4. * Mikulas Patocka (mikulas@artax.karlin.mff.cuni.cz), 1998-1999
  5. *
  6. * HPFS bitmap operations
  7. */
  8. #include "hpfs_fn.h"
  9. static int hpfs_alloc_if_possible_nolock(struct super_block *s, secno sec);
  10. /*
  11. * Check if a sector is allocated in bitmap
  12. * This is really slow. Turned on only if chk==2
  13. */
  14. static int chk_if_allocated(struct super_block *s, secno sec, char *msg)
  15. {
  16. struct quad_buffer_head qbh;
  17. unsigned *bmp;
  18. if (!(bmp = hpfs_map_bitmap(s, sec >> 14, &qbh, "chk"))) goto fail;
  19. if ((bmp[(sec & 0x3fff) >> 5] >> (sec & 0x1f)) & 1) {
  20. hpfs_error(s, "sector '%s' - %08x not allocated in bitmap", msg, sec);
  21. goto fail1;
  22. }
  23. hpfs_brelse4(&qbh);
  24. if (sec >= hpfs_sb(s)->sb_dirband_start && sec < hpfs_sb(s)->sb_dirband_start + hpfs_sb(s)->sb_dirband_size) {
  25. unsigned ssec = (sec - hpfs_sb(s)->sb_dirband_start) / 4;
  26. if (!(bmp = hpfs_map_dnode_bitmap(s, &qbh))) goto fail;
  27. if ((bmp[ssec >> 5] >> (ssec & 0x1f)) & 1) {
  28. hpfs_error(s, "sector '%s' - %08x not allocated in directory bitmap", msg, sec);
  29. goto fail1;
  30. }
  31. hpfs_brelse4(&qbh);
  32. }
  33. return 0;
  34. fail1:
  35. hpfs_brelse4(&qbh);
  36. fail:
  37. return 1;
  38. }
  39. /*
  40. * Check if sector(s) have proper number and additionally check if they're
  41. * allocated in bitmap.
  42. */
  43. int hpfs_chk_sectors(struct super_block *s, secno start, int len, char *msg)
  44. {
  45. if (start + len < start || start < 0x12 ||
  46. start + len > hpfs_sb(s)->sb_fs_size) {
  47. hpfs_error(s, "sector(s) '%s' badly placed at %08x", msg, start);
  48. return 1;
  49. }
  50. if (hpfs_sb(s)->sb_chk>=2) {
  51. int i;
  52. for (i = 0; i < len; i++)
  53. if (chk_if_allocated(s, start + i, msg)) return 1;
  54. }
  55. return 0;
  56. }
  57. static secno alloc_in_bmp(struct super_block *s, secno near, unsigned n, unsigned forward)
  58. {
  59. struct quad_buffer_head qbh;
  60. unsigned *bmp;
  61. unsigned bs = near & ~0x3fff;
  62. unsigned nr = (near & 0x3fff) & ~(n - 1);
  63. /*unsigned mnr;*/
  64. unsigned i, q;
  65. int a, b;
  66. secno ret = 0;
  67. if (n != 1 && n != 4) {
  68. hpfs_error(s, "Bad allocation size: %d", n);
  69. return 0;
  70. }
  71. lock_super(s);
  72. if (bs != ~0x3fff) {
  73. if (!(bmp = hpfs_map_bitmap(s, near >> 14, &qbh, "aib"))) goto uls;
  74. } else {
  75. if (!(bmp = hpfs_map_dnode_bitmap(s, &qbh))) goto uls;
  76. }
  77. if (!tstbits(bmp, nr, n + forward)) {
  78. ret = bs + nr;
  79. goto rt;
  80. }
  81. /*if (!tstbits(bmp, nr + n, n + forward)) {
  82. ret = bs + nr + n;
  83. goto rt;
  84. }*/
  85. q = nr + n; b = 0;
  86. while ((a = tstbits(bmp, q, n + forward)) != 0) {
  87. q += a;
  88. if (n != 1) q = ((q-1)&~(n-1))+n;
  89. if (!b) {
  90. if (q>>5 != nr>>5) {
  91. b = 1;
  92. q = nr & 0x1f;
  93. }
  94. } else if (q > nr) break;
  95. }
  96. if (!a) {
  97. ret = bs + q;
  98. goto rt;
  99. }
  100. nr >>= 5;
  101. /*for (i = nr + 1; i != nr; i++, i &= 0x1ff) {*/
  102. i = nr;
  103. do {
  104. if (!bmp[i]) goto cont;
  105. if (n + forward >= 0x3f && bmp[i] != -1) goto cont;
  106. q = i<<5;
  107. if (i > 0) {
  108. unsigned k = bmp[i-1];
  109. while (k & 0x80000000) {
  110. q--; k <<= 1;
  111. }
  112. }
  113. if (n != 1) q = ((q-1)&~(n-1))+n;
  114. while ((a = tstbits(bmp, q, n + forward)) != 0) {
  115. q += a;
  116. if (n != 1) q = ((q-1)&~(n-1))+n;
  117. if (q>>5 > i) break;
  118. }
  119. if (!a) {
  120. ret = bs + q;
  121. goto rt;
  122. }
  123. cont:
  124. i++, i &= 0x1ff;
  125. } while (i != nr);
  126. rt:
  127. if (ret) {
  128. if (hpfs_sb(s)->sb_chk && ((ret >> 14) != (bs >> 14) || (bmp[(ret & 0x3fff) >> 5] | ~(((1 << n) - 1) << (ret & 0x1f))) != 0xffffffff)) {
  129. hpfs_error(s, "Allocation doesn't work! Wanted %d, allocated at %08x", n, ret);
  130. ret = 0;
  131. goto b;
  132. }
  133. bmp[(ret & 0x3fff) >> 5] &= ~(((1 << n) - 1) << (ret & 0x1f));
  134. hpfs_mark_4buffers_dirty(&qbh);
  135. }
  136. b:
  137. hpfs_brelse4(&qbh);
  138. uls:
  139. unlock_super(s);
  140. return ret;
  141. }
  142. /*
  143. * Allocation strategy: 1) search place near the sector specified
  144. * 2) search bitmap where free sectors last found
  145. * 3) search all bitmaps
  146. * 4) search all bitmaps ignoring number of pre-allocated
  147. * sectors
  148. */
  149. secno hpfs_alloc_sector(struct super_block *s, secno near, unsigned n, int forward, int lock)
  150. {
  151. secno sec;
  152. int i;
  153. unsigned n_bmps;
  154. struct hpfs_sb_info *sbi = hpfs_sb(s);
  155. int f_p = 0;
  156. int near_bmp;
  157. if (forward < 0) {
  158. forward = -forward;
  159. f_p = 1;
  160. }
  161. if (lock) hpfs_lock_creation(s);
  162. n_bmps = (sbi->sb_fs_size + 0x4000 - 1) >> 14;
  163. if (near && near < sbi->sb_fs_size) {
  164. if ((sec = alloc_in_bmp(s, near, n, f_p ? forward : forward/4))) goto ret;
  165. near_bmp = near >> 14;
  166. } else near_bmp = n_bmps / 2;
  167. /*
  168. if (b != -1) {
  169. if ((sec = alloc_in_bmp(s, b<<14, n, f_p ? forward : forward/2))) {
  170. b &= 0x0fffffff;
  171. goto ret;
  172. }
  173. if (b > 0x10000000) if ((sec = alloc_in_bmp(s, (b&0xfffffff)<<14, n, f_p ? forward : 0))) goto ret;
  174. */
  175. if (!f_p) if (forward > sbi->sb_max_fwd_alloc) forward = sbi->sb_max_fwd_alloc;
  176. less_fwd:
  177. for (i = 0; i < n_bmps; i++) {
  178. if (near_bmp+i < n_bmps && ((sec = alloc_in_bmp(s, (near_bmp+i) << 14, n, forward)))) {
  179. sbi->sb_c_bitmap = near_bmp+i;
  180. goto ret;
  181. }
  182. if (!forward) {
  183. if (near_bmp-i-1 >= 0 && ((sec = alloc_in_bmp(s, (near_bmp-i-1) << 14, n, forward)))) {
  184. sbi->sb_c_bitmap = near_bmp-i-1;
  185. goto ret;
  186. }
  187. } else {
  188. if (near_bmp+i >= n_bmps && ((sec = alloc_in_bmp(s, (near_bmp+i-n_bmps) << 14, n, forward)))) {
  189. sbi->sb_c_bitmap = near_bmp+i-n_bmps;
  190. goto ret;
  191. }
  192. }
  193. if (i == 1 && sbi->sb_c_bitmap != -1 && ((sec = alloc_in_bmp(s, (sbi->sb_c_bitmap) << 14, n, forward)))) {
  194. goto ret;
  195. }
  196. }
  197. if (!f_p) {
  198. if (forward) {
  199. sbi->sb_max_fwd_alloc = forward * 3 / 4;
  200. forward /= 2;
  201. goto less_fwd;
  202. }
  203. }
  204. sec = 0;
  205. ret:
  206. if (sec && f_p) {
  207. for (i = 0; i < forward; i++) {
  208. if (!hpfs_alloc_if_possible_nolock(s, sec + i + 1)) {
  209. hpfs_error(s, "Prealloc doesn't work! Wanted %d, allocated at %08x, can't allocate %d", forward, sec, i);
  210. sec = 0;
  211. break;
  212. }
  213. }
  214. }
  215. if (lock) hpfs_unlock_creation(s);
  216. return sec;
  217. }
  218. static secno alloc_in_dirband(struct super_block *s, secno near, int lock)
  219. {
  220. unsigned nr = near;
  221. secno sec;
  222. struct hpfs_sb_info *sbi = hpfs_sb(s);
  223. if (nr < sbi->sb_dirband_start)
  224. nr = sbi->sb_dirband_start;
  225. if (nr >= sbi->sb_dirband_start + sbi->sb_dirband_size)
  226. nr = sbi->sb_dirband_start + sbi->sb_dirband_size - 4;
  227. nr -= sbi->sb_dirband_start;
  228. nr >>= 2;
  229. if (lock) hpfs_lock_creation(s);
  230. sec = alloc_in_bmp(s, (~0x3fff) | nr, 1, 0);
  231. if (lock) hpfs_unlock_creation(s);
  232. if (!sec) return 0;
  233. return ((sec & 0x3fff) << 2) + sbi->sb_dirband_start;
  234. }
  235. /* Alloc sector if it's free */
  236. static int hpfs_alloc_if_possible_nolock(struct super_block *s, secno sec)
  237. {
  238. struct quad_buffer_head qbh;
  239. unsigned *bmp;
  240. lock_super(s);
  241. if (!(bmp = hpfs_map_bitmap(s, sec >> 14, &qbh, "aip"))) goto end;
  242. if (bmp[(sec & 0x3fff) >> 5] & (1 << (sec & 0x1f))) {
  243. bmp[(sec & 0x3fff) >> 5] &= ~(1 << (sec & 0x1f));
  244. hpfs_mark_4buffers_dirty(&qbh);
  245. hpfs_brelse4(&qbh);
  246. unlock_super(s);
  247. return 1;
  248. }
  249. hpfs_brelse4(&qbh);
  250. end:
  251. unlock_super(s);
  252. return 0;
  253. }
  254. int hpfs_alloc_if_possible(struct super_block *s, secno sec)
  255. {
  256. int r;
  257. hpfs_lock_creation(s);
  258. r = hpfs_alloc_if_possible_nolock(s, sec);
  259. hpfs_unlock_creation(s);
  260. return r;
  261. }
  262. /* Free sectors in bitmaps */
  263. void hpfs_free_sectors(struct super_block *s, secno sec, unsigned n)
  264. {
  265. struct quad_buffer_head qbh;
  266. unsigned *bmp;
  267. struct hpfs_sb_info *sbi = hpfs_sb(s);
  268. /*printk("2 - ");*/
  269. if (!n) return;
  270. if (sec < 0x12) {
  271. hpfs_error(s, "Trying to free reserved sector %08x", sec);
  272. return;
  273. }
  274. lock_super(s);
  275. sbi->sb_max_fwd_alloc += n > 0xffff ? 0xffff : n;
  276. if (sbi->sb_max_fwd_alloc > 0xffffff) sbi->sb_max_fwd_alloc = 0xffffff;
  277. new_map:
  278. if (!(bmp = hpfs_map_bitmap(s, sec >> 14, &qbh, "free"))) {
  279. unlock_super(s);
  280. return;
  281. }
  282. new_tst:
  283. if ((bmp[(sec & 0x3fff) >> 5] >> (sec & 0x1f) & 1)) {
  284. hpfs_error(s, "sector %08x not allocated", sec);
  285. hpfs_brelse4(&qbh);
  286. unlock_super(s);
  287. return;
  288. }
  289. bmp[(sec & 0x3fff) >> 5] |= 1 << (sec & 0x1f);
  290. if (!--n) {
  291. hpfs_mark_4buffers_dirty(&qbh);
  292. hpfs_brelse4(&qbh);
  293. unlock_super(s);
  294. return;
  295. }
  296. if (!(++sec & 0x3fff)) {
  297. hpfs_mark_4buffers_dirty(&qbh);
  298. hpfs_brelse4(&qbh);
  299. goto new_map;
  300. }
  301. goto new_tst;
  302. }
  303. /*
  304. * Check if there are at least n free dnodes on the filesystem.
  305. * Called before adding to dnode. If we run out of space while
  306. * splitting dnodes, it would corrupt dnode tree.
  307. */
  308. int hpfs_check_free_dnodes(struct super_block *s, int n)
  309. {
  310. int n_bmps = (hpfs_sb(s)->sb_fs_size + 0x4000 - 1) >> 14;
  311. int b = hpfs_sb(s)->sb_c_bitmap & 0x0fffffff;
  312. int i, j;
  313. unsigned *bmp;
  314. struct quad_buffer_head qbh;
  315. if ((bmp = hpfs_map_dnode_bitmap(s, &qbh))) {
  316. for (j = 0; j < 512; j++) {
  317. unsigned k;
  318. if (!bmp[j]) continue;
  319. for (k = bmp[j]; k; k >>= 1) if (k & 1) if (!--n) {
  320. hpfs_brelse4(&qbh);
  321. return 0;
  322. }
  323. }
  324. }
  325. hpfs_brelse4(&qbh);
  326. i = 0;
  327. if (hpfs_sb(s)->sb_c_bitmap != -1) {
  328. bmp = hpfs_map_bitmap(s, b, &qbh, "chkdn1");
  329. goto chk_bmp;
  330. }
  331. chk_next:
  332. if (i == b) i++;
  333. if (i >= n_bmps) return 1;
  334. bmp = hpfs_map_bitmap(s, i, &qbh, "chkdn2");
  335. chk_bmp:
  336. if (bmp) {
  337. for (j = 0; j < 512; j++) {
  338. unsigned k;
  339. if (!bmp[j]) continue;
  340. for (k = 0xf; k; k <<= 4)
  341. if ((bmp[j] & k) == k) {
  342. if (!--n) {
  343. hpfs_brelse4(&qbh);
  344. return 0;
  345. }
  346. }
  347. }
  348. hpfs_brelse4(&qbh);
  349. }
  350. i++;
  351. goto chk_next;
  352. }
  353. void hpfs_free_dnode(struct super_block *s, dnode_secno dno)
  354. {
  355. if (hpfs_sb(s)->sb_chk) if (dno & 3) {
  356. hpfs_error(s, "hpfs_free_dnode: dnode %08x not aligned", dno);
  357. return;
  358. }
  359. if (dno < hpfs_sb(s)->sb_dirband_start ||
  360. dno >= hpfs_sb(s)->sb_dirband_start + hpfs_sb(s)->sb_dirband_size) {
  361. hpfs_free_sectors(s, dno, 4);
  362. } else {
  363. struct quad_buffer_head qbh;
  364. unsigned *bmp;
  365. unsigned ssec = (dno - hpfs_sb(s)->sb_dirband_start) / 4;
  366. lock_super(s);
  367. if (!(bmp = hpfs_map_dnode_bitmap(s, &qbh))) {
  368. unlock_super(s);
  369. return;
  370. }
  371. bmp[ssec >> 5] |= 1 << (ssec & 0x1f);
  372. hpfs_mark_4buffers_dirty(&qbh);
  373. hpfs_brelse4(&qbh);
  374. unlock_super(s);
  375. }
  376. }
  377. struct dnode *hpfs_alloc_dnode(struct super_block *s, secno near,
  378. dnode_secno *dno, struct quad_buffer_head *qbh,
  379. int lock)
  380. {
  381. struct dnode *d;
  382. if (hpfs_count_one_bitmap(s, hpfs_sb(s)->sb_dmap) > FREE_DNODES_ADD) {
  383. if (!(*dno = alloc_in_dirband(s, near, lock)))
  384. if (!(*dno = hpfs_alloc_sector(s, near, 4, 0, lock))) return NULL;
  385. } else {
  386. if (!(*dno = hpfs_alloc_sector(s, near, 4, 0, lock)))
  387. if (!(*dno = alloc_in_dirband(s, near, lock))) return NULL;
  388. }
  389. if (!(d = hpfs_get_4sectors(s, *dno, qbh))) {
  390. hpfs_free_dnode(s, *dno);
  391. return NULL;
  392. }
  393. memset(d, 0, 2048);
  394. d->magic = DNODE_MAGIC;
  395. d->first_free = 52;
  396. d->dirent[0] = 32;
  397. d->dirent[2] = 8;
  398. d->dirent[30] = 1;
  399. d->dirent[31] = 255;
  400. d->self = *dno;
  401. return d;
  402. }
  403. struct fnode *hpfs_alloc_fnode(struct super_block *s, secno near, fnode_secno *fno,
  404. struct buffer_head **bh)
  405. {
  406. struct fnode *f;
  407. if (!(*fno = hpfs_alloc_sector(s, near, 1, FNODE_ALLOC_FWD, 1))) return NULL;
  408. if (!(f = hpfs_get_sector(s, *fno, bh))) {
  409. hpfs_free_sectors(s, *fno, 1);
  410. return NULL;
  411. }
  412. memset(f, 0, 512);
  413. f->magic = FNODE_MAGIC;
  414. f->ea_offs = 0xc4;
  415. f->btree.n_free_nodes = 8;
  416. f->btree.first_free = 8;
  417. return f;
  418. }
  419. struct anode *hpfs_alloc_anode(struct super_block *s, secno near, anode_secno *ano,
  420. struct buffer_head **bh)
  421. {
  422. struct anode *a;
  423. if (!(*ano = hpfs_alloc_sector(s, near, 1, ANODE_ALLOC_FWD, 1))) return NULL;
  424. if (!(a = hpfs_get_sector(s, *ano, bh))) {
  425. hpfs_free_sectors(s, *ano, 1);
  426. return NULL;
  427. }
  428. memset(a, 0, 512);
  429. a->magic = ANODE_MAGIC;
  430. a->self = *ano;
  431. a->btree.n_free_nodes = 40;
  432. a->btree.n_used_nodes = 0;
  433. a->btree.first_free = 8;
  434. return a;
  435. }