lbalance.c 41 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301
  1. /*
  2. * Copyright 2000 by Hans Reiser, licensing governed by reiserfs/README
  3. */
  4. #include <asm/uaccess.h>
  5. #include <linux/string.h>
  6. #include <linux/time.h>
  7. #include <linux/reiserfs_fs.h>
  8. #include <linux/buffer_head.h>
  9. /* these are used in do_balance.c */
  10. /* leaf_move_items
  11. leaf_shift_left
  12. leaf_shift_right
  13. leaf_delete_items
  14. leaf_insert_into_buf
  15. leaf_paste_in_buffer
  16. leaf_cut_from_buffer
  17. leaf_paste_entries
  18. */
  19. /* copy copy_count entries from source directory item to dest buffer (creating new item if needed) */
  20. static void leaf_copy_dir_entries(struct buffer_info *dest_bi,
  21. struct buffer_head *source, int last_first,
  22. int item_num, int from, int copy_count)
  23. {
  24. struct buffer_head *dest = dest_bi->bi_bh;
  25. int item_num_in_dest; /* either the number of target item,
  26. or if we must create a new item,
  27. the number of the item we will
  28. create it next to */
  29. struct item_head *ih;
  30. struct reiserfs_de_head *deh;
  31. int copy_records_len; /* length of all records in item to be copied */
  32. char *records;
  33. ih = B_N_PITEM_HEAD(source, item_num);
  34. RFALSE(!is_direntry_le_ih(ih), "vs-10000: item must be directory item");
  35. /* length of all record to be copied and first byte of the last of them */
  36. deh = B_I_DEH(source, ih);
  37. if (copy_count) {
  38. copy_records_len = (from ? deh_location(&(deh[from - 1])) :
  39. ih_item_len(ih)) -
  40. deh_location(&(deh[from + copy_count - 1]));
  41. records =
  42. source->b_data + ih_location(ih) +
  43. deh_location(&(deh[from + copy_count - 1]));
  44. } else {
  45. copy_records_len = 0;
  46. records = NULL;
  47. }
  48. /* when copy last to first, dest buffer can contain 0 items */
  49. item_num_in_dest =
  50. (last_first ==
  51. LAST_TO_FIRST) ? ((B_NR_ITEMS(dest)) ? 0 : -1) : (B_NR_ITEMS(dest)
  52. - 1);
  53. /* if there are no items in dest or the first/last item in dest is not item of the same directory */
  54. if ((item_num_in_dest == -1) ||
  55. (last_first == FIRST_TO_LAST && le_ih_k_offset(ih) == DOT_OFFSET) ||
  56. (last_first == LAST_TO_FIRST
  57. && comp_short_le_keys /*COMP_SHORT_KEYS */ (&ih->ih_key,
  58. B_N_PKEY(dest,
  59. item_num_in_dest))))
  60. {
  61. /* create new item in dest */
  62. struct item_head new_ih;
  63. /* form item header */
  64. memcpy(&new_ih.ih_key, &ih->ih_key, KEY_SIZE);
  65. put_ih_version(&new_ih, KEY_FORMAT_3_5);
  66. /* calculate item len */
  67. put_ih_item_len(&new_ih,
  68. DEH_SIZE * copy_count + copy_records_len);
  69. put_ih_entry_count(&new_ih, 0);
  70. if (last_first == LAST_TO_FIRST) {
  71. /* form key by the following way */
  72. if (from < I_ENTRY_COUNT(ih)) {
  73. set_le_ih_k_offset(&new_ih,
  74. deh_offset(&(deh[from])));
  75. /*memcpy (&new_ih.ih_key.k_offset, &deh[from].deh_offset, SHORT_KEY_SIZE); */
  76. } else {
  77. /* no entries will be copied to this item in this function */
  78. set_le_ih_k_offset(&new_ih, U32_MAX);
  79. /* this item is not yet valid, but we want I_IS_DIRECTORY_ITEM to return 1 for it, so we -1 */
  80. }
  81. set_le_key_k_type(KEY_FORMAT_3_5, &(new_ih.ih_key),
  82. TYPE_DIRENTRY);
  83. }
  84. /* insert item into dest buffer */
  85. leaf_insert_into_buf(dest_bi,
  86. (last_first ==
  87. LAST_TO_FIRST) ? 0 : B_NR_ITEMS(dest),
  88. &new_ih, NULL, 0);
  89. } else {
  90. /* prepare space for entries */
  91. leaf_paste_in_buffer(dest_bi,
  92. (last_first ==
  93. FIRST_TO_LAST) ? (B_NR_ITEMS(dest) -
  94. 1) : 0, MAX_US_INT,
  95. DEH_SIZE * copy_count + copy_records_len,
  96. records, 0);
  97. }
  98. item_num_in_dest =
  99. (last_first == FIRST_TO_LAST) ? (B_NR_ITEMS(dest) - 1) : 0;
  100. leaf_paste_entries(dest_bi->bi_bh, item_num_in_dest,
  101. (last_first ==
  102. FIRST_TO_LAST) ? I_ENTRY_COUNT(B_N_PITEM_HEAD(dest,
  103. item_num_in_dest))
  104. : 0, copy_count, deh + from, records,
  105. DEH_SIZE * copy_count + copy_records_len);
  106. }
  107. /* Copy the first (if last_first == FIRST_TO_LAST) or last (last_first == LAST_TO_FIRST) item or
  108. part of it or nothing (see the return 0 below) from SOURCE to the end
  109. (if last_first) or beginning (!last_first) of the DEST */
  110. /* returns 1 if anything was copied, else 0 */
  111. static int leaf_copy_boundary_item(struct buffer_info *dest_bi,
  112. struct buffer_head *src, int last_first,
  113. int bytes_or_entries)
  114. {
  115. struct buffer_head *dest = dest_bi->bi_bh;
  116. int dest_nr_item, src_nr_item; /* number of items in the source and destination buffers */
  117. struct item_head *ih;
  118. struct item_head *dih;
  119. dest_nr_item = B_NR_ITEMS(dest);
  120. if (last_first == FIRST_TO_LAST) {
  121. /* if ( DEST is empty or first item of SOURCE and last item of DEST are the items of different objects
  122. or of different types ) then there is no need to treat this item differently from the other items
  123. that we copy, so we return */
  124. ih = B_N_PITEM_HEAD(src, 0);
  125. dih = B_N_PITEM_HEAD(dest, dest_nr_item - 1);
  126. if (!dest_nr_item
  127. || (!op_is_left_mergeable(&(ih->ih_key), src->b_size)))
  128. /* there is nothing to merge */
  129. return 0;
  130. RFALSE(!ih_item_len(ih),
  131. "vs-10010: item can not have empty length");
  132. if (is_direntry_le_ih(ih)) {
  133. if (bytes_or_entries == -1)
  134. /* copy all entries to dest */
  135. bytes_or_entries = ih_entry_count(ih);
  136. leaf_copy_dir_entries(dest_bi, src, FIRST_TO_LAST, 0, 0,
  137. bytes_or_entries);
  138. return 1;
  139. }
  140. /* copy part of the body of the first item of SOURCE to the end of the body of the last item of the DEST
  141. part defined by 'bytes_or_entries'; if bytes_or_entries == -1 copy whole body; don't create new item header
  142. */
  143. if (bytes_or_entries == -1)
  144. bytes_or_entries = ih_item_len(ih);
  145. #ifdef CONFIG_REISERFS_CHECK
  146. else {
  147. if (bytes_or_entries == ih_item_len(ih)
  148. && is_indirect_le_ih(ih))
  149. if (get_ih_free_space(ih))
  150. reiserfs_panic(NULL,
  151. "vs-10020: leaf_copy_boundary_item: "
  152. "last unformatted node must be filled entirely (%h)",
  153. ih);
  154. }
  155. #endif
  156. /* merge first item (or its part) of src buffer with the last
  157. item of dest buffer. Both are of the same file */
  158. leaf_paste_in_buffer(dest_bi,
  159. dest_nr_item - 1, ih_item_len(dih),
  160. bytes_or_entries, B_I_PITEM(src, ih), 0);
  161. if (is_indirect_le_ih(dih)) {
  162. RFALSE(get_ih_free_space(dih),
  163. "vs-10030: merge to left: last unformatted node of non-last indirect item %h must have zerto free space",
  164. ih);
  165. if (bytes_or_entries == ih_item_len(ih))
  166. set_ih_free_space(dih, get_ih_free_space(ih));
  167. }
  168. return 1;
  169. }
  170. /* copy boundary item to right (last_first == LAST_TO_FIRST) */
  171. /* ( DEST is empty or last item of SOURCE and first item of DEST
  172. are the items of different object or of different types )
  173. */
  174. src_nr_item = B_NR_ITEMS(src);
  175. ih = B_N_PITEM_HEAD(src, src_nr_item - 1);
  176. dih = B_N_PITEM_HEAD(dest, 0);
  177. if (!dest_nr_item || !op_is_left_mergeable(&(dih->ih_key), src->b_size))
  178. return 0;
  179. if (is_direntry_le_ih(ih)) {
  180. if (bytes_or_entries == -1)
  181. /* bytes_or_entries = entries number in last item body of SOURCE */
  182. bytes_or_entries = ih_entry_count(ih);
  183. leaf_copy_dir_entries(dest_bi, src, LAST_TO_FIRST,
  184. src_nr_item - 1,
  185. ih_entry_count(ih) - bytes_or_entries,
  186. bytes_or_entries);
  187. return 1;
  188. }
  189. /* copy part of the body of the last item of SOURCE to the begin of the body of the first item of the DEST;
  190. part defined by 'bytes_or_entries'; if byte_or_entriess == -1 copy whole body; change first item key of the DEST;
  191. don't create new item header
  192. */
  193. RFALSE(is_indirect_le_ih(ih) && get_ih_free_space(ih),
  194. "vs-10040: merge to right: last unformatted node of non-last indirect item must be filled entirely (%h)",
  195. ih);
  196. if (bytes_or_entries == -1) {
  197. /* bytes_or_entries = length of last item body of SOURCE */
  198. bytes_or_entries = ih_item_len(ih);
  199. RFALSE(le_ih_k_offset(dih) !=
  200. le_ih_k_offset(ih) + op_bytes_number(ih, src->b_size),
  201. "vs-10050: items %h and %h do not match", ih, dih);
  202. /* change first item key of the DEST */
  203. set_le_ih_k_offset(dih, le_ih_k_offset(ih));
  204. /* item becomes non-mergeable */
  205. /* or mergeable if left item was */
  206. set_le_ih_k_type(dih, le_ih_k_type(ih));
  207. } else {
  208. /* merge to right only part of item */
  209. RFALSE(ih_item_len(ih) <= bytes_or_entries,
  210. "vs-10060: no so much bytes %lu (needed %lu)",
  211. (unsigned long)ih_item_len(ih),
  212. (unsigned long)bytes_or_entries);
  213. /* change first item key of the DEST */
  214. if (is_direct_le_ih(dih)) {
  215. RFALSE(le_ih_k_offset(dih) <=
  216. (unsigned long)bytes_or_entries,
  217. "vs-10070: dih %h, bytes_or_entries(%d)", dih,
  218. bytes_or_entries);
  219. set_le_ih_k_offset(dih,
  220. le_ih_k_offset(dih) -
  221. bytes_or_entries);
  222. } else {
  223. RFALSE(le_ih_k_offset(dih) <=
  224. (bytes_or_entries / UNFM_P_SIZE) * dest->b_size,
  225. "vs-10080: dih %h, bytes_or_entries(%d)",
  226. dih,
  227. (bytes_or_entries / UNFM_P_SIZE) * dest->b_size);
  228. set_le_ih_k_offset(dih,
  229. le_ih_k_offset(dih) -
  230. ((bytes_or_entries / UNFM_P_SIZE) *
  231. dest->b_size));
  232. }
  233. }
  234. leaf_paste_in_buffer(dest_bi, 0, 0, bytes_or_entries,
  235. B_I_PITEM(src,
  236. ih) + ih_item_len(ih) - bytes_or_entries,
  237. 0);
  238. return 1;
  239. }
  240. /* copy cpy_mun items from buffer src to buffer dest
  241. * last_first == FIRST_TO_LAST means, that we copy cpy_num items beginning from first-th item in src to tail of dest
  242. * last_first == LAST_TO_FIRST means, that we copy cpy_num items beginning from first-th item in src to head of dest
  243. */
  244. static void leaf_copy_items_entirely(struct buffer_info *dest_bi,
  245. struct buffer_head *src, int last_first,
  246. int first, int cpy_num)
  247. {
  248. struct buffer_head *dest;
  249. int nr, free_space;
  250. int dest_before;
  251. int last_loc, last_inserted_loc, location;
  252. int i, j;
  253. struct block_head *blkh;
  254. struct item_head *ih;
  255. RFALSE(last_first != LAST_TO_FIRST && last_first != FIRST_TO_LAST,
  256. "vs-10090: bad last_first parameter %d", last_first);
  257. RFALSE(B_NR_ITEMS(src) - first < cpy_num,
  258. "vs-10100: too few items in source %d, required %d from %d",
  259. B_NR_ITEMS(src), cpy_num, first);
  260. RFALSE(cpy_num < 0, "vs-10110: can not copy negative amount of items");
  261. RFALSE(!dest_bi, "vs-10120: can not copy negative amount of items");
  262. dest = dest_bi->bi_bh;
  263. RFALSE(!dest, "vs-10130: can not copy negative amount of items");
  264. if (cpy_num == 0)
  265. return;
  266. blkh = B_BLK_HEAD(dest);
  267. nr = blkh_nr_item(blkh);
  268. free_space = blkh_free_space(blkh);
  269. /* we will insert items before 0-th or nr-th item in dest buffer. It depends of last_first parameter */
  270. dest_before = (last_first == LAST_TO_FIRST) ? 0 : nr;
  271. /* location of head of first new item */
  272. ih = B_N_PITEM_HEAD(dest, dest_before);
  273. RFALSE(blkh_free_space(blkh) < cpy_num * IH_SIZE,
  274. "vs-10140: not enough free space for headers %d (needed %d)",
  275. B_FREE_SPACE(dest), cpy_num * IH_SIZE);
  276. /* prepare space for headers */
  277. memmove(ih + cpy_num, ih, (nr - dest_before) * IH_SIZE);
  278. /* copy item headers */
  279. memcpy(ih, B_N_PITEM_HEAD(src, first), cpy_num * IH_SIZE);
  280. free_space -= (IH_SIZE * cpy_num);
  281. set_blkh_free_space(blkh, free_space);
  282. /* location of unmovable item */
  283. j = location = (dest_before == 0) ? dest->b_size : ih_location(ih - 1);
  284. for (i = dest_before; i < nr + cpy_num; i++) {
  285. location -= ih_item_len(ih + i - dest_before);
  286. put_ih_location(ih + i - dest_before, location);
  287. }
  288. /* prepare space for items */
  289. last_loc = ih_location(&(ih[nr + cpy_num - 1 - dest_before]));
  290. last_inserted_loc = ih_location(&(ih[cpy_num - 1]));
  291. /* check free space */
  292. RFALSE(free_space < j - last_inserted_loc,
  293. "vs-10150: not enough free space for items %d (needed %d)",
  294. free_space, j - last_inserted_loc);
  295. memmove(dest->b_data + last_loc,
  296. dest->b_data + last_loc + j - last_inserted_loc,
  297. last_inserted_loc - last_loc);
  298. /* copy items */
  299. memcpy(dest->b_data + last_inserted_loc,
  300. B_N_PITEM(src, (first + cpy_num - 1)), j - last_inserted_loc);
  301. /* sizes, item number */
  302. set_blkh_nr_item(blkh, nr + cpy_num);
  303. set_blkh_free_space(blkh, free_space - (j - last_inserted_loc));
  304. do_balance_mark_leaf_dirty(dest_bi->tb, dest, 0);
  305. if (dest_bi->bi_parent) {
  306. struct disk_child *t_dc;
  307. t_dc = B_N_CHILD(dest_bi->bi_parent, dest_bi->bi_position);
  308. RFALSE(dc_block_number(t_dc) != dest->b_blocknr,
  309. "vs-10160: block number in bh does not match to field in disk_child structure %lu and %lu",
  310. (long unsigned)dest->b_blocknr,
  311. (long unsigned)dc_block_number(t_dc));
  312. put_dc_size(t_dc,
  313. dc_size(t_dc) + (j - last_inserted_loc +
  314. IH_SIZE * cpy_num));
  315. do_balance_mark_internal_dirty(dest_bi->tb, dest_bi->bi_parent,
  316. 0);
  317. }
  318. }
  319. /* This function splits the (liquid) item into two items (useful when
  320. shifting part of an item into another node.) */
  321. static void leaf_item_bottle(struct buffer_info *dest_bi,
  322. struct buffer_head *src, int last_first,
  323. int item_num, int cpy_bytes)
  324. {
  325. struct buffer_head *dest = dest_bi->bi_bh;
  326. struct item_head *ih;
  327. RFALSE(cpy_bytes == -1,
  328. "vs-10170: bytes == - 1 means: do not split item");
  329. if (last_first == FIRST_TO_LAST) {
  330. /* if ( if item in position item_num in buffer SOURCE is directory item ) */
  331. if (is_direntry_le_ih(ih = B_N_PITEM_HEAD(src, item_num)))
  332. leaf_copy_dir_entries(dest_bi, src, FIRST_TO_LAST,
  333. item_num, 0, cpy_bytes);
  334. else {
  335. struct item_head n_ih;
  336. /* copy part of the body of the item number 'item_num' of SOURCE to the end of the DEST
  337. part defined by 'cpy_bytes'; create new item header; change old item_header (????);
  338. n_ih = new item_header;
  339. */
  340. memcpy(&n_ih, ih, IH_SIZE);
  341. put_ih_item_len(&n_ih, cpy_bytes);
  342. if (is_indirect_le_ih(ih)) {
  343. RFALSE(cpy_bytes == ih_item_len(ih)
  344. && get_ih_free_space(ih),
  345. "vs-10180: when whole indirect item is bottle to left neighbor, it must have free_space==0 (not %lu)",
  346. (long unsigned)get_ih_free_space(ih));
  347. set_ih_free_space(&n_ih, 0);
  348. }
  349. RFALSE(op_is_left_mergeable(&(ih->ih_key), src->b_size),
  350. "vs-10190: bad mergeability of item %h", ih);
  351. n_ih.ih_version = ih->ih_version; /* JDM Endian safe, both le */
  352. leaf_insert_into_buf(dest_bi, B_NR_ITEMS(dest), &n_ih,
  353. B_N_PITEM(src, item_num), 0);
  354. }
  355. } else {
  356. /* if ( if item in position item_num in buffer SOURCE is directory item ) */
  357. if (is_direntry_le_ih(ih = B_N_PITEM_HEAD(src, item_num)))
  358. leaf_copy_dir_entries(dest_bi, src, LAST_TO_FIRST,
  359. item_num,
  360. I_ENTRY_COUNT(ih) - cpy_bytes,
  361. cpy_bytes);
  362. else {
  363. struct item_head n_ih;
  364. /* copy part of the body of the item number 'item_num' of SOURCE to the begin of the DEST
  365. part defined by 'cpy_bytes'; create new item header;
  366. n_ih = new item_header;
  367. */
  368. memcpy(&n_ih, ih, SHORT_KEY_SIZE);
  369. n_ih.ih_version = ih->ih_version; /* JDM Endian safe, both le */
  370. if (is_direct_le_ih(ih)) {
  371. set_le_ih_k_offset(&n_ih,
  372. le_ih_k_offset(ih) +
  373. ih_item_len(ih) - cpy_bytes);
  374. set_le_ih_k_type(&n_ih, TYPE_DIRECT);
  375. set_ih_free_space(&n_ih, MAX_US_INT);
  376. } else {
  377. /* indirect item */
  378. RFALSE(!cpy_bytes && get_ih_free_space(ih),
  379. "vs-10200: ih->ih_free_space must be 0 when indirect item will be appended");
  380. set_le_ih_k_offset(&n_ih,
  381. le_ih_k_offset(ih) +
  382. (ih_item_len(ih) -
  383. cpy_bytes) / UNFM_P_SIZE *
  384. dest->b_size);
  385. set_le_ih_k_type(&n_ih, TYPE_INDIRECT);
  386. set_ih_free_space(&n_ih, get_ih_free_space(ih));
  387. }
  388. /* set item length */
  389. put_ih_item_len(&n_ih, cpy_bytes);
  390. n_ih.ih_version = ih->ih_version; /* JDM Endian safe, both le */
  391. leaf_insert_into_buf(dest_bi, 0, &n_ih,
  392. B_N_PITEM(src,
  393. item_num) +
  394. ih_item_len(ih) - cpy_bytes, 0);
  395. }
  396. }
  397. }
  398. /* If cpy_bytes equals minus one than copy cpy_num whole items from SOURCE to DEST.
  399. If cpy_bytes not equal to minus one than copy cpy_num-1 whole items from SOURCE to DEST.
  400. From last item copy cpy_num bytes for regular item and cpy_num directory entries for
  401. directory item. */
  402. static int leaf_copy_items(struct buffer_info *dest_bi, struct buffer_head *src,
  403. int last_first, int cpy_num, int cpy_bytes)
  404. {
  405. struct buffer_head *dest;
  406. int pos, i, src_nr_item, bytes;
  407. dest = dest_bi->bi_bh;
  408. RFALSE(!dest || !src, "vs-10210: !dest || !src");
  409. RFALSE(last_first != FIRST_TO_LAST && last_first != LAST_TO_FIRST,
  410. "vs-10220:last_first != FIRST_TO_LAST && last_first != LAST_TO_FIRST");
  411. RFALSE(B_NR_ITEMS(src) < cpy_num,
  412. "vs-10230: No enough items: %d, req. %d", B_NR_ITEMS(src),
  413. cpy_num);
  414. RFALSE(cpy_num < 0, "vs-10240: cpy_num < 0 (%d)", cpy_num);
  415. if (cpy_num == 0)
  416. return 0;
  417. if (last_first == FIRST_TO_LAST) {
  418. /* copy items to left */
  419. pos = 0;
  420. if (cpy_num == 1)
  421. bytes = cpy_bytes;
  422. else
  423. bytes = -1;
  424. /* copy the first item or it part or nothing to the end of the DEST (i = leaf_copy_boundary_item(DEST,SOURCE,0,bytes)) */
  425. i = leaf_copy_boundary_item(dest_bi, src, FIRST_TO_LAST, bytes);
  426. cpy_num -= i;
  427. if (cpy_num == 0)
  428. return i;
  429. pos += i;
  430. if (cpy_bytes == -1)
  431. /* copy first cpy_num items starting from position 'pos' of SOURCE to end of DEST */
  432. leaf_copy_items_entirely(dest_bi, src, FIRST_TO_LAST,
  433. pos, cpy_num);
  434. else {
  435. /* copy first cpy_num-1 items starting from position 'pos-1' of the SOURCE to the end of the DEST */
  436. leaf_copy_items_entirely(dest_bi, src, FIRST_TO_LAST,
  437. pos, cpy_num - 1);
  438. /* copy part of the item which number is cpy_num+pos-1 to the end of the DEST */
  439. leaf_item_bottle(dest_bi, src, FIRST_TO_LAST,
  440. cpy_num + pos - 1, cpy_bytes);
  441. }
  442. } else {
  443. /* copy items to right */
  444. src_nr_item = B_NR_ITEMS(src);
  445. if (cpy_num == 1)
  446. bytes = cpy_bytes;
  447. else
  448. bytes = -1;
  449. /* copy the last item or it part or nothing to the begin of the DEST (i = leaf_copy_boundary_item(DEST,SOURCE,1,bytes)); */
  450. i = leaf_copy_boundary_item(dest_bi, src, LAST_TO_FIRST, bytes);
  451. cpy_num -= i;
  452. if (cpy_num == 0)
  453. return i;
  454. pos = src_nr_item - cpy_num - i;
  455. if (cpy_bytes == -1) {
  456. /* starting from position 'pos' copy last cpy_num items of SOURCE to begin of DEST */
  457. leaf_copy_items_entirely(dest_bi, src, LAST_TO_FIRST,
  458. pos, cpy_num);
  459. } else {
  460. /* copy last cpy_num-1 items starting from position 'pos+1' of the SOURCE to the begin of the DEST; */
  461. leaf_copy_items_entirely(dest_bi, src, LAST_TO_FIRST,
  462. pos + 1, cpy_num - 1);
  463. /* copy part of the item which number is pos to the begin of the DEST */
  464. leaf_item_bottle(dest_bi, src, LAST_TO_FIRST, pos,
  465. cpy_bytes);
  466. }
  467. }
  468. return i;
  469. }
  470. /* there are types of coping: from S[0] to L[0], from S[0] to R[0],
  471. from R[0] to L[0]. for each of these we have to define parent and
  472. positions of destination and source buffers */
  473. static void leaf_define_dest_src_infos(int shift_mode, struct tree_balance *tb,
  474. struct buffer_info *dest_bi,
  475. struct buffer_info *src_bi,
  476. int *first_last,
  477. struct buffer_head *Snew)
  478. {
  479. memset(dest_bi, 0, sizeof(struct buffer_info));
  480. memset(src_bi, 0, sizeof(struct buffer_info));
  481. /* define dest, src, dest parent, dest position */
  482. switch (shift_mode) {
  483. case LEAF_FROM_S_TO_L: /* it is used in leaf_shift_left */
  484. src_bi->tb = tb;
  485. src_bi->bi_bh = PATH_PLAST_BUFFER(tb->tb_path);
  486. src_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, 0);
  487. src_bi->bi_position = PATH_H_B_ITEM_ORDER(tb->tb_path, 0); /* src->b_item_order */
  488. dest_bi->tb = tb;
  489. dest_bi->bi_bh = tb->L[0];
  490. dest_bi->bi_parent = tb->FL[0];
  491. dest_bi->bi_position = get_left_neighbor_position(tb, 0);
  492. *first_last = FIRST_TO_LAST;
  493. break;
  494. case LEAF_FROM_S_TO_R: /* it is used in leaf_shift_right */
  495. src_bi->tb = tb;
  496. src_bi->bi_bh = PATH_PLAST_BUFFER(tb->tb_path);
  497. src_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, 0);
  498. src_bi->bi_position = PATH_H_B_ITEM_ORDER(tb->tb_path, 0);
  499. dest_bi->tb = tb;
  500. dest_bi->bi_bh = tb->R[0];
  501. dest_bi->bi_parent = tb->FR[0];
  502. dest_bi->bi_position = get_right_neighbor_position(tb, 0);
  503. *first_last = LAST_TO_FIRST;
  504. break;
  505. case LEAF_FROM_R_TO_L: /* it is used in balance_leaf_when_delete */
  506. src_bi->tb = tb;
  507. src_bi->bi_bh = tb->R[0];
  508. src_bi->bi_parent = tb->FR[0];
  509. src_bi->bi_position = get_right_neighbor_position(tb, 0);
  510. dest_bi->tb = tb;
  511. dest_bi->bi_bh = tb->L[0];
  512. dest_bi->bi_parent = tb->FL[0];
  513. dest_bi->bi_position = get_left_neighbor_position(tb, 0);
  514. *first_last = FIRST_TO_LAST;
  515. break;
  516. case LEAF_FROM_L_TO_R: /* it is used in balance_leaf_when_delete */
  517. src_bi->tb = tb;
  518. src_bi->bi_bh = tb->L[0];
  519. src_bi->bi_parent = tb->FL[0];
  520. src_bi->bi_position = get_left_neighbor_position(tb, 0);
  521. dest_bi->tb = tb;
  522. dest_bi->bi_bh = tb->R[0];
  523. dest_bi->bi_parent = tb->FR[0];
  524. dest_bi->bi_position = get_right_neighbor_position(tb, 0);
  525. *first_last = LAST_TO_FIRST;
  526. break;
  527. case LEAF_FROM_S_TO_SNEW:
  528. src_bi->tb = tb;
  529. src_bi->bi_bh = PATH_PLAST_BUFFER(tb->tb_path);
  530. src_bi->bi_parent = PATH_H_PPARENT(tb->tb_path, 0);
  531. src_bi->bi_position = PATH_H_B_ITEM_ORDER(tb->tb_path, 0);
  532. dest_bi->tb = tb;
  533. dest_bi->bi_bh = Snew;
  534. dest_bi->bi_parent = NULL;
  535. dest_bi->bi_position = 0;
  536. *first_last = LAST_TO_FIRST;
  537. break;
  538. default:
  539. reiserfs_panic(NULL,
  540. "vs-10250: leaf_define_dest_src_infos: shift type is unknown (%d)",
  541. shift_mode);
  542. }
  543. RFALSE(src_bi->bi_bh == 0 || dest_bi->bi_bh == 0,
  544. "vs-10260: mode==%d, source (%p) or dest (%p) buffer is initialized incorrectly",
  545. shift_mode, src_bi->bi_bh, dest_bi->bi_bh);
  546. }
  547. /* copy mov_num items and mov_bytes of the (mov_num-1)th item to
  548. neighbor. Delete them from source */
  549. int leaf_move_items(int shift_mode, struct tree_balance *tb, int mov_num,
  550. int mov_bytes, struct buffer_head *Snew)
  551. {
  552. int ret_value;
  553. struct buffer_info dest_bi, src_bi;
  554. int first_last;
  555. leaf_define_dest_src_infos(shift_mode, tb, &dest_bi, &src_bi,
  556. &first_last, Snew);
  557. ret_value =
  558. leaf_copy_items(&dest_bi, src_bi.bi_bh, first_last, mov_num,
  559. mov_bytes);
  560. leaf_delete_items(&src_bi, first_last,
  561. (first_last ==
  562. FIRST_TO_LAST) ? 0 : (B_NR_ITEMS(src_bi.bi_bh) -
  563. mov_num), mov_num, mov_bytes);
  564. return ret_value;
  565. }
  566. /* Shift shift_num items (and shift_bytes of last shifted item if shift_bytes != -1)
  567. from S[0] to L[0] and replace the delimiting key */
  568. int leaf_shift_left(struct tree_balance *tb, int shift_num, int shift_bytes)
  569. {
  570. struct buffer_head *S0 = PATH_PLAST_BUFFER(tb->tb_path);
  571. int i;
  572. /* move shift_num (and shift_bytes bytes) items from S[0] to left neighbor L[0] */
  573. i = leaf_move_items(LEAF_FROM_S_TO_L, tb, shift_num, shift_bytes, NULL);
  574. if (shift_num) {
  575. if (B_NR_ITEMS(S0) == 0) { /* number of items in S[0] == 0 */
  576. RFALSE(shift_bytes != -1,
  577. "vs-10270: S0 is empty now, but shift_bytes != -1 (%d)",
  578. shift_bytes);
  579. #ifdef CONFIG_REISERFS_CHECK
  580. if (tb->tb_mode == M_PASTE || tb->tb_mode == M_INSERT) {
  581. print_cur_tb("vs-10275");
  582. reiserfs_panic(tb->tb_sb,
  583. "vs-10275: leaf_shift_left: balance condition corrupted (%c)",
  584. tb->tb_mode);
  585. }
  586. #endif
  587. if (PATH_H_POSITION(tb->tb_path, 1) == 0)
  588. replace_key(tb, tb->CFL[0], tb->lkey[0],
  589. PATH_H_PPARENT(tb->tb_path, 0), 0);
  590. } else {
  591. /* replace lkey in CFL[0] by 0-th key from S[0]; */
  592. replace_key(tb, tb->CFL[0], tb->lkey[0], S0, 0);
  593. RFALSE((shift_bytes != -1 &&
  594. !(is_direntry_le_ih(B_N_PITEM_HEAD(S0, 0))
  595. && !I_ENTRY_COUNT(B_N_PITEM_HEAD(S0, 0)))) &&
  596. (!op_is_left_mergeable
  597. (B_N_PKEY(S0, 0), S0->b_size)),
  598. "vs-10280: item must be mergeable");
  599. }
  600. }
  601. return i;
  602. }
  603. /* CLEANING STOPPED HERE */
  604. /* Shift shift_num (shift_bytes) items from S[0] to the right neighbor, and replace the delimiting key */
  605. int leaf_shift_right(struct tree_balance *tb, int shift_num, int shift_bytes)
  606. {
  607. // struct buffer_head * S0 = PATH_PLAST_BUFFER (tb->tb_path);
  608. int ret_value;
  609. /* move shift_num (and shift_bytes) items from S[0] to right neighbor R[0] */
  610. ret_value =
  611. leaf_move_items(LEAF_FROM_S_TO_R, tb, shift_num, shift_bytes, NULL);
  612. /* replace rkey in CFR[0] by the 0-th key from R[0] */
  613. if (shift_num) {
  614. replace_key(tb, tb->CFR[0], tb->rkey[0], tb->R[0], 0);
  615. }
  616. return ret_value;
  617. }
  618. static void leaf_delete_items_entirely(struct buffer_info *bi,
  619. int first, int del_num);
  620. /* If del_bytes == -1, starting from position 'first' delete del_num items in whole in buffer CUR.
  621. If not.
  622. If last_first == 0. Starting from position 'first' delete del_num-1 items in whole. Delete part of body of
  623. the first item. Part defined by del_bytes. Don't delete first item header
  624. If last_first == 1. Starting from position 'first+1' delete del_num-1 items in whole. Delete part of body of
  625. the last item . Part defined by del_bytes. Don't delete last item header.
  626. */
  627. void leaf_delete_items(struct buffer_info *cur_bi, int last_first,
  628. int first, int del_num, int del_bytes)
  629. {
  630. struct buffer_head *bh;
  631. int item_amount = B_NR_ITEMS(bh = cur_bi->bi_bh);
  632. RFALSE(!bh, "10155: bh is not defined");
  633. RFALSE(del_num < 0, "10160: del_num can not be < 0. del_num==%d",
  634. del_num);
  635. RFALSE(first < 0
  636. || first + del_num > item_amount,
  637. "10165: invalid number of first item to be deleted (%d) or "
  638. "no so much items (%d) to delete (only %d)", first,
  639. first + del_num, item_amount);
  640. if (del_num == 0)
  641. return;
  642. if (first == 0 && del_num == item_amount && del_bytes == -1) {
  643. make_empty_node(cur_bi);
  644. do_balance_mark_leaf_dirty(cur_bi->tb, bh, 0);
  645. return;
  646. }
  647. if (del_bytes == -1)
  648. /* delete del_num items beginning from item in position first */
  649. leaf_delete_items_entirely(cur_bi, first, del_num);
  650. else {
  651. if (last_first == FIRST_TO_LAST) {
  652. /* delete del_num-1 items beginning from item in position first */
  653. leaf_delete_items_entirely(cur_bi, first, del_num - 1);
  654. /* delete the part of the first item of the bh
  655. do not delete item header
  656. */
  657. leaf_cut_from_buffer(cur_bi, 0, 0, del_bytes);
  658. } else {
  659. struct item_head *ih;
  660. int len;
  661. /* delete del_num-1 items beginning from item in position first+1 */
  662. leaf_delete_items_entirely(cur_bi, first + 1,
  663. del_num - 1);
  664. if (is_direntry_le_ih
  665. (ih = B_N_PITEM_HEAD(bh, B_NR_ITEMS(bh) - 1)))
  666. /* the last item is directory */
  667. /* len = numbers of directory entries in this item */
  668. len = ih_entry_count(ih);
  669. else
  670. /* len = body len of item */
  671. len = ih_item_len(ih);
  672. /* delete the part of the last item of the bh
  673. do not delete item header
  674. */
  675. leaf_cut_from_buffer(cur_bi, B_NR_ITEMS(bh) - 1,
  676. len - del_bytes, del_bytes);
  677. }
  678. }
  679. }
  680. /* insert item into the leaf node in position before */
  681. void leaf_insert_into_buf(struct buffer_info *bi, int before,
  682. struct item_head *inserted_item_ih,
  683. const char *inserted_item_body, int zeros_number)
  684. {
  685. struct buffer_head *bh = bi->bi_bh;
  686. int nr, free_space;
  687. struct block_head *blkh;
  688. struct item_head *ih;
  689. int i;
  690. int last_loc, unmoved_loc;
  691. char *to;
  692. blkh = B_BLK_HEAD(bh);
  693. nr = blkh_nr_item(blkh);
  694. free_space = blkh_free_space(blkh);
  695. /* check free space */
  696. RFALSE(free_space < ih_item_len(inserted_item_ih) + IH_SIZE,
  697. "vs-10170: not enough free space in block %z, new item %h",
  698. bh, inserted_item_ih);
  699. RFALSE(zeros_number > ih_item_len(inserted_item_ih),
  700. "vs-10172: zero number == %d, item length == %d",
  701. zeros_number, ih_item_len(inserted_item_ih));
  702. /* get item new item must be inserted before */
  703. ih = B_N_PITEM_HEAD(bh, before);
  704. /* prepare space for the body of new item */
  705. last_loc = nr ? ih_location(&(ih[nr - before - 1])) : bh->b_size;
  706. unmoved_loc = before ? ih_location(ih - 1) : bh->b_size;
  707. memmove(bh->b_data + last_loc - ih_item_len(inserted_item_ih),
  708. bh->b_data + last_loc, unmoved_loc - last_loc);
  709. to = bh->b_data + unmoved_loc - ih_item_len(inserted_item_ih);
  710. memset(to, 0, zeros_number);
  711. to += zeros_number;
  712. /* copy body to prepared space */
  713. if (inserted_item_body)
  714. memmove(to, inserted_item_body,
  715. ih_item_len(inserted_item_ih) - zeros_number);
  716. else
  717. memset(to, '\0', ih_item_len(inserted_item_ih) - zeros_number);
  718. /* insert item header */
  719. memmove(ih + 1, ih, IH_SIZE * (nr - before));
  720. memmove(ih, inserted_item_ih, IH_SIZE);
  721. /* change locations */
  722. for (i = before; i < nr + 1; i++) {
  723. unmoved_loc -= ih_item_len(&(ih[i - before]));
  724. put_ih_location(&(ih[i - before]), unmoved_loc);
  725. }
  726. /* sizes, free space, item number */
  727. set_blkh_nr_item(blkh, blkh_nr_item(blkh) + 1);
  728. set_blkh_free_space(blkh,
  729. free_space - (IH_SIZE +
  730. ih_item_len(inserted_item_ih)));
  731. do_balance_mark_leaf_dirty(bi->tb, bh, 1);
  732. if (bi->bi_parent) {
  733. struct disk_child *t_dc;
  734. t_dc = B_N_CHILD(bi->bi_parent, bi->bi_position);
  735. put_dc_size(t_dc,
  736. dc_size(t_dc) + (IH_SIZE +
  737. ih_item_len(inserted_item_ih)));
  738. do_balance_mark_internal_dirty(bi->tb, bi->bi_parent, 0);
  739. }
  740. }
  741. /* paste paste_size bytes to affected_item_num-th item.
  742. When item is a directory, this only prepare space for new entries */
  743. void leaf_paste_in_buffer(struct buffer_info *bi, int affected_item_num,
  744. int pos_in_item, int paste_size,
  745. const char *body, int zeros_number)
  746. {
  747. struct buffer_head *bh = bi->bi_bh;
  748. int nr, free_space;
  749. struct block_head *blkh;
  750. struct item_head *ih;
  751. int i;
  752. int last_loc, unmoved_loc;
  753. blkh = B_BLK_HEAD(bh);
  754. nr = blkh_nr_item(blkh);
  755. free_space = blkh_free_space(blkh);
  756. /* check free space */
  757. RFALSE(free_space < paste_size,
  758. "vs-10175: not enough free space: needed %d, available %d",
  759. paste_size, free_space);
  760. #ifdef CONFIG_REISERFS_CHECK
  761. if (zeros_number > paste_size) {
  762. print_cur_tb("10177");
  763. reiserfs_panic(NULL,
  764. "vs-10177: leaf_paste_in_buffer: ero number == %d, paste_size == %d",
  765. zeros_number, paste_size);
  766. }
  767. #endif /* CONFIG_REISERFS_CHECK */
  768. /* item to be appended */
  769. ih = B_N_PITEM_HEAD(bh, affected_item_num);
  770. last_loc = ih_location(&(ih[nr - affected_item_num - 1]));
  771. unmoved_loc = affected_item_num ? ih_location(ih - 1) : bh->b_size;
  772. /* prepare space */
  773. memmove(bh->b_data + last_loc - paste_size, bh->b_data + last_loc,
  774. unmoved_loc - last_loc);
  775. /* change locations */
  776. for (i = affected_item_num; i < nr; i++)
  777. put_ih_location(&(ih[i - affected_item_num]),
  778. ih_location(&(ih[i - affected_item_num])) -
  779. paste_size);
  780. if (body) {
  781. if (!is_direntry_le_ih(ih)) {
  782. if (!pos_in_item) {
  783. /* shift data to right */
  784. memmove(bh->b_data + ih_location(ih) +
  785. paste_size,
  786. bh->b_data + ih_location(ih),
  787. ih_item_len(ih));
  788. /* paste data in the head of item */
  789. memset(bh->b_data + ih_location(ih), 0,
  790. zeros_number);
  791. memcpy(bh->b_data + ih_location(ih) +
  792. zeros_number, body,
  793. paste_size - zeros_number);
  794. } else {
  795. memset(bh->b_data + unmoved_loc - paste_size, 0,
  796. zeros_number);
  797. memcpy(bh->b_data + unmoved_loc - paste_size +
  798. zeros_number, body,
  799. paste_size - zeros_number);
  800. }
  801. }
  802. } else
  803. memset(bh->b_data + unmoved_loc - paste_size, '\0', paste_size);
  804. put_ih_item_len(ih, ih_item_len(ih) + paste_size);
  805. /* change free space */
  806. set_blkh_free_space(blkh, free_space - paste_size);
  807. do_balance_mark_leaf_dirty(bi->tb, bh, 0);
  808. if (bi->bi_parent) {
  809. struct disk_child *t_dc =
  810. B_N_CHILD(bi->bi_parent, bi->bi_position);
  811. put_dc_size(t_dc, dc_size(t_dc) + paste_size);
  812. do_balance_mark_internal_dirty(bi->tb, bi->bi_parent, 0);
  813. }
  814. }
  815. /* cuts DEL_COUNT entries beginning from FROM-th entry. Directory item
  816. does not have free space, so it moves DEHs and remaining records as
  817. necessary. Return value is size of removed part of directory item
  818. in bytes. */
  819. static int leaf_cut_entries(struct buffer_head *bh,
  820. struct item_head *ih, int from, int del_count)
  821. {
  822. char *item;
  823. struct reiserfs_de_head *deh;
  824. int prev_record_offset; /* offset of record, that is (from-1)th */
  825. char *prev_record; /* */
  826. int cut_records_len; /* length of all removed records */
  827. int i;
  828. /* make sure, that item is directory and there are enough entries to
  829. remove */
  830. RFALSE(!is_direntry_le_ih(ih), "10180: item is not directory item");
  831. RFALSE(I_ENTRY_COUNT(ih) < from + del_count,
  832. "10185: item contains not enough entries: entry_cout = %d, from = %d, to delete = %d",
  833. I_ENTRY_COUNT(ih), from, del_count);
  834. if (del_count == 0)
  835. return 0;
  836. /* first byte of item */
  837. item = bh->b_data + ih_location(ih);
  838. /* entry head array */
  839. deh = B_I_DEH(bh, ih);
  840. /* first byte of remaining entries, those are BEFORE cut entries
  841. (prev_record) and length of all removed records (cut_records_len) */
  842. prev_record_offset =
  843. (from ? deh_location(&(deh[from - 1])) : ih_item_len(ih));
  844. cut_records_len = prev_record_offset /*from_record */ -
  845. deh_location(&(deh[from + del_count - 1]));
  846. prev_record = item + prev_record_offset;
  847. /* adjust locations of remaining entries */
  848. for (i = I_ENTRY_COUNT(ih) - 1; i > from + del_count - 1; i--)
  849. put_deh_location(&(deh[i]),
  850. deh_location(&deh[i]) -
  851. (DEH_SIZE * del_count));
  852. for (i = 0; i < from; i++)
  853. put_deh_location(&(deh[i]),
  854. deh_location(&deh[i]) - (DEH_SIZE * del_count +
  855. cut_records_len));
  856. put_ih_entry_count(ih, ih_entry_count(ih) - del_count);
  857. /* shift entry head array and entries those are AFTER removed entries */
  858. memmove((char *)(deh + from),
  859. deh + from + del_count,
  860. prev_record - cut_records_len - (char *)(deh + from +
  861. del_count));
  862. /* shift records, those are BEFORE removed entries */
  863. memmove(prev_record - cut_records_len - DEH_SIZE * del_count,
  864. prev_record, item + ih_item_len(ih) - prev_record);
  865. return DEH_SIZE * del_count + cut_records_len;
  866. }
  867. /* when cut item is part of regular file
  868. pos_in_item - first byte that must be cut
  869. cut_size - number of bytes to be cut beginning from pos_in_item
  870. when cut item is part of directory
  871. pos_in_item - number of first deleted entry
  872. cut_size - count of deleted entries
  873. */
  874. void leaf_cut_from_buffer(struct buffer_info *bi, int cut_item_num,
  875. int pos_in_item, int cut_size)
  876. {
  877. int nr;
  878. struct buffer_head *bh = bi->bi_bh;
  879. struct block_head *blkh;
  880. struct item_head *ih;
  881. int last_loc, unmoved_loc;
  882. int i;
  883. blkh = B_BLK_HEAD(bh);
  884. nr = blkh_nr_item(blkh);
  885. /* item head of truncated item */
  886. ih = B_N_PITEM_HEAD(bh, cut_item_num);
  887. if (is_direntry_le_ih(ih)) {
  888. /* first cut entry () */
  889. cut_size = leaf_cut_entries(bh, ih, pos_in_item, cut_size);
  890. if (pos_in_item == 0) {
  891. /* change key */
  892. RFALSE(cut_item_num,
  893. "when 0-th enrty of item is cut, that item must be first in the node, not %d-th",
  894. cut_item_num);
  895. /* change item key by key of first entry in the item */
  896. set_le_ih_k_offset(ih, deh_offset(B_I_DEH(bh, ih)));
  897. /*memcpy (&ih->ih_key.k_offset, &(B_I_DEH (bh, ih)->deh_offset), SHORT_KEY_SIZE); */
  898. }
  899. } else {
  900. /* item is direct or indirect */
  901. RFALSE(is_statdata_le_ih(ih), "10195: item is stat data");
  902. RFALSE(pos_in_item && pos_in_item + cut_size != ih_item_len(ih),
  903. "10200: invalid offset (%lu) or trunc_size (%lu) or ih_item_len (%lu)",
  904. (long unsigned)pos_in_item, (long unsigned)cut_size,
  905. (long unsigned)ih_item_len(ih));
  906. /* shift item body to left if cut is from the head of item */
  907. if (pos_in_item == 0) {
  908. memmove(bh->b_data + ih_location(ih),
  909. bh->b_data + ih_location(ih) + cut_size,
  910. ih_item_len(ih) - cut_size);
  911. /* change key of item */
  912. if (is_direct_le_ih(ih))
  913. set_le_ih_k_offset(ih,
  914. le_ih_k_offset(ih) +
  915. cut_size);
  916. else {
  917. set_le_ih_k_offset(ih,
  918. le_ih_k_offset(ih) +
  919. (cut_size / UNFM_P_SIZE) *
  920. bh->b_size);
  921. RFALSE(ih_item_len(ih) == cut_size
  922. && get_ih_free_space(ih),
  923. "10205: invalid ih_free_space (%h)", ih);
  924. }
  925. }
  926. }
  927. /* location of the last item */
  928. last_loc = ih_location(&(ih[nr - cut_item_num - 1]));
  929. /* location of the item, which is remaining at the same place */
  930. unmoved_loc = cut_item_num ? ih_location(ih - 1) : bh->b_size;
  931. /* shift */
  932. memmove(bh->b_data + last_loc + cut_size, bh->b_data + last_loc,
  933. unmoved_loc - last_loc - cut_size);
  934. /* change item length */
  935. put_ih_item_len(ih, ih_item_len(ih) - cut_size);
  936. if (is_indirect_le_ih(ih)) {
  937. if (pos_in_item)
  938. set_ih_free_space(ih, 0);
  939. }
  940. /* change locations */
  941. for (i = cut_item_num; i < nr; i++)
  942. put_ih_location(&(ih[i - cut_item_num]),
  943. ih_location(&ih[i - cut_item_num]) + cut_size);
  944. /* size, free space */
  945. set_blkh_free_space(blkh, blkh_free_space(blkh) + cut_size);
  946. do_balance_mark_leaf_dirty(bi->tb, bh, 0);
  947. if (bi->bi_parent) {
  948. struct disk_child *t_dc;
  949. t_dc = B_N_CHILD(bi->bi_parent, bi->bi_position);
  950. put_dc_size(t_dc, dc_size(t_dc) - cut_size);
  951. do_balance_mark_internal_dirty(bi->tb, bi->bi_parent, 0);
  952. }
  953. }
  954. /* delete del_num items from buffer starting from the first'th item */
  955. static void leaf_delete_items_entirely(struct buffer_info *bi,
  956. int first, int del_num)
  957. {
  958. struct buffer_head *bh = bi->bi_bh;
  959. int nr;
  960. int i, j;
  961. int last_loc, last_removed_loc;
  962. struct block_head *blkh;
  963. struct item_head *ih;
  964. RFALSE(bh == NULL, "10210: buffer is 0");
  965. RFALSE(del_num < 0, "10215: del_num less than 0 (%d)", del_num);
  966. if (del_num == 0)
  967. return;
  968. blkh = B_BLK_HEAD(bh);
  969. nr = blkh_nr_item(blkh);
  970. RFALSE(first < 0 || first + del_num > nr,
  971. "10220: first=%d, number=%d, there is %d items", first, del_num,
  972. nr);
  973. if (first == 0 && del_num == nr) {
  974. /* this does not work */
  975. make_empty_node(bi);
  976. do_balance_mark_leaf_dirty(bi->tb, bh, 0);
  977. return;
  978. }
  979. ih = B_N_PITEM_HEAD(bh, first);
  980. /* location of unmovable item */
  981. j = (first == 0) ? bh->b_size : ih_location(ih - 1);
  982. /* delete items */
  983. last_loc = ih_location(&(ih[nr - 1 - first]));
  984. last_removed_loc = ih_location(&(ih[del_num - 1]));
  985. memmove(bh->b_data + last_loc + j - last_removed_loc,
  986. bh->b_data + last_loc, last_removed_loc - last_loc);
  987. /* delete item headers */
  988. memmove(ih, ih + del_num, (nr - first - del_num) * IH_SIZE);
  989. /* change item location */
  990. for (i = first; i < nr - del_num; i++)
  991. put_ih_location(&(ih[i - first]),
  992. ih_location(&(ih[i - first])) + (j -
  993. last_removed_loc));
  994. /* sizes, item number */
  995. set_blkh_nr_item(blkh, blkh_nr_item(blkh) - del_num);
  996. set_blkh_free_space(blkh,
  997. blkh_free_space(blkh) + (j - last_removed_loc +
  998. IH_SIZE * del_num));
  999. do_balance_mark_leaf_dirty(bi->tb, bh, 0);
  1000. if (bi->bi_parent) {
  1001. struct disk_child *t_dc =
  1002. B_N_CHILD(bi->bi_parent, bi->bi_position);
  1003. put_dc_size(t_dc,
  1004. dc_size(t_dc) - (j - last_removed_loc +
  1005. IH_SIZE * del_num));
  1006. do_balance_mark_internal_dirty(bi->tb, bi->bi_parent, 0);
  1007. }
  1008. }
  1009. /* paste new_entry_count entries (new_dehs, records) into position before to item_num-th item */
  1010. void leaf_paste_entries(struct buffer_head *bh,
  1011. int item_num,
  1012. int before,
  1013. int new_entry_count,
  1014. struct reiserfs_de_head *new_dehs,
  1015. const char *records, int paste_size)
  1016. {
  1017. struct item_head *ih;
  1018. char *item;
  1019. struct reiserfs_de_head *deh;
  1020. char *insert_point;
  1021. int i, old_entry_num;
  1022. if (new_entry_count == 0)
  1023. return;
  1024. ih = B_N_PITEM_HEAD(bh, item_num);
  1025. /* make sure, that item is directory, and there are enough records in it */
  1026. RFALSE(!is_direntry_le_ih(ih), "10225: item is not directory item");
  1027. RFALSE(I_ENTRY_COUNT(ih) < before,
  1028. "10230: there are no entry we paste entries before. entry_count = %d, before = %d",
  1029. I_ENTRY_COUNT(ih), before);
  1030. /* first byte of dest item */
  1031. item = bh->b_data + ih_location(ih);
  1032. /* entry head array */
  1033. deh = B_I_DEH(bh, ih);
  1034. /* new records will be pasted at this point */
  1035. insert_point =
  1036. item +
  1037. (before ? deh_location(&(deh[before - 1]))
  1038. : (ih_item_len(ih) - paste_size));
  1039. /* adjust locations of records that will be AFTER new records */
  1040. for (i = I_ENTRY_COUNT(ih) - 1; i >= before; i--)
  1041. put_deh_location(&(deh[i]),
  1042. deh_location(&(deh[i])) +
  1043. (DEH_SIZE * new_entry_count));
  1044. /* adjust locations of records that will be BEFORE new records */
  1045. for (i = 0; i < before; i++)
  1046. put_deh_location(&(deh[i]),
  1047. deh_location(&(deh[i])) + paste_size);
  1048. old_entry_num = I_ENTRY_COUNT(ih);
  1049. put_ih_entry_count(ih, ih_entry_count(ih) + new_entry_count);
  1050. /* prepare space for pasted records */
  1051. memmove(insert_point + paste_size, insert_point,
  1052. item + (ih_item_len(ih) - paste_size) - insert_point);
  1053. /* copy new records */
  1054. memcpy(insert_point + DEH_SIZE * new_entry_count, records,
  1055. paste_size - DEH_SIZE * new_entry_count);
  1056. /* prepare space for new entry heads */
  1057. deh += before;
  1058. memmove((char *)(deh + new_entry_count), deh,
  1059. insert_point - (char *)deh);
  1060. /* copy new entry heads */
  1061. deh = (struct reiserfs_de_head *)((char *)deh);
  1062. memcpy(deh, new_dehs, DEH_SIZE * new_entry_count);
  1063. /* set locations of new records */
  1064. for (i = 0; i < new_entry_count; i++) {
  1065. put_deh_location(&(deh[i]),
  1066. deh_location(&(deh[i])) +
  1067. (-deh_location
  1068. (&(new_dehs[new_entry_count - 1])) +
  1069. insert_point + DEH_SIZE * new_entry_count -
  1070. item));
  1071. }
  1072. /* change item key if necessary (when we paste before 0-th entry */
  1073. if (!before) {
  1074. set_le_ih_k_offset(ih, deh_offset(new_dehs));
  1075. /* memcpy (&ih->ih_key.k_offset,
  1076. &new_dehs->deh_offset, SHORT_KEY_SIZE);*/
  1077. }
  1078. #ifdef CONFIG_REISERFS_CHECK
  1079. {
  1080. int prev, next;
  1081. /* check record locations */
  1082. deh = B_I_DEH(bh, ih);
  1083. for (i = 0; i < I_ENTRY_COUNT(ih); i++) {
  1084. next =
  1085. (i <
  1086. I_ENTRY_COUNT(ih) -
  1087. 1) ? deh_location(&(deh[i + 1])) : 0;
  1088. prev = (i != 0) ? deh_location(&(deh[i - 1])) : 0;
  1089. if (prev && prev <= deh_location(&(deh[i])))
  1090. reiserfs_warning(NULL,
  1091. "vs-10240: leaf_paste_entries: directory item (%h) corrupted (prev %a, cur(%d) %a)",
  1092. ih, deh + i - 1, i, deh + i);
  1093. if (next && next >= deh_location(&(deh[i])))
  1094. reiserfs_warning(NULL,
  1095. "vs-10250: leaf_paste_entries: directory item (%h) corrupted (cur(%d) %a, next %a)",
  1096. ih, i, deh + i, deh + i + 1);
  1097. }
  1098. }
  1099. #endif
  1100. }