alloc.c 10 KB

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