do_balan.c 54 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768176917701771177217731774177517761777177817791780178117821783178417851786178717881789179017911792179317941795179617971798179918001801180218031804180518061807180818091810181118121813181418151816181718181819182018211822182318241825182618271828182918301831183218331834183518361837183818391840184118421843184418451846184718481849185018511852185318541855185618571858185918601861186218631864186518661867186818691870187118721873187418751876187718781879188018811882188318841885188618871888188918901891189218931894189518961897189818991900
  1. /*
  2. * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README
  3. */
  4. /*
  5. * Now we have all buffers that must be used in balancing of the tree
  6. * Further calculations can not cause schedule(), and thus the buffer
  7. * tree will be stable until the balancing will be finished
  8. * balance the tree according to the analysis made before,
  9. * and using buffers obtained after all above.
  10. */
  11. #include <linux/uaccess.h>
  12. #include <linux/time.h>
  13. #include "reiserfs.h"
  14. #include <linux/buffer_head.h>
  15. #include <linux/kernel.h>
  16. static inline void buffer_info_init_left(struct tree_balance *tb,
  17. struct buffer_info *bi)
  18. {
  19. bi->tb = tb;
  20. bi->bi_bh = tb->L[0];
  21. bi->bi_parent = tb->FL[0];
  22. bi->bi_position = get_left_neighbor_position(tb, 0);
  23. }
  24. static inline void buffer_info_init_right(struct tree_balance *tb,
  25. struct buffer_info *bi)
  26. {
  27. bi->tb = tb;
  28. bi->bi_bh = tb->R[0];
  29. bi->bi_parent = tb->FR[0];
  30. bi->bi_position = get_right_neighbor_position(tb, 0);
  31. }
  32. static inline void buffer_info_init_tbS0(struct tree_balance *tb,
  33. struct buffer_info *bi)
  34. {
  35. bi->tb = tb;
  36. bi->bi_bh = PATH_PLAST_BUFFER(tb->tb_path);
  37. bi->bi_parent = PATH_H_PPARENT(tb->tb_path, 0);
  38. bi->bi_position = PATH_H_POSITION(tb->tb_path, 1);
  39. }
  40. static inline void buffer_info_init_bh(struct tree_balance *tb,
  41. struct buffer_info *bi,
  42. struct buffer_head *bh)
  43. {
  44. bi->tb = tb;
  45. bi->bi_bh = bh;
  46. bi->bi_parent = NULL;
  47. bi->bi_position = 0;
  48. }
  49. inline void do_balance_mark_leaf_dirty(struct tree_balance *tb,
  50. struct buffer_head *bh, int flag)
  51. {
  52. journal_mark_dirty(tb->transaction_handle, bh);
  53. }
  54. #define do_balance_mark_internal_dirty do_balance_mark_leaf_dirty
  55. #define do_balance_mark_sb_dirty do_balance_mark_leaf_dirty
  56. /*
  57. * summary:
  58. * if deleting something ( tb->insert_size[0] < 0 )
  59. * return(balance_leaf_when_delete()); (flag d handled here)
  60. * else
  61. * if lnum is larger than 0 we put items into the left node
  62. * if rnum is larger than 0 we put items into the right node
  63. * if snum1 is larger than 0 we put items into the new node s1
  64. * if snum2 is larger than 0 we put items into the new node s2
  65. * Note that all *num* count new items being created.
  66. */
  67. static void balance_leaf_when_delete_del(struct tree_balance *tb)
  68. {
  69. struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
  70. int item_pos = PATH_LAST_POSITION(tb->tb_path);
  71. struct buffer_info bi;
  72. #ifdef CONFIG_REISERFS_CHECK
  73. struct item_head *ih = item_head(tbS0, item_pos);
  74. #endif
  75. RFALSE(ih_item_len(ih) + IH_SIZE != -tb->insert_size[0],
  76. "vs-12013: mode Delete, insert size %d, ih to be deleted %h",
  77. -tb->insert_size[0], ih);
  78. buffer_info_init_tbS0(tb, &bi);
  79. leaf_delete_items(&bi, 0, item_pos, 1, -1);
  80. if (!item_pos && tb->CFL[0]) {
  81. if (B_NR_ITEMS(tbS0)) {
  82. replace_key(tb, tb->CFL[0], tb->lkey[0], tbS0, 0);
  83. } else {
  84. if (!PATH_H_POSITION(tb->tb_path, 1))
  85. replace_key(tb, tb->CFL[0], tb->lkey[0],
  86. PATH_H_PPARENT(tb->tb_path, 0), 0);
  87. }
  88. }
  89. RFALSE(!item_pos && !tb->CFL[0],
  90. "PAP-12020: tb->CFL[0]==%p, tb->L[0]==%p", tb->CFL[0],
  91. tb->L[0]);
  92. }
  93. /* cut item in S[0] */
  94. static void balance_leaf_when_delete_cut(struct tree_balance *tb)
  95. {
  96. struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
  97. int item_pos = PATH_LAST_POSITION(tb->tb_path);
  98. struct item_head *ih = item_head(tbS0, item_pos);
  99. int pos_in_item = tb->tb_path->pos_in_item;
  100. struct buffer_info bi;
  101. buffer_info_init_tbS0(tb, &bi);
  102. if (is_direntry_le_ih(ih)) {
  103. /*
  104. * UFS unlink semantics are such that you can only
  105. * delete one directory entry at a time.
  106. *
  107. * when we cut a directory tb->insert_size[0] means
  108. * number of entries to be cut (always 1)
  109. */
  110. tb->insert_size[0] = -1;
  111. leaf_cut_from_buffer(&bi, item_pos, pos_in_item,
  112. -tb->insert_size[0]);
  113. RFALSE(!item_pos && !pos_in_item && !tb->CFL[0],
  114. "PAP-12030: can not change delimiting key. CFL[0]=%p",
  115. tb->CFL[0]);
  116. if (!item_pos && !pos_in_item && tb->CFL[0])
  117. replace_key(tb, tb->CFL[0], tb->lkey[0], tbS0, 0);
  118. } else {
  119. leaf_cut_from_buffer(&bi, item_pos, pos_in_item,
  120. -tb->insert_size[0]);
  121. RFALSE(!ih_item_len(ih),
  122. "PAP-12035: cut must leave non-zero dynamic "
  123. "length of item");
  124. }
  125. }
  126. static int balance_leaf_when_delete_left(struct tree_balance *tb)
  127. {
  128. struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
  129. int n = B_NR_ITEMS(tbS0);
  130. /* L[0] must be joined with S[0] */
  131. if (tb->lnum[0] == -1) {
  132. /* R[0] must be also joined with S[0] */
  133. if (tb->rnum[0] == -1) {
  134. if (tb->FR[0] == PATH_H_PPARENT(tb->tb_path, 0)) {
  135. /*
  136. * all contents of all the
  137. * 3 buffers will be in L[0]
  138. */
  139. if (PATH_H_POSITION(tb->tb_path, 1) == 0 &&
  140. 1 < B_NR_ITEMS(tb->FR[0]))
  141. replace_key(tb, tb->CFL[0],
  142. tb->lkey[0], tb->FR[0], 1);
  143. leaf_move_items(LEAF_FROM_S_TO_L, tb, n, -1,
  144. NULL);
  145. leaf_move_items(LEAF_FROM_R_TO_L, tb,
  146. B_NR_ITEMS(tb->R[0]), -1,
  147. NULL);
  148. reiserfs_invalidate_buffer(tb, tbS0);
  149. reiserfs_invalidate_buffer(tb, tb->R[0]);
  150. return 0;
  151. }
  152. /* all contents of all the 3 buffers will be in R[0] */
  153. leaf_move_items(LEAF_FROM_S_TO_R, tb, n, -1, NULL);
  154. leaf_move_items(LEAF_FROM_L_TO_R, tb,
  155. B_NR_ITEMS(tb->L[0]), -1, NULL);
  156. /* right_delimiting_key is correct in R[0] */
  157. replace_key(tb, tb->CFR[0], tb->rkey[0], tb->R[0], 0);
  158. reiserfs_invalidate_buffer(tb, tbS0);
  159. reiserfs_invalidate_buffer(tb, tb->L[0]);
  160. return -1;
  161. }
  162. RFALSE(tb->rnum[0] != 0,
  163. "PAP-12045: rnum must be 0 (%d)", tb->rnum[0]);
  164. /* all contents of L[0] and S[0] will be in L[0] */
  165. leaf_shift_left(tb, n, -1);
  166. reiserfs_invalidate_buffer(tb, tbS0);
  167. return 0;
  168. }
  169. /*
  170. * a part of contents of S[0] will be in L[0] and
  171. * the rest part of S[0] will be in R[0]
  172. */
  173. RFALSE((tb->lnum[0] + tb->rnum[0] < n) ||
  174. (tb->lnum[0] + tb->rnum[0] > n + 1),
  175. "PAP-12050: rnum(%d) and lnum(%d) and item "
  176. "number(%d) in S[0] are not consistent",
  177. tb->rnum[0], tb->lnum[0], n);
  178. RFALSE((tb->lnum[0] + tb->rnum[0] == n) &&
  179. (tb->lbytes != -1 || tb->rbytes != -1),
  180. "PAP-12055: bad rbytes (%d)/lbytes (%d) "
  181. "parameters when items are not split",
  182. tb->rbytes, tb->lbytes);
  183. RFALSE((tb->lnum[0] + tb->rnum[0] == n + 1) &&
  184. (tb->lbytes < 1 || tb->rbytes != -1),
  185. "PAP-12060: bad rbytes (%d)/lbytes (%d) "
  186. "parameters when items are split",
  187. tb->rbytes, tb->lbytes);
  188. leaf_shift_left(tb, tb->lnum[0], tb->lbytes);
  189. leaf_shift_right(tb, tb->rnum[0], tb->rbytes);
  190. reiserfs_invalidate_buffer(tb, tbS0);
  191. return 0;
  192. }
  193. /*
  194. * Balance leaf node in case of delete or cut: insert_size[0] < 0
  195. *
  196. * lnum, rnum can have values >= -1
  197. * -1 means that the neighbor must be joined with S
  198. * 0 means that nothing should be done with the neighbor
  199. * >0 means to shift entirely or partly the specified number of items
  200. * to the neighbor
  201. */
  202. static int balance_leaf_when_delete(struct tree_balance *tb, int flag)
  203. {
  204. struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
  205. struct buffer_info bi;
  206. int n;
  207. RFALSE(tb->FR[0] && B_LEVEL(tb->FR[0]) != DISK_LEAF_NODE_LEVEL + 1,
  208. "vs- 12000: level: wrong FR %z", tb->FR[0]);
  209. RFALSE(tb->blknum[0] > 1,
  210. "PAP-12005: tb->blknum == %d, can not be > 1", tb->blknum[0]);
  211. RFALSE(!tb->blknum[0] && !PATH_H_PPARENT(tb->tb_path, 0),
  212. "PAP-12010: tree can not be empty");
  213. buffer_info_init_tbS0(tb, &bi);
  214. /* Delete or truncate the item */
  215. BUG_ON(flag != M_DELETE && flag != M_CUT);
  216. if (flag == M_DELETE)
  217. balance_leaf_when_delete_del(tb);
  218. else /* M_CUT */
  219. balance_leaf_when_delete_cut(tb);
  220. /*
  221. * the rule is that no shifting occurs unless by shifting
  222. * a node can be freed
  223. */
  224. n = B_NR_ITEMS(tbS0);
  225. /* L[0] takes part in balancing */
  226. if (tb->lnum[0])
  227. return balance_leaf_when_delete_left(tb);
  228. if (tb->rnum[0] == -1) {
  229. /* all contents of R[0] and S[0] will be in R[0] */
  230. leaf_shift_right(tb, n, -1);
  231. reiserfs_invalidate_buffer(tb, tbS0);
  232. return 0;
  233. }
  234. RFALSE(tb->rnum[0],
  235. "PAP-12065: bad rnum parameter must be 0 (%d)", tb->rnum[0]);
  236. return 0;
  237. }
  238. static unsigned int balance_leaf_insert_left(struct tree_balance *tb,
  239. struct item_head *const ih,
  240. const char * const body)
  241. {
  242. int ret;
  243. struct buffer_info bi;
  244. int n = B_NR_ITEMS(tb->L[0]);
  245. unsigned body_shift_bytes = 0;
  246. if (tb->item_pos == tb->lnum[0] - 1 && tb->lbytes != -1) {
  247. /* part of new item falls into L[0] */
  248. int new_item_len, shift;
  249. ret = leaf_shift_left(tb, tb->lnum[0] - 1, -1);
  250. /* Calculate item length to insert to S[0] */
  251. new_item_len = ih_item_len(ih) - tb->lbytes;
  252. /* Calculate and check item length to insert to L[0] */
  253. put_ih_item_len(ih, ih_item_len(ih) - new_item_len);
  254. RFALSE(ih_item_len(ih) <= 0,
  255. "PAP-12080: there is nothing to insert into L[0]: "
  256. "ih_item_len=%d", ih_item_len(ih));
  257. /* Insert new item into L[0] */
  258. buffer_info_init_left(tb, &bi);
  259. leaf_insert_into_buf(&bi, n + tb->item_pos - ret, ih, body,
  260. min_t(int, tb->zeroes_num, ih_item_len(ih)));
  261. /*
  262. * Calculate key component, item length and body to
  263. * insert into S[0]
  264. */
  265. shift = 0;
  266. if (is_indirect_le_ih(ih))
  267. shift = tb->tb_sb->s_blocksize_bits - UNFM_P_SHIFT;
  268. add_le_ih_k_offset(ih, tb->lbytes << shift);
  269. put_ih_item_len(ih, new_item_len);
  270. if (tb->lbytes > tb->zeroes_num) {
  271. body_shift_bytes = tb->lbytes - tb->zeroes_num;
  272. tb->zeroes_num = 0;
  273. } else
  274. tb->zeroes_num -= tb->lbytes;
  275. RFALSE(ih_item_len(ih) <= 0,
  276. "PAP-12085: there is nothing to insert into S[0]: "
  277. "ih_item_len=%d", ih_item_len(ih));
  278. } else {
  279. /* new item in whole falls into L[0] */
  280. /* Shift lnum[0]-1 items to L[0] */
  281. ret = leaf_shift_left(tb, tb->lnum[0] - 1, tb->lbytes);
  282. /* Insert new item into L[0] */
  283. buffer_info_init_left(tb, &bi);
  284. leaf_insert_into_buf(&bi, n + tb->item_pos - ret, ih, body,
  285. tb->zeroes_num);
  286. tb->insert_size[0] = 0;
  287. tb->zeroes_num = 0;
  288. }
  289. return body_shift_bytes;
  290. }
  291. static void balance_leaf_paste_left_shift_dirent(struct tree_balance *tb,
  292. struct item_head * const ih,
  293. const char * const body)
  294. {
  295. int n = B_NR_ITEMS(tb->L[0]);
  296. struct buffer_info bi;
  297. RFALSE(tb->zeroes_num,
  298. "PAP-12090: invalid parameter in case of a directory");
  299. /* directory item */
  300. if (tb->lbytes > tb->pos_in_item) {
  301. /* new directory entry falls into L[0] */
  302. struct item_head *pasted;
  303. int ret, l_pos_in_item = tb->pos_in_item;
  304. /*
  305. * Shift lnum[0] - 1 items in whole.
  306. * Shift lbytes - 1 entries from given directory item
  307. */
  308. ret = leaf_shift_left(tb, tb->lnum[0], tb->lbytes - 1);
  309. if (ret && !tb->item_pos) {
  310. pasted = item_head(tb->L[0], B_NR_ITEMS(tb->L[0]) - 1);
  311. l_pos_in_item += ih_entry_count(pasted) -
  312. (tb->lbytes - 1);
  313. }
  314. /* Append given directory entry to directory item */
  315. buffer_info_init_left(tb, &bi);
  316. leaf_paste_in_buffer(&bi, n + tb->item_pos - ret,
  317. l_pos_in_item, tb->insert_size[0],
  318. body, tb->zeroes_num);
  319. /*
  320. * previous string prepared space for pasting new entry,
  321. * following string pastes this entry
  322. */
  323. /*
  324. * when we have merge directory item, pos_in_item
  325. * has been changed too
  326. */
  327. /* paste new directory entry. 1 is entry number */
  328. leaf_paste_entries(&bi, n + tb->item_pos - ret,
  329. l_pos_in_item, 1,
  330. (struct reiserfs_de_head *) body,
  331. body + DEH_SIZE, tb->insert_size[0]);
  332. tb->insert_size[0] = 0;
  333. } else {
  334. /* new directory item doesn't fall into L[0] */
  335. /*
  336. * Shift lnum[0]-1 items in whole. Shift lbytes
  337. * directory entries from directory item number lnum[0]
  338. */
  339. leaf_shift_left(tb, tb->lnum[0], tb->lbytes);
  340. }
  341. /* Calculate new position to append in item body */
  342. tb->pos_in_item -= tb->lbytes;
  343. }
  344. static unsigned int balance_leaf_paste_left_shift(struct tree_balance *tb,
  345. struct item_head * const ih,
  346. const char * const body)
  347. {
  348. struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
  349. int n = B_NR_ITEMS(tb->L[0]);
  350. struct buffer_info bi;
  351. int body_shift_bytes = 0;
  352. if (is_direntry_le_ih(item_head(tbS0, tb->item_pos))) {
  353. balance_leaf_paste_left_shift_dirent(tb, ih, body);
  354. return 0;
  355. }
  356. RFALSE(tb->lbytes <= 0,
  357. "PAP-12095: there is nothing to shift to L[0]. "
  358. "lbytes=%d", tb->lbytes);
  359. RFALSE(tb->pos_in_item != ih_item_len(item_head(tbS0, tb->item_pos)),
  360. "PAP-12100: incorrect position to paste: "
  361. "item_len=%d, pos_in_item=%d",
  362. ih_item_len(item_head(tbS0, tb->item_pos)), tb->pos_in_item);
  363. /* appended item will be in L[0] in whole */
  364. if (tb->lbytes >= tb->pos_in_item) {
  365. struct item_head *tbS0_pos_ih, *tbL0_ih;
  366. struct item_head *tbS0_0_ih;
  367. struct reiserfs_key *left_delim_key;
  368. int ret, l_n, version, temp_l;
  369. tbS0_pos_ih = item_head(tbS0, tb->item_pos);
  370. tbS0_0_ih = item_head(tbS0, 0);
  371. /*
  372. * this bytes number must be appended
  373. * to the last item of L[h]
  374. */
  375. l_n = tb->lbytes - tb->pos_in_item;
  376. /* Calculate new insert_size[0] */
  377. tb->insert_size[0] -= l_n;
  378. RFALSE(tb->insert_size[0] <= 0,
  379. "PAP-12105: there is nothing to paste into "
  380. "L[0]. insert_size=%d", tb->insert_size[0]);
  381. ret = leaf_shift_left(tb, tb->lnum[0],
  382. ih_item_len(tbS0_pos_ih));
  383. tbL0_ih = item_head(tb->L[0], n + tb->item_pos - ret);
  384. /* Append to body of item in L[0] */
  385. buffer_info_init_left(tb, &bi);
  386. leaf_paste_in_buffer(&bi, n + tb->item_pos - ret,
  387. ih_item_len(tbL0_ih), l_n, body,
  388. min_t(int, l_n, tb->zeroes_num));
  389. /*
  390. * 0-th item in S0 can be only of DIRECT type
  391. * when l_n != 0
  392. */
  393. temp_l = l_n;
  394. RFALSE(ih_item_len(tbS0_0_ih),
  395. "PAP-12106: item length must be 0");
  396. RFALSE(comp_short_le_keys(&tbS0_0_ih->ih_key,
  397. leaf_key(tb->L[0], n + tb->item_pos - ret)),
  398. "PAP-12107: items must be of the same file");
  399. if (is_indirect_le_ih(tbL0_ih)) {
  400. int shift = tb->tb_sb->s_blocksize_bits - UNFM_P_SHIFT;
  401. temp_l = l_n << shift;
  402. }
  403. /* update key of first item in S0 */
  404. version = ih_version(tbS0_0_ih);
  405. add_le_key_k_offset(version, &tbS0_0_ih->ih_key, temp_l);
  406. /* update left delimiting key */
  407. left_delim_key = internal_key(tb->CFL[0], tb->lkey[0]);
  408. add_le_key_k_offset(version, left_delim_key, temp_l);
  409. /*
  410. * Calculate new body, position in item and
  411. * insert_size[0]
  412. */
  413. if (l_n > tb->zeroes_num) {
  414. body_shift_bytes = l_n - tb->zeroes_num;
  415. tb->zeroes_num = 0;
  416. } else
  417. tb->zeroes_num -= l_n;
  418. tb->pos_in_item = 0;
  419. RFALSE(comp_short_le_keys(&tbS0_0_ih->ih_key,
  420. leaf_key(tb->L[0],
  421. B_NR_ITEMS(tb->L[0]) - 1)) ||
  422. !op_is_left_mergeable(leaf_key(tbS0, 0), tbS0->b_size) ||
  423. !op_is_left_mergeable(left_delim_key, tbS0->b_size),
  424. "PAP-12120: item must be merge-able with left "
  425. "neighboring item");
  426. } else {
  427. /* only part of the appended item will be in L[0] */
  428. /* Calculate position in item for append in S[0] */
  429. tb->pos_in_item -= tb->lbytes;
  430. RFALSE(tb->pos_in_item <= 0,
  431. "PAP-12125: no place for paste. pos_in_item=%d",
  432. tb->pos_in_item);
  433. /*
  434. * Shift lnum[0] - 1 items in whole.
  435. * Shift lbytes - 1 byte from item number lnum[0]
  436. */
  437. leaf_shift_left(tb, tb->lnum[0], tb->lbytes);
  438. }
  439. return body_shift_bytes;
  440. }
  441. /* appended item will be in L[0] in whole */
  442. static void balance_leaf_paste_left_whole(struct tree_balance *tb,
  443. struct item_head * const ih,
  444. const char * const body)
  445. {
  446. struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
  447. int n = B_NR_ITEMS(tb->L[0]);
  448. struct buffer_info bi;
  449. struct item_head *pasted;
  450. int ret;
  451. /* if we paste into first item of S[0] and it is left mergable */
  452. if (!tb->item_pos &&
  453. op_is_left_mergeable(leaf_key(tbS0, 0), tbS0->b_size)) {
  454. /*
  455. * then increment pos_in_item by the size of the
  456. * last item in L[0]
  457. */
  458. pasted = item_head(tb->L[0], n - 1);
  459. if (is_direntry_le_ih(pasted))
  460. tb->pos_in_item += ih_entry_count(pasted);
  461. else
  462. tb->pos_in_item += ih_item_len(pasted);
  463. }
  464. /*
  465. * Shift lnum[0] - 1 items in whole.
  466. * Shift lbytes - 1 byte from item number lnum[0]
  467. */
  468. ret = leaf_shift_left(tb, tb->lnum[0], tb->lbytes);
  469. /* Append to body of item in L[0] */
  470. buffer_info_init_left(tb, &bi);
  471. leaf_paste_in_buffer(&bi, n + tb->item_pos - ret, tb->pos_in_item,
  472. tb->insert_size[0], body, tb->zeroes_num);
  473. /* if appended item is directory, paste entry */
  474. pasted = item_head(tb->L[0], n + tb->item_pos - ret);
  475. if (is_direntry_le_ih(pasted))
  476. leaf_paste_entries(&bi, n + tb->item_pos - ret,
  477. tb->pos_in_item, 1,
  478. (struct reiserfs_de_head *)body,
  479. body + DEH_SIZE, tb->insert_size[0]);
  480. /*
  481. * if appended item is indirect item, put unformatted node
  482. * into un list
  483. */
  484. if (is_indirect_le_ih(pasted))
  485. set_ih_free_space(pasted, 0);
  486. tb->insert_size[0] = 0;
  487. tb->zeroes_num = 0;
  488. }
  489. static unsigned int balance_leaf_paste_left(struct tree_balance *tb,
  490. struct item_head * const ih,
  491. const char * const body)
  492. {
  493. /* we must shift the part of the appended item */
  494. if (tb->item_pos == tb->lnum[0] - 1 && tb->lbytes != -1)
  495. return balance_leaf_paste_left_shift(tb, ih, body);
  496. else
  497. balance_leaf_paste_left_whole(tb, ih, body);
  498. return 0;
  499. }
  500. /* Shift lnum[0] items from S[0] to the left neighbor L[0] */
  501. static unsigned int balance_leaf_left(struct tree_balance *tb,
  502. struct item_head * const ih,
  503. const char * const body, int flag)
  504. {
  505. if (tb->lnum[0] <= 0)
  506. return 0;
  507. /* new item or it part falls to L[0], shift it too */
  508. if (tb->item_pos < tb->lnum[0]) {
  509. BUG_ON(flag != M_INSERT && flag != M_PASTE);
  510. if (flag == M_INSERT)
  511. return balance_leaf_insert_left(tb, ih, body);
  512. else /* M_PASTE */
  513. return balance_leaf_paste_left(tb, ih, body);
  514. } else
  515. /* new item doesn't fall into L[0] */
  516. leaf_shift_left(tb, tb->lnum[0], tb->lbytes);
  517. return 0;
  518. }
  519. static void balance_leaf_insert_right(struct tree_balance *tb,
  520. struct item_head * const ih,
  521. const char * const body)
  522. {
  523. struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
  524. int n = B_NR_ITEMS(tbS0);
  525. struct buffer_info bi;
  526. /* new item or part of it doesn't fall into R[0] */
  527. if (n - tb->rnum[0] >= tb->item_pos) {
  528. leaf_shift_right(tb, tb->rnum[0], tb->rbytes);
  529. return;
  530. }
  531. /* new item or its part falls to R[0] */
  532. /* part of new item falls into R[0] */
  533. if (tb->item_pos == n - tb->rnum[0] + 1 && tb->rbytes != -1) {
  534. loff_t old_key_comp, old_len, r_zeroes_number;
  535. const char *r_body;
  536. int shift;
  537. loff_t offset;
  538. leaf_shift_right(tb, tb->rnum[0] - 1, -1);
  539. /* Remember key component and item length */
  540. old_key_comp = le_ih_k_offset(ih);
  541. old_len = ih_item_len(ih);
  542. /*
  543. * Calculate key component and item length to insert
  544. * into R[0]
  545. */
  546. shift = 0;
  547. if (is_indirect_le_ih(ih))
  548. shift = tb->tb_sb->s_blocksize_bits - UNFM_P_SHIFT;
  549. offset = le_ih_k_offset(ih) + ((old_len - tb->rbytes) << shift);
  550. set_le_ih_k_offset(ih, offset);
  551. put_ih_item_len(ih, tb->rbytes);
  552. /* Insert part of the item into R[0] */
  553. buffer_info_init_right(tb, &bi);
  554. if ((old_len - tb->rbytes) > tb->zeroes_num) {
  555. r_zeroes_number = 0;
  556. r_body = body + (old_len - tb->rbytes) - tb->zeroes_num;
  557. } else {
  558. r_body = body;
  559. r_zeroes_number = tb->zeroes_num -
  560. (old_len - tb->rbytes);
  561. tb->zeroes_num -= r_zeroes_number;
  562. }
  563. leaf_insert_into_buf(&bi, 0, ih, r_body, r_zeroes_number);
  564. /* Replace right delimiting key by first key in R[0] */
  565. replace_key(tb, tb->CFR[0], tb->rkey[0], tb->R[0], 0);
  566. /*
  567. * Calculate key component and item length to
  568. * insert into S[0]
  569. */
  570. set_le_ih_k_offset(ih, old_key_comp);
  571. put_ih_item_len(ih, old_len - tb->rbytes);
  572. tb->insert_size[0] -= tb->rbytes;
  573. } else {
  574. /* whole new item falls into R[0] */
  575. /* Shift rnum[0]-1 items to R[0] */
  576. leaf_shift_right(tb, tb->rnum[0] - 1, tb->rbytes);
  577. /* Insert new item into R[0] */
  578. buffer_info_init_right(tb, &bi);
  579. leaf_insert_into_buf(&bi, tb->item_pos - n + tb->rnum[0] - 1,
  580. ih, body, tb->zeroes_num);
  581. if (tb->item_pos - n + tb->rnum[0] - 1 == 0)
  582. replace_key(tb, tb->CFR[0], tb->rkey[0], tb->R[0], 0);
  583. tb->zeroes_num = tb->insert_size[0] = 0;
  584. }
  585. }
  586. static void balance_leaf_paste_right_shift_dirent(struct tree_balance *tb,
  587. struct item_head * const ih,
  588. const char * const body)
  589. {
  590. struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
  591. struct buffer_info bi;
  592. int entry_count;
  593. RFALSE(tb->zeroes_num,
  594. "PAP-12145: invalid parameter in case of a directory");
  595. entry_count = ih_entry_count(item_head(tbS0, tb->item_pos));
  596. /* new directory entry falls into R[0] */
  597. if (entry_count - tb->rbytes < tb->pos_in_item) {
  598. int paste_entry_position;
  599. RFALSE(tb->rbytes - 1 >= entry_count || !tb->insert_size[0],
  600. "PAP-12150: no enough of entries to shift to R[0]: "
  601. "rbytes=%d, entry_count=%d", tb->rbytes, entry_count);
  602. /*
  603. * Shift rnum[0]-1 items in whole.
  604. * Shift rbytes-1 directory entries from directory
  605. * item number rnum[0]
  606. */
  607. leaf_shift_right(tb, tb->rnum[0], tb->rbytes - 1);
  608. /* Paste given directory entry to directory item */
  609. paste_entry_position = tb->pos_in_item - entry_count +
  610. tb->rbytes - 1;
  611. buffer_info_init_right(tb, &bi);
  612. leaf_paste_in_buffer(&bi, 0, paste_entry_position,
  613. tb->insert_size[0], body, tb->zeroes_num);
  614. /* paste entry */
  615. leaf_paste_entries(&bi, 0, paste_entry_position, 1,
  616. (struct reiserfs_de_head *) body,
  617. body + DEH_SIZE, tb->insert_size[0]);
  618. /* change delimiting keys */
  619. if (paste_entry_position == 0)
  620. replace_key(tb, tb->CFR[0], tb->rkey[0], tb->R[0], 0);
  621. tb->insert_size[0] = 0;
  622. tb->pos_in_item++;
  623. } else {
  624. /* new directory entry doesn't fall into R[0] */
  625. leaf_shift_right(tb, tb->rnum[0], tb->rbytes);
  626. }
  627. }
  628. static void balance_leaf_paste_right_shift(struct tree_balance *tb,
  629. struct item_head * const ih,
  630. const char * const body)
  631. {
  632. struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
  633. int n_shift, n_rem, r_zeroes_number, version;
  634. unsigned long temp_rem;
  635. const char *r_body;
  636. struct buffer_info bi;
  637. /* we append to directory item */
  638. if (is_direntry_le_ih(item_head(tbS0, tb->item_pos))) {
  639. balance_leaf_paste_right_shift_dirent(tb, ih, body);
  640. return;
  641. }
  642. /* regular object */
  643. /*
  644. * Calculate number of bytes which must be shifted
  645. * from appended item
  646. */
  647. n_shift = tb->rbytes - tb->insert_size[0];
  648. if (n_shift < 0)
  649. n_shift = 0;
  650. RFALSE(tb->pos_in_item != ih_item_len(item_head(tbS0, tb->item_pos)),
  651. "PAP-12155: invalid position to paste. ih_item_len=%d, "
  652. "pos_in_item=%d", tb->pos_in_item,
  653. ih_item_len(item_head(tbS0, tb->item_pos)));
  654. leaf_shift_right(tb, tb->rnum[0], n_shift);
  655. /*
  656. * Calculate number of bytes which must remain in body
  657. * after appending to R[0]
  658. */
  659. n_rem = tb->insert_size[0] - tb->rbytes;
  660. if (n_rem < 0)
  661. n_rem = 0;
  662. temp_rem = n_rem;
  663. version = ih_version(item_head(tb->R[0], 0));
  664. if (is_indirect_le_key(version, leaf_key(tb->R[0], 0))) {
  665. int shift = tb->tb_sb->s_blocksize_bits - UNFM_P_SHIFT;
  666. temp_rem = n_rem << shift;
  667. }
  668. add_le_key_k_offset(version, leaf_key(tb->R[0], 0), temp_rem);
  669. add_le_key_k_offset(version, internal_key(tb->CFR[0], tb->rkey[0]),
  670. temp_rem);
  671. do_balance_mark_internal_dirty(tb, tb->CFR[0], 0);
  672. /* Append part of body into R[0] */
  673. buffer_info_init_right(tb, &bi);
  674. if (n_rem > tb->zeroes_num) {
  675. r_zeroes_number = 0;
  676. r_body = body + n_rem - tb->zeroes_num;
  677. } else {
  678. r_body = body;
  679. r_zeroes_number = tb->zeroes_num - n_rem;
  680. tb->zeroes_num -= r_zeroes_number;
  681. }
  682. leaf_paste_in_buffer(&bi, 0, n_shift, tb->insert_size[0] - n_rem,
  683. r_body, r_zeroes_number);
  684. if (is_indirect_le_ih(item_head(tb->R[0], 0)))
  685. set_ih_free_space(item_head(tb->R[0], 0), 0);
  686. tb->insert_size[0] = n_rem;
  687. if (!n_rem)
  688. tb->pos_in_item++;
  689. }
  690. static void balance_leaf_paste_right_whole(struct tree_balance *tb,
  691. struct item_head * const ih,
  692. const char * const body)
  693. {
  694. struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
  695. int n = B_NR_ITEMS(tbS0);
  696. struct item_head *pasted;
  697. struct buffer_info bi;
  698. buffer_info_init_right(tb, &bi);
  699. leaf_shift_right(tb, tb->rnum[0], tb->rbytes);
  700. /* append item in R[0] */
  701. if (tb->pos_in_item >= 0) {
  702. buffer_info_init_right(tb, &bi);
  703. leaf_paste_in_buffer(&bi, tb->item_pos - n + tb->rnum[0],
  704. tb->pos_in_item, tb->insert_size[0], body,
  705. tb->zeroes_num);
  706. }
  707. /* paste new entry, if item is directory item */
  708. pasted = item_head(tb->R[0], tb->item_pos - n + tb->rnum[0]);
  709. if (is_direntry_le_ih(pasted) && tb->pos_in_item >= 0) {
  710. leaf_paste_entries(&bi, tb->item_pos - n + tb->rnum[0],
  711. tb->pos_in_item, 1,
  712. (struct reiserfs_de_head *)body,
  713. body + DEH_SIZE, tb->insert_size[0]);
  714. if (!tb->pos_in_item) {
  715. RFALSE(tb->item_pos - n + tb->rnum[0],
  716. "PAP-12165: directory item must be first "
  717. "item of node when pasting is in 0th position");
  718. /* update delimiting keys */
  719. replace_key(tb, tb->CFR[0], tb->rkey[0], tb->R[0], 0);
  720. }
  721. }
  722. if (is_indirect_le_ih(pasted))
  723. set_ih_free_space(pasted, 0);
  724. tb->zeroes_num = tb->insert_size[0] = 0;
  725. }
  726. static void balance_leaf_paste_right(struct tree_balance *tb,
  727. struct item_head * const ih,
  728. const char * const body)
  729. {
  730. struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
  731. int n = B_NR_ITEMS(tbS0);
  732. /* new item doesn't fall into R[0] */
  733. if (n - tb->rnum[0] > tb->item_pos) {
  734. leaf_shift_right(tb, tb->rnum[0], tb->rbytes);
  735. return;
  736. }
  737. /* pasted item or part of it falls to R[0] */
  738. if (tb->item_pos == n - tb->rnum[0] && tb->rbytes != -1)
  739. /* we must shift the part of the appended item */
  740. balance_leaf_paste_right_shift(tb, ih, body);
  741. else
  742. /* pasted item in whole falls into R[0] */
  743. balance_leaf_paste_right_whole(tb, ih, body);
  744. }
  745. /* shift rnum[0] items from S[0] to the right neighbor R[0] */
  746. static void balance_leaf_right(struct tree_balance *tb,
  747. struct item_head * const ih,
  748. const char * const body, int flag)
  749. {
  750. if (tb->rnum[0] <= 0)
  751. return;
  752. BUG_ON(flag != M_INSERT && flag != M_PASTE);
  753. if (flag == M_INSERT)
  754. balance_leaf_insert_right(tb, ih, body);
  755. else /* M_PASTE */
  756. balance_leaf_paste_right(tb, ih, body);
  757. }
  758. static void balance_leaf_new_nodes_insert(struct tree_balance *tb,
  759. struct item_head * const ih,
  760. const char * const body,
  761. struct item_head *insert_key,
  762. struct buffer_head **insert_ptr,
  763. int i)
  764. {
  765. struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
  766. int n = B_NR_ITEMS(tbS0);
  767. struct buffer_info bi;
  768. int shift;
  769. /* new item or it part don't falls into S_new[i] */
  770. if (n - tb->snum[i] >= tb->item_pos) {
  771. leaf_move_items(LEAF_FROM_S_TO_SNEW, tb,
  772. tb->snum[i], tb->sbytes[i], tb->S_new[i]);
  773. return;
  774. }
  775. /* new item or it's part falls to first new node S_new[i] */
  776. /* part of new item falls into S_new[i] */
  777. if (tb->item_pos == n - tb->snum[i] + 1 && tb->sbytes[i] != -1) {
  778. int old_key_comp, old_len, r_zeroes_number;
  779. const char *r_body;
  780. /* Move snum[i]-1 items from S[0] to S_new[i] */
  781. leaf_move_items(LEAF_FROM_S_TO_SNEW, tb, tb->snum[i] - 1, -1,
  782. tb->S_new[i]);
  783. /* Remember key component and item length */
  784. old_key_comp = le_ih_k_offset(ih);
  785. old_len = ih_item_len(ih);
  786. /*
  787. * Calculate key component and item length to insert
  788. * into S_new[i]
  789. */
  790. shift = 0;
  791. if (is_indirect_le_ih(ih))
  792. shift = tb->tb_sb->s_blocksize_bits - UNFM_P_SHIFT;
  793. set_le_ih_k_offset(ih,
  794. le_ih_k_offset(ih) +
  795. ((old_len - tb->sbytes[i]) << shift));
  796. put_ih_item_len(ih, tb->sbytes[i]);
  797. /* Insert part of the item into S_new[i] before 0-th item */
  798. buffer_info_init_bh(tb, &bi, tb->S_new[i]);
  799. if ((old_len - tb->sbytes[i]) > tb->zeroes_num) {
  800. r_zeroes_number = 0;
  801. r_body = body + (old_len - tb->sbytes[i]) -
  802. tb->zeroes_num;
  803. } else {
  804. r_body = body;
  805. r_zeroes_number = tb->zeroes_num - (old_len -
  806. tb->sbytes[i]);
  807. tb->zeroes_num -= r_zeroes_number;
  808. }
  809. leaf_insert_into_buf(&bi, 0, ih, r_body, r_zeroes_number);
  810. /*
  811. * Calculate key component and item length to
  812. * insert into S[i]
  813. */
  814. set_le_ih_k_offset(ih, old_key_comp);
  815. put_ih_item_len(ih, old_len - tb->sbytes[i]);
  816. tb->insert_size[0] -= tb->sbytes[i];
  817. } else {
  818. /* whole new item falls into S_new[i] */
  819. /*
  820. * Shift snum[0] - 1 items to S_new[i]
  821. * (sbytes[i] of split item)
  822. */
  823. leaf_move_items(LEAF_FROM_S_TO_SNEW, tb,
  824. tb->snum[i] - 1, tb->sbytes[i], tb->S_new[i]);
  825. /* Insert new item into S_new[i] */
  826. buffer_info_init_bh(tb, &bi, tb->S_new[i]);
  827. leaf_insert_into_buf(&bi, tb->item_pos - n + tb->snum[i] - 1,
  828. ih, body, tb->zeroes_num);
  829. tb->zeroes_num = tb->insert_size[0] = 0;
  830. }
  831. }
  832. /* we append to directory item */
  833. static void balance_leaf_new_nodes_paste_dirent(struct tree_balance *tb,
  834. struct item_head * const ih,
  835. const char * const body,
  836. struct item_head *insert_key,
  837. struct buffer_head **insert_ptr,
  838. int i)
  839. {
  840. struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
  841. struct item_head *aux_ih = item_head(tbS0, tb->item_pos);
  842. int entry_count = ih_entry_count(aux_ih);
  843. struct buffer_info bi;
  844. if (entry_count - tb->sbytes[i] < tb->pos_in_item &&
  845. tb->pos_in_item <= entry_count) {
  846. /* new directory entry falls into S_new[i] */
  847. RFALSE(!tb->insert_size[0],
  848. "PAP-12215: insert_size is already 0");
  849. RFALSE(tb->sbytes[i] - 1 >= entry_count,
  850. "PAP-12220: there are no so much entries (%d), only %d",
  851. tb->sbytes[i] - 1, entry_count);
  852. /*
  853. * Shift snum[i]-1 items in whole.
  854. * Shift sbytes[i] directory entries
  855. * from directory item number snum[i]
  856. */
  857. leaf_move_items(LEAF_FROM_S_TO_SNEW, tb, tb->snum[i],
  858. tb->sbytes[i] - 1, tb->S_new[i]);
  859. /*
  860. * Paste given directory entry to
  861. * directory item
  862. */
  863. buffer_info_init_bh(tb, &bi, tb->S_new[i]);
  864. leaf_paste_in_buffer(&bi, 0, tb->pos_in_item - entry_count +
  865. tb->sbytes[i] - 1, tb->insert_size[0],
  866. body, tb->zeroes_num);
  867. /* paste new directory entry */
  868. leaf_paste_entries(&bi, 0, tb->pos_in_item - entry_count +
  869. tb->sbytes[i] - 1, 1,
  870. (struct reiserfs_de_head *) body,
  871. body + DEH_SIZE, tb->insert_size[0]);
  872. tb->insert_size[0] = 0;
  873. tb->pos_in_item++;
  874. } else {
  875. /* new directory entry doesn't fall into S_new[i] */
  876. leaf_move_items(LEAF_FROM_S_TO_SNEW, tb, tb->snum[i],
  877. tb->sbytes[i], tb->S_new[i]);
  878. }
  879. }
  880. static void balance_leaf_new_nodes_paste_shift(struct tree_balance *tb,
  881. struct item_head * const ih,
  882. const char * const body,
  883. struct item_head *insert_key,
  884. struct buffer_head **insert_ptr,
  885. int i)
  886. {
  887. struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
  888. struct item_head *aux_ih = item_head(tbS0, tb->item_pos);
  889. int n_shift, n_rem, r_zeroes_number, shift;
  890. const char *r_body;
  891. struct item_head *tmp;
  892. struct buffer_info bi;
  893. RFALSE(ih, "PAP-12210: ih must be 0");
  894. if (is_direntry_le_ih(aux_ih)) {
  895. balance_leaf_new_nodes_paste_dirent(tb, ih, body, insert_key,
  896. insert_ptr, i);
  897. return;
  898. }
  899. /* regular object */
  900. RFALSE(tb->pos_in_item != ih_item_len(item_head(tbS0, tb->item_pos)) ||
  901. tb->insert_size[0] <= 0,
  902. "PAP-12225: item too short or insert_size <= 0");
  903. /*
  904. * Calculate number of bytes which must be shifted from appended item
  905. */
  906. n_shift = tb->sbytes[i] - tb->insert_size[0];
  907. if (n_shift < 0)
  908. n_shift = 0;
  909. leaf_move_items(LEAF_FROM_S_TO_SNEW, tb, tb->snum[i], n_shift,
  910. tb->S_new[i]);
  911. /*
  912. * Calculate number of bytes which must remain in body after
  913. * append to S_new[i]
  914. */
  915. n_rem = tb->insert_size[0] - tb->sbytes[i];
  916. if (n_rem < 0)
  917. n_rem = 0;
  918. /* Append part of body into S_new[0] */
  919. buffer_info_init_bh(tb, &bi, tb->S_new[i]);
  920. if (n_rem > tb->zeroes_num) {
  921. r_zeroes_number = 0;
  922. r_body = body + n_rem - tb->zeroes_num;
  923. } else {
  924. r_body = body;
  925. r_zeroes_number = tb->zeroes_num - n_rem;
  926. tb->zeroes_num -= r_zeroes_number;
  927. }
  928. leaf_paste_in_buffer(&bi, 0, n_shift, tb->insert_size[0] - n_rem,
  929. r_body, r_zeroes_number);
  930. tmp = item_head(tb->S_new[i], 0);
  931. shift = 0;
  932. if (is_indirect_le_ih(tmp)) {
  933. set_ih_free_space(tmp, 0);
  934. shift = tb->tb_sb->s_blocksize_bits - UNFM_P_SHIFT;
  935. }
  936. add_le_ih_k_offset(tmp, n_rem << shift);
  937. tb->insert_size[0] = n_rem;
  938. if (!n_rem)
  939. tb->pos_in_item++;
  940. }
  941. static void balance_leaf_new_nodes_paste_whole(struct tree_balance *tb,
  942. struct item_head * const ih,
  943. const char * const body,
  944. struct item_head *insert_key,
  945. struct buffer_head **insert_ptr,
  946. int i)
  947. {
  948. struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
  949. int n = B_NR_ITEMS(tbS0);
  950. int leaf_mi;
  951. struct item_head *pasted;
  952. struct buffer_info bi;
  953. #ifdef CONFIG_REISERFS_CHECK
  954. struct item_head *ih_check = item_head(tbS0, tb->item_pos);
  955. if (!is_direntry_le_ih(ih_check) &&
  956. (tb->pos_in_item != ih_item_len(ih_check) ||
  957. tb->insert_size[0] <= 0))
  958. reiserfs_panic(tb->tb_sb,
  959. "PAP-12235",
  960. "pos_in_item must be equal to ih_item_len");
  961. #endif
  962. leaf_mi = leaf_move_items(LEAF_FROM_S_TO_SNEW, tb, tb->snum[i],
  963. tb->sbytes[i], tb->S_new[i]);
  964. RFALSE(leaf_mi,
  965. "PAP-12240: unexpected value returned by leaf_move_items (%d)",
  966. leaf_mi);
  967. /* paste into item */
  968. buffer_info_init_bh(tb, &bi, tb->S_new[i]);
  969. leaf_paste_in_buffer(&bi, tb->item_pos - n + tb->snum[i],
  970. tb->pos_in_item, tb->insert_size[0],
  971. body, tb->zeroes_num);
  972. pasted = item_head(tb->S_new[i], tb->item_pos - n +
  973. tb->snum[i]);
  974. if (is_direntry_le_ih(pasted))
  975. leaf_paste_entries(&bi, tb->item_pos - n + tb->snum[i],
  976. tb->pos_in_item, 1,
  977. (struct reiserfs_de_head *)body,
  978. body + DEH_SIZE, tb->insert_size[0]);
  979. /* if we paste to indirect item update ih_free_space */
  980. if (is_indirect_le_ih(pasted))
  981. set_ih_free_space(pasted, 0);
  982. tb->zeroes_num = tb->insert_size[0] = 0;
  983. }
  984. static void balance_leaf_new_nodes_paste(struct tree_balance *tb,
  985. struct item_head * const ih,
  986. const char * const body,
  987. struct item_head *insert_key,
  988. struct buffer_head **insert_ptr,
  989. int i)
  990. {
  991. struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
  992. int n = B_NR_ITEMS(tbS0);
  993. /* pasted item doesn't fall into S_new[i] */
  994. if (n - tb->snum[i] > tb->item_pos) {
  995. leaf_move_items(LEAF_FROM_S_TO_SNEW, tb,
  996. tb->snum[i], tb->sbytes[i], tb->S_new[i]);
  997. return;
  998. }
  999. /* pasted item or part if it falls to S_new[i] */
  1000. if (tb->item_pos == n - tb->snum[i] && tb->sbytes[i] != -1)
  1001. /* we must shift part of the appended item */
  1002. balance_leaf_new_nodes_paste_shift(tb, ih, body, insert_key,
  1003. insert_ptr, i);
  1004. else
  1005. /* item falls wholly into S_new[i] */
  1006. balance_leaf_new_nodes_paste_whole(tb, ih, body, insert_key,
  1007. insert_ptr, i);
  1008. }
  1009. /* Fill new nodes that appear in place of S[0] */
  1010. static void balance_leaf_new_nodes(struct tree_balance *tb,
  1011. struct item_head * const ih,
  1012. const char * const body,
  1013. struct item_head *insert_key,
  1014. struct buffer_head **insert_ptr,
  1015. int flag)
  1016. {
  1017. int i;
  1018. for (i = tb->blknum[0] - 2; i >= 0; i--) {
  1019. BUG_ON(flag != M_INSERT && flag != M_PASTE);
  1020. RFALSE(!tb->snum[i],
  1021. "PAP-12200: snum[%d] == %d. Must be > 0", i,
  1022. tb->snum[i]);
  1023. /* here we shift from S to S_new nodes */
  1024. tb->S_new[i] = get_FEB(tb);
  1025. /* initialized block type and tree level */
  1026. set_blkh_level(B_BLK_HEAD(tb->S_new[i]), DISK_LEAF_NODE_LEVEL);
  1027. if (flag == M_INSERT)
  1028. balance_leaf_new_nodes_insert(tb, ih, body, insert_key,
  1029. insert_ptr, i);
  1030. else /* M_PASTE */
  1031. balance_leaf_new_nodes_paste(tb, ih, body, insert_key,
  1032. insert_ptr, i);
  1033. memcpy(insert_key + i, leaf_key(tb->S_new[i], 0), KEY_SIZE);
  1034. insert_ptr[i] = tb->S_new[i];
  1035. RFALSE(!buffer_journaled(tb->S_new[i])
  1036. || buffer_journal_dirty(tb->S_new[i])
  1037. || buffer_dirty(tb->S_new[i]),
  1038. "PAP-12247: S_new[%d] : (%b)",
  1039. i, tb->S_new[i]);
  1040. }
  1041. }
  1042. static void balance_leaf_finish_node_insert(struct tree_balance *tb,
  1043. struct item_head * const ih,
  1044. const char * const body)
  1045. {
  1046. struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
  1047. struct buffer_info bi;
  1048. buffer_info_init_tbS0(tb, &bi);
  1049. leaf_insert_into_buf(&bi, tb->item_pos, ih, body, tb->zeroes_num);
  1050. /* If we insert the first key change the delimiting key */
  1051. if (tb->item_pos == 0) {
  1052. if (tb->CFL[0]) /* can be 0 in reiserfsck */
  1053. replace_key(tb, tb->CFL[0], tb->lkey[0], tbS0, 0);
  1054. }
  1055. }
  1056. static void balance_leaf_finish_node_paste_dirent(struct tree_balance *tb,
  1057. struct item_head * const ih,
  1058. const char * const body)
  1059. {
  1060. struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
  1061. struct item_head *pasted = item_head(tbS0, tb->item_pos);
  1062. struct buffer_info bi;
  1063. if (tb->pos_in_item >= 0 && tb->pos_in_item <= ih_entry_count(pasted)) {
  1064. RFALSE(!tb->insert_size[0],
  1065. "PAP-12260: insert_size is 0 already");
  1066. /* prepare space */
  1067. buffer_info_init_tbS0(tb, &bi);
  1068. leaf_paste_in_buffer(&bi, tb->item_pos, tb->pos_in_item,
  1069. tb->insert_size[0], body, tb->zeroes_num);
  1070. /* paste entry */
  1071. leaf_paste_entries(&bi, tb->item_pos, tb->pos_in_item, 1,
  1072. (struct reiserfs_de_head *)body,
  1073. body + DEH_SIZE, tb->insert_size[0]);
  1074. if (!tb->item_pos && !tb->pos_in_item) {
  1075. RFALSE(!tb->CFL[0] || !tb->L[0],
  1076. "PAP-12270: CFL[0]/L[0] must be specified");
  1077. if (tb->CFL[0])
  1078. replace_key(tb, tb->CFL[0], tb->lkey[0],
  1079. tbS0, 0);
  1080. }
  1081. tb->insert_size[0] = 0;
  1082. }
  1083. }
  1084. static void balance_leaf_finish_node_paste(struct tree_balance *tb,
  1085. struct item_head * const ih,
  1086. const char * const body)
  1087. {
  1088. struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
  1089. struct buffer_info bi;
  1090. struct item_head *pasted = item_head(tbS0, tb->item_pos);
  1091. /* when directory, may be new entry already pasted */
  1092. if (is_direntry_le_ih(pasted)) {
  1093. balance_leaf_finish_node_paste_dirent(tb, ih, body);
  1094. return;
  1095. }
  1096. /* regular object */
  1097. if (tb->pos_in_item == ih_item_len(pasted)) {
  1098. RFALSE(tb->insert_size[0] <= 0,
  1099. "PAP-12275: insert size must not be %d",
  1100. tb->insert_size[0]);
  1101. buffer_info_init_tbS0(tb, &bi);
  1102. leaf_paste_in_buffer(&bi, tb->item_pos,
  1103. tb->pos_in_item, tb->insert_size[0], body,
  1104. tb->zeroes_num);
  1105. if (is_indirect_le_ih(pasted))
  1106. set_ih_free_space(pasted, 0);
  1107. tb->insert_size[0] = 0;
  1108. }
  1109. #ifdef CONFIG_REISERFS_CHECK
  1110. else if (tb->insert_size[0]) {
  1111. print_cur_tb("12285");
  1112. reiserfs_panic(tb->tb_sb, "PAP-12285",
  1113. "insert_size must be 0 (%d)", tb->insert_size[0]);
  1114. }
  1115. #endif
  1116. }
  1117. /*
  1118. * if the affected item was not wholly shifted then we
  1119. * perform all necessary operations on that part or whole
  1120. * of the affected item which remains in S
  1121. */
  1122. static void balance_leaf_finish_node(struct tree_balance *tb,
  1123. struct item_head * const ih,
  1124. const char * const body, int flag)
  1125. {
  1126. /* if we must insert or append into buffer S[0] */
  1127. if (0 <= tb->item_pos && tb->item_pos < tb->s0num) {
  1128. if (flag == M_INSERT)
  1129. balance_leaf_finish_node_insert(tb, ih, body);
  1130. else /* M_PASTE */
  1131. balance_leaf_finish_node_paste(tb, ih, body);
  1132. }
  1133. }
  1134. /**
  1135. * balance_leaf - reiserfs tree balancing algorithm
  1136. * @tb: tree balance state
  1137. * @ih: item header of inserted item (little endian)
  1138. * @body: body of inserted item or bytes to paste
  1139. * @flag: i - insert, d - delete, c - cut, p - paste (see do_balance)
  1140. * passed back:
  1141. * @insert_key: key to insert new nodes
  1142. * @insert_ptr: array of nodes to insert at the next level
  1143. *
  1144. * In our processing of one level we sometimes determine what must be
  1145. * inserted into the next higher level. This insertion consists of a
  1146. * key or two keys and their corresponding pointers.
  1147. */
  1148. static int balance_leaf(struct tree_balance *tb, struct item_head *ih,
  1149. const char *body, int flag,
  1150. struct item_head *insert_key,
  1151. struct buffer_head **insert_ptr)
  1152. {
  1153. struct buffer_head *tbS0 = PATH_PLAST_BUFFER(tb->tb_path);
  1154. PROC_INFO_INC(tb->tb_sb, balance_at[0]);
  1155. /* Make balance in case insert_size[0] < 0 */
  1156. if (tb->insert_size[0] < 0)
  1157. return balance_leaf_when_delete(tb, flag);
  1158. tb->item_pos = PATH_LAST_POSITION(tb->tb_path),
  1159. tb->pos_in_item = tb->tb_path->pos_in_item,
  1160. tb->zeroes_num = 0;
  1161. if (flag == M_INSERT && !body)
  1162. tb->zeroes_num = ih_item_len(ih);
  1163. /*
  1164. * for indirect item pos_in_item is measured in unformatted node
  1165. * pointers. Recalculate to bytes
  1166. */
  1167. if (flag != M_INSERT
  1168. && is_indirect_le_ih(item_head(tbS0, tb->item_pos)))
  1169. tb->pos_in_item *= UNFM_P_SIZE;
  1170. body += balance_leaf_left(tb, ih, body, flag);
  1171. /* tb->lnum[0] > 0 */
  1172. /* Calculate new item position */
  1173. tb->item_pos -= (tb->lnum[0] - ((tb->lbytes != -1) ? 1 : 0));
  1174. balance_leaf_right(tb, ih, body, flag);
  1175. /* tb->rnum[0] > 0 */
  1176. RFALSE(tb->blknum[0] > 3,
  1177. "PAP-12180: blknum can not be %d. It must be <= 3", tb->blknum[0]);
  1178. RFALSE(tb->blknum[0] < 0,
  1179. "PAP-12185: blknum can not be %d. It must be >= 0", tb->blknum[0]);
  1180. /*
  1181. * if while adding to a node we discover that it is possible to split
  1182. * it in two, and merge the left part into the left neighbor and the
  1183. * right part into the right neighbor, eliminating the node
  1184. */
  1185. if (tb->blknum[0] == 0) { /* node S[0] is empty now */
  1186. RFALSE(!tb->lnum[0] || !tb->rnum[0],
  1187. "PAP-12190: lnum and rnum must not be zero");
  1188. /*
  1189. * if insertion was done before 0-th position in R[0], right
  1190. * delimiting key of the tb->L[0]'s and left delimiting key are
  1191. * not set correctly
  1192. */
  1193. if (tb->CFL[0]) {
  1194. if (!tb->CFR[0])
  1195. reiserfs_panic(tb->tb_sb, "vs-12195",
  1196. "CFR not initialized");
  1197. copy_key(internal_key(tb->CFL[0], tb->lkey[0]),
  1198. internal_key(tb->CFR[0], tb->rkey[0]));
  1199. do_balance_mark_internal_dirty(tb, tb->CFL[0], 0);
  1200. }
  1201. reiserfs_invalidate_buffer(tb, tbS0);
  1202. return 0;
  1203. }
  1204. balance_leaf_new_nodes(tb, ih, body, insert_key, insert_ptr, flag);
  1205. balance_leaf_finish_node(tb, ih, body, flag);
  1206. #ifdef CONFIG_REISERFS_CHECK
  1207. if (flag == M_PASTE && tb->insert_size[0]) {
  1208. print_cur_tb("12290");
  1209. reiserfs_panic(tb->tb_sb,
  1210. "PAP-12290", "insert_size is still not 0 (%d)",
  1211. tb->insert_size[0]);
  1212. }
  1213. #endif
  1214. /* Leaf level of the tree is balanced (end of balance_leaf) */
  1215. return 0;
  1216. }
  1217. /* Make empty node */
  1218. void make_empty_node(struct buffer_info *bi)
  1219. {
  1220. struct block_head *blkh;
  1221. RFALSE(bi->bi_bh == NULL, "PAP-12295: pointer to the buffer is NULL");
  1222. blkh = B_BLK_HEAD(bi->bi_bh);
  1223. set_blkh_nr_item(blkh, 0);
  1224. set_blkh_free_space(blkh, MAX_CHILD_SIZE(bi->bi_bh));
  1225. if (bi->bi_parent)
  1226. B_N_CHILD(bi->bi_parent, bi->bi_position)->dc_size = 0; /* Endian safe if 0 */
  1227. }
  1228. /* Get first empty buffer */
  1229. struct buffer_head *get_FEB(struct tree_balance *tb)
  1230. {
  1231. int i;
  1232. struct buffer_info bi;
  1233. for (i = 0; i < MAX_FEB_SIZE; i++)
  1234. if (tb->FEB[i] != NULL)
  1235. break;
  1236. if (i == MAX_FEB_SIZE)
  1237. reiserfs_panic(tb->tb_sb, "vs-12300", "FEB list is empty");
  1238. buffer_info_init_bh(tb, &bi, tb->FEB[i]);
  1239. make_empty_node(&bi);
  1240. set_buffer_uptodate(tb->FEB[i]);
  1241. tb->used[i] = tb->FEB[i];
  1242. tb->FEB[i] = NULL;
  1243. return tb->used[i];
  1244. }
  1245. /* This is now used because reiserfs_free_block has to be able to schedule. */
  1246. static void store_thrown(struct tree_balance *tb, struct buffer_head *bh)
  1247. {
  1248. int i;
  1249. if (buffer_dirty(bh))
  1250. reiserfs_warning(tb->tb_sb, "reiserfs-12320",
  1251. "called with dirty buffer");
  1252. for (i = 0; i < ARRAY_SIZE(tb->thrown); i++)
  1253. if (!tb->thrown[i]) {
  1254. tb->thrown[i] = bh;
  1255. get_bh(bh); /* free_thrown puts this */
  1256. return;
  1257. }
  1258. reiserfs_warning(tb->tb_sb, "reiserfs-12321",
  1259. "too many thrown buffers");
  1260. }
  1261. static void free_thrown(struct tree_balance *tb)
  1262. {
  1263. int i;
  1264. b_blocknr_t blocknr;
  1265. for (i = 0; i < ARRAY_SIZE(tb->thrown); i++) {
  1266. if (tb->thrown[i]) {
  1267. blocknr = tb->thrown[i]->b_blocknr;
  1268. if (buffer_dirty(tb->thrown[i]))
  1269. reiserfs_warning(tb->tb_sb, "reiserfs-12322",
  1270. "called with dirty buffer %d",
  1271. blocknr);
  1272. brelse(tb->thrown[i]); /* incremented in store_thrown */
  1273. reiserfs_free_block(tb->transaction_handle, NULL,
  1274. blocknr, 0);
  1275. }
  1276. }
  1277. }
  1278. void reiserfs_invalidate_buffer(struct tree_balance *tb, struct buffer_head *bh)
  1279. {
  1280. struct block_head *blkh;
  1281. blkh = B_BLK_HEAD(bh);
  1282. set_blkh_level(blkh, FREE_LEVEL);
  1283. set_blkh_nr_item(blkh, 0);
  1284. clear_buffer_dirty(bh);
  1285. store_thrown(tb, bh);
  1286. }
  1287. /* Replace n_dest'th key in buffer dest by n_src'th key of buffer src.*/
  1288. void replace_key(struct tree_balance *tb, struct buffer_head *dest, int n_dest,
  1289. struct buffer_head *src, int n_src)
  1290. {
  1291. RFALSE(dest == NULL || src == NULL,
  1292. "vs-12305: source or destination buffer is 0 (src=%p, dest=%p)",
  1293. src, dest);
  1294. RFALSE(!B_IS_KEYS_LEVEL(dest),
  1295. "vs-12310: invalid level (%z) for destination buffer. dest must be leaf",
  1296. dest);
  1297. RFALSE(n_dest < 0 || n_src < 0,
  1298. "vs-12315: src(%d) or dest(%d) key number < 0", n_src, n_dest);
  1299. RFALSE(n_dest >= B_NR_ITEMS(dest) || n_src >= B_NR_ITEMS(src),
  1300. "vs-12320: src(%d(%d)) or dest(%d(%d)) key number is too big",
  1301. n_src, B_NR_ITEMS(src), n_dest, B_NR_ITEMS(dest));
  1302. if (B_IS_ITEMS_LEVEL(src))
  1303. /* source buffer contains leaf node */
  1304. memcpy(internal_key(dest, n_dest), item_head(src, n_src),
  1305. KEY_SIZE);
  1306. else
  1307. memcpy(internal_key(dest, n_dest), internal_key(src, n_src),
  1308. KEY_SIZE);
  1309. do_balance_mark_internal_dirty(tb, dest, 0);
  1310. }
  1311. int get_left_neighbor_position(struct tree_balance *tb, int h)
  1312. {
  1313. int Sh_position = PATH_H_POSITION(tb->tb_path, h + 1);
  1314. RFALSE(PATH_H_PPARENT(tb->tb_path, h) == NULL || tb->FL[h] == NULL,
  1315. "vs-12325: FL[%d](%p) or F[%d](%p) does not exist",
  1316. h, tb->FL[h], h, PATH_H_PPARENT(tb->tb_path, h));
  1317. if (Sh_position == 0)
  1318. return B_NR_ITEMS(tb->FL[h]);
  1319. else
  1320. return Sh_position - 1;
  1321. }
  1322. int get_right_neighbor_position(struct tree_balance *tb, int h)
  1323. {
  1324. int Sh_position = PATH_H_POSITION(tb->tb_path, h + 1);
  1325. RFALSE(PATH_H_PPARENT(tb->tb_path, h) == NULL || tb->FR[h] == NULL,
  1326. "vs-12330: F[%d](%p) or FR[%d](%p) does not exist",
  1327. h, PATH_H_PPARENT(tb->tb_path, h), h, tb->FR[h]);
  1328. if (Sh_position == B_NR_ITEMS(PATH_H_PPARENT(tb->tb_path, h)))
  1329. return 0;
  1330. else
  1331. return Sh_position + 1;
  1332. }
  1333. #ifdef CONFIG_REISERFS_CHECK
  1334. int is_reusable(struct super_block *s, b_blocknr_t block, int bit_value);
  1335. static void check_internal_node(struct super_block *s, struct buffer_head *bh,
  1336. char *mes)
  1337. {
  1338. struct disk_child *dc;
  1339. int i;
  1340. RFALSE(!bh, "PAP-12336: bh == 0");
  1341. if (!bh || !B_IS_IN_TREE(bh))
  1342. return;
  1343. RFALSE(!buffer_dirty(bh) &&
  1344. !(buffer_journaled(bh) || buffer_journal_dirty(bh)),
  1345. "PAP-12337: buffer (%b) must be dirty", bh);
  1346. dc = B_N_CHILD(bh, 0);
  1347. for (i = 0; i <= B_NR_ITEMS(bh); i++, dc++) {
  1348. if (!is_reusable(s, dc_block_number(dc), 1)) {
  1349. print_cur_tb(mes);
  1350. reiserfs_panic(s, "PAP-12338",
  1351. "invalid child pointer %y in %b",
  1352. dc, bh);
  1353. }
  1354. }
  1355. }
  1356. static int locked_or_not_in_tree(struct tree_balance *tb,
  1357. struct buffer_head *bh, char *which)
  1358. {
  1359. if ((!buffer_journal_prepared(bh) && buffer_locked(bh)) ||
  1360. !B_IS_IN_TREE(bh)) {
  1361. reiserfs_warning(tb->tb_sb, "vs-12339", "%s (%b)", which, bh);
  1362. return 1;
  1363. }
  1364. return 0;
  1365. }
  1366. static int check_before_balancing(struct tree_balance *tb)
  1367. {
  1368. int retval = 0;
  1369. if (REISERFS_SB(tb->tb_sb)->cur_tb) {
  1370. reiserfs_panic(tb->tb_sb, "vs-12335", "suspect that schedule "
  1371. "occurred based on cur_tb not being null at "
  1372. "this point in code. do_balance cannot properly "
  1373. "handle concurrent tree accesses on a same "
  1374. "mount point.");
  1375. }
  1376. /*
  1377. * double check that buffers that we will modify are unlocked.
  1378. * (fix_nodes should already have prepped all of these for us).
  1379. */
  1380. if (tb->lnum[0]) {
  1381. retval |= locked_or_not_in_tree(tb, tb->L[0], "L[0]");
  1382. retval |= locked_or_not_in_tree(tb, tb->FL[0], "FL[0]");
  1383. retval |= locked_or_not_in_tree(tb, tb->CFL[0], "CFL[0]");
  1384. check_leaf(tb->L[0]);
  1385. }
  1386. if (tb->rnum[0]) {
  1387. retval |= locked_or_not_in_tree(tb, tb->R[0], "R[0]");
  1388. retval |= locked_or_not_in_tree(tb, tb->FR[0], "FR[0]");
  1389. retval |= locked_or_not_in_tree(tb, tb->CFR[0], "CFR[0]");
  1390. check_leaf(tb->R[0]);
  1391. }
  1392. retval |= locked_or_not_in_tree(tb, PATH_PLAST_BUFFER(tb->tb_path),
  1393. "S[0]");
  1394. check_leaf(PATH_PLAST_BUFFER(tb->tb_path));
  1395. return retval;
  1396. }
  1397. static void check_after_balance_leaf(struct tree_balance *tb)
  1398. {
  1399. if (tb->lnum[0]) {
  1400. if (B_FREE_SPACE(tb->L[0]) !=
  1401. MAX_CHILD_SIZE(tb->L[0]) -
  1402. dc_size(B_N_CHILD
  1403. (tb->FL[0], get_left_neighbor_position(tb, 0)))) {
  1404. print_cur_tb("12221");
  1405. reiserfs_panic(tb->tb_sb, "PAP-12355",
  1406. "shift to left was incorrect");
  1407. }
  1408. }
  1409. if (tb->rnum[0]) {
  1410. if (B_FREE_SPACE(tb->R[0]) !=
  1411. MAX_CHILD_SIZE(tb->R[0]) -
  1412. dc_size(B_N_CHILD
  1413. (tb->FR[0], get_right_neighbor_position(tb, 0)))) {
  1414. print_cur_tb("12222");
  1415. reiserfs_panic(tb->tb_sb, "PAP-12360",
  1416. "shift to right was incorrect");
  1417. }
  1418. }
  1419. if (PATH_H_PBUFFER(tb->tb_path, 1) &&
  1420. (B_FREE_SPACE(PATH_H_PBUFFER(tb->tb_path, 0)) !=
  1421. (MAX_CHILD_SIZE(PATH_H_PBUFFER(tb->tb_path, 0)) -
  1422. dc_size(B_N_CHILD(PATH_H_PBUFFER(tb->tb_path, 1),
  1423. PATH_H_POSITION(tb->tb_path, 1)))))) {
  1424. int left = B_FREE_SPACE(PATH_H_PBUFFER(tb->tb_path, 0));
  1425. int right = (MAX_CHILD_SIZE(PATH_H_PBUFFER(tb->tb_path, 0)) -
  1426. dc_size(B_N_CHILD(PATH_H_PBUFFER(tb->tb_path, 1),
  1427. PATH_H_POSITION(tb->tb_path,
  1428. 1))));
  1429. print_cur_tb("12223");
  1430. reiserfs_warning(tb->tb_sb, "reiserfs-12363",
  1431. "B_FREE_SPACE (PATH_H_PBUFFER(tb->tb_path,0)) = %d; "
  1432. "MAX_CHILD_SIZE (%d) - dc_size( %y, %d ) [%d] = %d",
  1433. left,
  1434. MAX_CHILD_SIZE(PATH_H_PBUFFER(tb->tb_path, 0)),
  1435. PATH_H_PBUFFER(tb->tb_path, 1),
  1436. PATH_H_POSITION(tb->tb_path, 1),
  1437. dc_size(B_N_CHILD
  1438. (PATH_H_PBUFFER(tb->tb_path, 1),
  1439. PATH_H_POSITION(tb->tb_path, 1))),
  1440. right);
  1441. reiserfs_panic(tb->tb_sb, "PAP-12365", "S is incorrect");
  1442. }
  1443. }
  1444. static void check_leaf_level(struct tree_balance *tb)
  1445. {
  1446. check_leaf(tb->L[0]);
  1447. check_leaf(tb->R[0]);
  1448. check_leaf(PATH_PLAST_BUFFER(tb->tb_path));
  1449. }
  1450. static void check_internal_levels(struct tree_balance *tb)
  1451. {
  1452. int h;
  1453. /* check all internal nodes */
  1454. for (h = 1; tb->insert_size[h]; h++) {
  1455. check_internal_node(tb->tb_sb, PATH_H_PBUFFER(tb->tb_path, h),
  1456. "BAD BUFFER ON PATH");
  1457. if (tb->lnum[h])
  1458. check_internal_node(tb->tb_sb, tb->L[h], "BAD L");
  1459. if (tb->rnum[h])
  1460. check_internal_node(tb->tb_sb, tb->R[h], "BAD R");
  1461. }
  1462. }
  1463. #endif
  1464. /*
  1465. * Now we have all of the buffers that must be used in balancing of
  1466. * the tree. We rely on the assumption that schedule() will not occur
  1467. * while do_balance works. ( Only interrupt handlers are acceptable.)
  1468. * We balance the tree according to the analysis made before this,
  1469. * using buffers already obtained. For SMP support it will someday be
  1470. * necessary to add ordered locking of tb.
  1471. */
  1472. /*
  1473. * Some interesting rules of balancing:
  1474. * we delete a maximum of two nodes per level per balancing: we never
  1475. * delete R, when we delete two of three nodes L, S, R then we move
  1476. * them into R.
  1477. *
  1478. * we only delete L if we are deleting two nodes, if we delete only
  1479. * one node we delete S
  1480. *
  1481. * if we shift leaves then we shift as much as we can: this is a
  1482. * deliberate policy of extremism in node packing which results in
  1483. * higher average utilization after repeated random balance operations
  1484. * at the cost of more memory copies and more balancing as a result of
  1485. * small insertions to full nodes.
  1486. *
  1487. * if we shift internal nodes we try to evenly balance the node
  1488. * utilization, with consequent less balancing at the cost of lower
  1489. * utilization.
  1490. *
  1491. * one could argue that the policy for directories in leaves should be
  1492. * that of internal nodes, but we will wait until another day to
  1493. * evaluate this.... It would be nice to someday measure and prove
  1494. * these assumptions as to what is optimal....
  1495. */
  1496. static inline void do_balance_starts(struct tree_balance *tb)
  1497. {
  1498. /* use print_cur_tb() to see initial state of struct tree_balance */
  1499. /* store_print_tb (tb); */
  1500. /* do not delete, just comment it out */
  1501. /*
  1502. print_tb(flag, PATH_LAST_POSITION(tb->tb_path),
  1503. tb->tb_path->pos_in_item, tb, "check");
  1504. */
  1505. RFALSE(check_before_balancing(tb), "PAP-12340: locked buffers in TB");
  1506. #ifdef CONFIG_REISERFS_CHECK
  1507. REISERFS_SB(tb->tb_sb)->cur_tb = tb;
  1508. #endif
  1509. }
  1510. static inline void do_balance_completed(struct tree_balance *tb)
  1511. {
  1512. #ifdef CONFIG_REISERFS_CHECK
  1513. check_leaf_level(tb);
  1514. check_internal_levels(tb);
  1515. REISERFS_SB(tb->tb_sb)->cur_tb = NULL;
  1516. #endif
  1517. /*
  1518. * reiserfs_free_block is no longer schedule safe. So, we need to
  1519. * put the buffers we want freed on the thrown list during do_balance,
  1520. * and then free them now
  1521. */
  1522. REISERFS_SB(tb->tb_sb)->s_do_balance++;
  1523. /* release all nodes hold to perform the balancing */
  1524. unfix_nodes(tb);
  1525. free_thrown(tb);
  1526. }
  1527. /*
  1528. * do_balance - balance the tree
  1529. *
  1530. * @tb: tree_balance structure
  1531. * @ih: item header of inserted item
  1532. * @body: body of inserted item or bytes to paste
  1533. * @flag: 'i' - insert, 'd' - delete, 'c' - cut, 'p' paste
  1534. *
  1535. * Cut means delete part of an item (includes removing an entry from a
  1536. * directory).
  1537. *
  1538. * Delete means delete whole item.
  1539. *
  1540. * Insert means add a new item into the tree.
  1541. *
  1542. * Paste means to append to the end of an existing file or to
  1543. * insert a directory entry.
  1544. */
  1545. void do_balance(struct tree_balance *tb, struct item_head *ih,
  1546. const char *body, int flag)
  1547. {
  1548. int child_pos; /* position of a child node in its parent */
  1549. int h; /* level of the tree being processed */
  1550. /*
  1551. * in our processing of one level we sometimes determine what
  1552. * must be inserted into the next higher level. This insertion
  1553. * consists of a key or two keys and their corresponding
  1554. * pointers
  1555. */
  1556. struct item_head insert_key[2];
  1557. /* inserted node-ptrs for the next level */
  1558. struct buffer_head *insert_ptr[2];
  1559. tb->tb_mode = flag;
  1560. tb->need_balance_dirty = 0;
  1561. if (FILESYSTEM_CHANGED_TB(tb)) {
  1562. reiserfs_panic(tb->tb_sb, "clm-6000", "fs generation has "
  1563. "changed");
  1564. }
  1565. /* if we have no real work to do */
  1566. if (!tb->insert_size[0]) {
  1567. reiserfs_warning(tb->tb_sb, "PAP-12350",
  1568. "insert_size == 0, mode == %c", flag);
  1569. unfix_nodes(tb);
  1570. return;
  1571. }
  1572. atomic_inc(&fs_generation(tb->tb_sb));
  1573. do_balance_starts(tb);
  1574. /*
  1575. * balance_leaf returns 0 except if combining L R and S into
  1576. * one node. see balance_internal() for explanation of this
  1577. * line of code.
  1578. */
  1579. child_pos = PATH_H_B_ITEM_ORDER(tb->tb_path, 0) +
  1580. balance_leaf(tb, ih, body, flag, insert_key, insert_ptr);
  1581. #ifdef CONFIG_REISERFS_CHECK
  1582. check_after_balance_leaf(tb);
  1583. #endif
  1584. /* Balance internal level of the tree. */
  1585. for (h = 1; h < MAX_HEIGHT && tb->insert_size[h]; h++)
  1586. child_pos = balance_internal(tb, h, child_pos, insert_key,
  1587. insert_ptr);
  1588. do_balance_completed(tb);
  1589. }