开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > Linux/Unix编程 > 查看源码
alloc.c
资源名称：linux-2.4.20.tar.gz　[点击查看]
上传用户：jlfgdled
上传日期：2013-04-10
资源大小：33168k
文件大小：10k
源码类别：

Linux/Unix编程

开发平台：

Unix_Linux

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