btree.c 62 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768176917701771177217731774177517761777177817791780178117821783178417851786178717881789179017911792179317941795179617971798179918001801180218031804180518061807180818091810181118121813181418151816181718181819182018211822182318241825182618271828182918301831183218331834183518361837183818391840184118421843184418451846184718481849185018511852185318541855185618571858185918601861186218631864186518661867186818691870187118721873187418751876187718781879188018811882188318841885188618871888188918901891189218931894189518961897189818991900190119021903190419051906190719081909191019111912191319141915191619171918191919201921192219231924192519261927192819291930193119321933193419351936193719381939194019411942194319441945194619471948194919501951195219531954195519561957195819591960196119621963196419651966196719681969197019711972197319741975197619771978197919801981198219831984198519861987198819891990199119921993199419951996199719981999200020012002200320042005200620072008200920102011201220132014201520162017201820192020202120222023202420252026202720282029203020312032203320342035203620372038203920402041204220432044204520462047204820492050205120522053205420552056205720582059206020612062206320642065206620672068206920702071207220732074207520762077207820792080208120822083208420852086208720882089209020912092209320942095209620972098209921002101210221032104210521062107210821092110211121122113211421152116211721182119212021212122212321242125212621272128212921302131213221332134213521362137213821392140214121422143214421452146214721482149215021512152215321542155215621572158215921602161216221632164216521662167216821692170217121722173217421752176217721782179218021812182218321842185218621872188218921902191219221932194219521962197219821992200220122022203220422052206220722082209221022112212221322142215221622172218221922202221222222232224222522262227222822292230223122322233223422352236223722382239224022412242224322442245224622472248224922502251225222532254225522562257225822592260226122622263226422652266226722682269227022712272227322742275227622772278227922802281228222832284228522862287228822892290229122922293229422952296229722982299230023012302230323042305230623072308230923102311231223132314231523162317231823192320232123222323232423252326232723282329233023312332233323342335233623372338233923402341234223432344234523462347234823492350235123522353235423552356235723582359236023612362236323642365236623672368236923702371237223732374237523762377237823792380238123822383238423852386238723882389239023912392239323942395239623972398239924002401240224032404240524062407240824092410
  1. // SPDX-License-Identifier: GPL-2.0+
  2. /*
  3. * btree.c - NILFS B-tree.
  4. *
  5. * Copyright (C) 2005-2008 Nippon Telegraph and Telephone Corporation.
  6. *
  7. * Written by Koji Sato.
  8. */
  9. #include <linux/slab.h>
  10. #include <linux/string.h>
  11. #include <linux/errno.h>
  12. #include <linux/pagevec.h>
  13. #include "nilfs.h"
  14. #include "page.h"
  15. #include "btnode.h"
  16. #include "btree.h"
  17. #include "alloc.h"
  18. #include "dat.h"
  19. static void __nilfs_btree_init(struct nilfs_bmap *bmap);
  20. static struct nilfs_btree_path *nilfs_btree_alloc_path(void)
  21. {
  22. struct nilfs_btree_path *path;
  23. int level = NILFS_BTREE_LEVEL_DATA;
  24. path = kmem_cache_alloc(nilfs_btree_path_cache, GFP_NOFS);
  25. if (path == NULL)
  26. goto out;
  27. for (; level < NILFS_BTREE_LEVEL_MAX; level++) {
  28. path[level].bp_bh = NULL;
  29. path[level].bp_sib_bh = NULL;
  30. path[level].bp_index = 0;
  31. path[level].bp_oldreq.bpr_ptr = NILFS_BMAP_INVALID_PTR;
  32. path[level].bp_newreq.bpr_ptr = NILFS_BMAP_INVALID_PTR;
  33. path[level].bp_op = NULL;
  34. }
  35. out:
  36. return path;
  37. }
  38. static void nilfs_btree_free_path(struct nilfs_btree_path *path)
  39. {
  40. int level = NILFS_BTREE_LEVEL_DATA;
  41. for (; level < NILFS_BTREE_LEVEL_MAX; level++)
  42. brelse(path[level].bp_bh);
  43. kmem_cache_free(nilfs_btree_path_cache, path);
  44. }
  45. /*
  46. * B-tree node operations
  47. */
  48. static int nilfs_btree_get_new_block(const struct nilfs_bmap *btree,
  49. __u64 ptr, struct buffer_head **bhp)
  50. {
  51. struct address_space *btnc = &NILFS_BMAP_I(btree)->i_btnode_cache;
  52. struct buffer_head *bh;
  53. bh = nilfs_btnode_create_block(btnc, ptr);
  54. if (!bh)
  55. return -ENOMEM;
  56. set_buffer_nilfs_volatile(bh);
  57. *bhp = bh;
  58. return 0;
  59. }
  60. static int nilfs_btree_node_get_flags(const struct nilfs_btree_node *node)
  61. {
  62. return node->bn_flags;
  63. }
  64. static void
  65. nilfs_btree_node_set_flags(struct nilfs_btree_node *node, int flags)
  66. {
  67. node->bn_flags = flags;
  68. }
  69. static int nilfs_btree_node_root(const struct nilfs_btree_node *node)
  70. {
  71. return nilfs_btree_node_get_flags(node) & NILFS_BTREE_NODE_ROOT;
  72. }
  73. static int nilfs_btree_node_get_level(const struct nilfs_btree_node *node)
  74. {
  75. return node->bn_level;
  76. }
  77. static void
  78. nilfs_btree_node_set_level(struct nilfs_btree_node *node, int level)
  79. {
  80. node->bn_level = level;
  81. }
  82. static int nilfs_btree_node_get_nchildren(const struct nilfs_btree_node *node)
  83. {
  84. return le16_to_cpu(node->bn_nchildren);
  85. }
  86. static void
  87. nilfs_btree_node_set_nchildren(struct nilfs_btree_node *node, int nchildren)
  88. {
  89. node->bn_nchildren = cpu_to_le16(nchildren);
  90. }
  91. static int nilfs_btree_node_size(const struct nilfs_bmap *btree)
  92. {
  93. return i_blocksize(btree->b_inode);
  94. }
  95. static int nilfs_btree_nchildren_per_block(const struct nilfs_bmap *btree)
  96. {
  97. return btree->b_nchildren_per_block;
  98. }
  99. static __le64 *
  100. nilfs_btree_node_dkeys(const struct nilfs_btree_node *node)
  101. {
  102. return (__le64 *)((char *)(node + 1) +
  103. (nilfs_btree_node_root(node) ?
  104. 0 : NILFS_BTREE_NODE_EXTRA_PAD_SIZE));
  105. }
  106. static __le64 *
  107. nilfs_btree_node_dptrs(const struct nilfs_btree_node *node, int ncmax)
  108. {
  109. return (__le64 *)(nilfs_btree_node_dkeys(node) + ncmax);
  110. }
  111. static __u64
  112. nilfs_btree_node_get_key(const struct nilfs_btree_node *node, int index)
  113. {
  114. return le64_to_cpu(*(nilfs_btree_node_dkeys(node) + index));
  115. }
  116. static void
  117. nilfs_btree_node_set_key(struct nilfs_btree_node *node, int index, __u64 key)
  118. {
  119. *(nilfs_btree_node_dkeys(node) + index) = cpu_to_le64(key);
  120. }
  121. static __u64
  122. nilfs_btree_node_get_ptr(const struct nilfs_btree_node *node, int index,
  123. int ncmax)
  124. {
  125. return le64_to_cpu(*(nilfs_btree_node_dptrs(node, ncmax) + index));
  126. }
  127. static void
  128. nilfs_btree_node_set_ptr(struct nilfs_btree_node *node, int index, __u64 ptr,
  129. int ncmax)
  130. {
  131. *(nilfs_btree_node_dptrs(node, ncmax) + index) = cpu_to_le64(ptr);
  132. }
  133. static void nilfs_btree_node_init(struct nilfs_btree_node *node, int flags,
  134. int level, int nchildren, int ncmax,
  135. const __u64 *keys, const __u64 *ptrs)
  136. {
  137. __le64 *dkeys;
  138. __le64 *dptrs;
  139. int i;
  140. nilfs_btree_node_set_flags(node, flags);
  141. nilfs_btree_node_set_level(node, level);
  142. nilfs_btree_node_set_nchildren(node, nchildren);
  143. dkeys = nilfs_btree_node_dkeys(node);
  144. dptrs = nilfs_btree_node_dptrs(node, ncmax);
  145. for (i = 0; i < nchildren; i++) {
  146. dkeys[i] = cpu_to_le64(keys[i]);
  147. dptrs[i] = cpu_to_le64(ptrs[i]);
  148. }
  149. }
  150. /* Assume the buffer heads corresponding to left and right are locked. */
  151. static void nilfs_btree_node_move_left(struct nilfs_btree_node *left,
  152. struct nilfs_btree_node *right,
  153. int n, int lncmax, int rncmax)
  154. {
  155. __le64 *ldkeys, *rdkeys;
  156. __le64 *ldptrs, *rdptrs;
  157. int lnchildren, rnchildren;
  158. ldkeys = nilfs_btree_node_dkeys(left);
  159. ldptrs = nilfs_btree_node_dptrs(left, lncmax);
  160. lnchildren = nilfs_btree_node_get_nchildren(left);
  161. rdkeys = nilfs_btree_node_dkeys(right);
  162. rdptrs = nilfs_btree_node_dptrs(right, rncmax);
  163. rnchildren = nilfs_btree_node_get_nchildren(right);
  164. memcpy(ldkeys + lnchildren, rdkeys, n * sizeof(*rdkeys));
  165. memcpy(ldptrs + lnchildren, rdptrs, n * sizeof(*rdptrs));
  166. memmove(rdkeys, rdkeys + n, (rnchildren - n) * sizeof(*rdkeys));
  167. memmove(rdptrs, rdptrs + n, (rnchildren - n) * sizeof(*rdptrs));
  168. lnchildren += n;
  169. rnchildren -= n;
  170. nilfs_btree_node_set_nchildren(left, lnchildren);
  171. nilfs_btree_node_set_nchildren(right, rnchildren);
  172. }
  173. /* Assume that the buffer heads corresponding to left and right are locked. */
  174. static void nilfs_btree_node_move_right(struct nilfs_btree_node *left,
  175. struct nilfs_btree_node *right,
  176. int n, int lncmax, int rncmax)
  177. {
  178. __le64 *ldkeys, *rdkeys;
  179. __le64 *ldptrs, *rdptrs;
  180. int lnchildren, rnchildren;
  181. ldkeys = nilfs_btree_node_dkeys(left);
  182. ldptrs = nilfs_btree_node_dptrs(left, lncmax);
  183. lnchildren = nilfs_btree_node_get_nchildren(left);
  184. rdkeys = nilfs_btree_node_dkeys(right);
  185. rdptrs = nilfs_btree_node_dptrs(right, rncmax);
  186. rnchildren = nilfs_btree_node_get_nchildren(right);
  187. memmove(rdkeys + n, rdkeys, rnchildren * sizeof(*rdkeys));
  188. memmove(rdptrs + n, rdptrs, rnchildren * sizeof(*rdptrs));
  189. memcpy(rdkeys, ldkeys + lnchildren - n, n * sizeof(*rdkeys));
  190. memcpy(rdptrs, ldptrs + lnchildren - n, n * sizeof(*rdptrs));
  191. lnchildren -= n;
  192. rnchildren += n;
  193. nilfs_btree_node_set_nchildren(left, lnchildren);
  194. nilfs_btree_node_set_nchildren(right, rnchildren);
  195. }
  196. /* Assume that the buffer head corresponding to node is locked. */
  197. static void nilfs_btree_node_insert(struct nilfs_btree_node *node, int index,
  198. __u64 key, __u64 ptr, int ncmax)
  199. {
  200. __le64 *dkeys;
  201. __le64 *dptrs;
  202. int nchildren;
  203. dkeys = nilfs_btree_node_dkeys(node);
  204. dptrs = nilfs_btree_node_dptrs(node, ncmax);
  205. nchildren = nilfs_btree_node_get_nchildren(node);
  206. if (index < nchildren) {
  207. memmove(dkeys + index + 1, dkeys + index,
  208. (nchildren - index) * sizeof(*dkeys));
  209. memmove(dptrs + index + 1, dptrs + index,
  210. (nchildren - index) * sizeof(*dptrs));
  211. }
  212. dkeys[index] = cpu_to_le64(key);
  213. dptrs[index] = cpu_to_le64(ptr);
  214. nchildren++;
  215. nilfs_btree_node_set_nchildren(node, nchildren);
  216. }
  217. /* Assume that the buffer head corresponding to node is locked. */
  218. static void nilfs_btree_node_delete(struct nilfs_btree_node *node, int index,
  219. __u64 *keyp, __u64 *ptrp, int ncmax)
  220. {
  221. __u64 key;
  222. __u64 ptr;
  223. __le64 *dkeys;
  224. __le64 *dptrs;
  225. int nchildren;
  226. dkeys = nilfs_btree_node_dkeys(node);
  227. dptrs = nilfs_btree_node_dptrs(node, ncmax);
  228. key = le64_to_cpu(dkeys[index]);
  229. ptr = le64_to_cpu(dptrs[index]);
  230. nchildren = nilfs_btree_node_get_nchildren(node);
  231. if (keyp != NULL)
  232. *keyp = key;
  233. if (ptrp != NULL)
  234. *ptrp = ptr;
  235. if (index < nchildren - 1) {
  236. memmove(dkeys + index, dkeys + index + 1,
  237. (nchildren - index - 1) * sizeof(*dkeys));
  238. memmove(dptrs + index, dptrs + index + 1,
  239. (nchildren - index - 1) * sizeof(*dptrs));
  240. }
  241. nchildren--;
  242. nilfs_btree_node_set_nchildren(node, nchildren);
  243. }
  244. static int nilfs_btree_node_lookup(const struct nilfs_btree_node *node,
  245. __u64 key, int *indexp)
  246. {
  247. __u64 nkey;
  248. int index, low, high, s;
  249. /* binary search */
  250. low = 0;
  251. high = nilfs_btree_node_get_nchildren(node) - 1;
  252. index = 0;
  253. s = 0;
  254. while (low <= high) {
  255. index = (low + high) / 2;
  256. nkey = nilfs_btree_node_get_key(node, index);
  257. if (nkey == key) {
  258. s = 0;
  259. goto out;
  260. } else if (nkey < key) {
  261. low = index + 1;
  262. s = -1;
  263. } else {
  264. high = index - 1;
  265. s = 1;
  266. }
  267. }
  268. /* adjust index */
  269. if (nilfs_btree_node_get_level(node) > NILFS_BTREE_LEVEL_NODE_MIN) {
  270. if (s > 0 && index > 0)
  271. index--;
  272. } else if (s < 0)
  273. index++;
  274. out:
  275. *indexp = index;
  276. return s == 0;
  277. }
  278. /**
  279. * nilfs_btree_node_broken - verify consistency of btree node
  280. * @node: btree node block to be examined
  281. * @size: node size (in bytes)
  282. * @inode: host inode of btree
  283. * @blocknr: block number
  284. *
  285. * Return Value: If node is broken, 1 is returned. Otherwise, 0 is returned.
  286. */
  287. static int nilfs_btree_node_broken(const struct nilfs_btree_node *node,
  288. size_t size, struct inode *inode,
  289. sector_t blocknr)
  290. {
  291. int level, flags, nchildren;
  292. int ret = 0;
  293. level = nilfs_btree_node_get_level(node);
  294. flags = nilfs_btree_node_get_flags(node);
  295. nchildren = nilfs_btree_node_get_nchildren(node);
  296. if (unlikely(level < NILFS_BTREE_LEVEL_NODE_MIN ||
  297. level >= NILFS_BTREE_LEVEL_MAX ||
  298. (flags & NILFS_BTREE_NODE_ROOT) ||
  299. nchildren < 0 ||
  300. nchildren > NILFS_BTREE_NODE_NCHILDREN_MAX(size))) {
  301. nilfs_crit(inode->i_sb,
  302. "bad btree node (ino=%lu, blocknr=%llu): level = %d, flags = 0x%x, nchildren = %d",
  303. inode->i_ino, (unsigned long long)blocknr, level,
  304. flags, nchildren);
  305. ret = 1;
  306. }
  307. return ret;
  308. }
  309. /**
  310. * nilfs_btree_root_broken - verify consistency of btree root node
  311. * @node: btree root node to be examined
  312. * @inode: host inode of btree
  313. *
  314. * Return Value: If node is broken, 1 is returned. Otherwise, 0 is returned.
  315. */
  316. static int nilfs_btree_root_broken(const struct nilfs_btree_node *node,
  317. struct inode *inode)
  318. {
  319. int level, flags, nchildren;
  320. int ret = 0;
  321. level = nilfs_btree_node_get_level(node);
  322. flags = nilfs_btree_node_get_flags(node);
  323. nchildren = nilfs_btree_node_get_nchildren(node);
  324. if (unlikely(level < NILFS_BTREE_LEVEL_NODE_MIN ||
  325. level >= NILFS_BTREE_LEVEL_MAX ||
  326. nchildren < 0 ||
  327. nchildren > NILFS_BTREE_ROOT_NCHILDREN_MAX)) {
  328. nilfs_crit(inode->i_sb,
  329. "bad btree root (ino=%lu): level = %d, flags = 0x%x, nchildren = %d",
  330. inode->i_ino, level, flags, nchildren);
  331. ret = 1;
  332. }
  333. return ret;
  334. }
  335. int nilfs_btree_broken_node_block(struct buffer_head *bh)
  336. {
  337. struct inode *inode;
  338. int ret;
  339. if (buffer_nilfs_checked(bh))
  340. return 0;
  341. inode = bh->b_page->mapping->host;
  342. ret = nilfs_btree_node_broken((struct nilfs_btree_node *)bh->b_data,
  343. bh->b_size, inode, bh->b_blocknr);
  344. if (likely(!ret))
  345. set_buffer_nilfs_checked(bh);
  346. return ret;
  347. }
  348. static struct nilfs_btree_node *
  349. nilfs_btree_get_root(const struct nilfs_bmap *btree)
  350. {
  351. return (struct nilfs_btree_node *)btree->b_u.u_data;
  352. }
  353. static struct nilfs_btree_node *
  354. nilfs_btree_get_nonroot_node(const struct nilfs_btree_path *path, int level)
  355. {
  356. return (struct nilfs_btree_node *)path[level].bp_bh->b_data;
  357. }
  358. static struct nilfs_btree_node *
  359. nilfs_btree_get_sib_node(const struct nilfs_btree_path *path, int level)
  360. {
  361. return (struct nilfs_btree_node *)path[level].bp_sib_bh->b_data;
  362. }
  363. static int nilfs_btree_height(const struct nilfs_bmap *btree)
  364. {
  365. return nilfs_btree_node_get_level(nilfs_btree_get_root(btree)) + 1;
  366. }
  367. static struct nilfs_btree_node *
  368. nilfs_btree_get_node(const struct nilfs_bmap *btree,
  369. const struct nilfs_btree_path *path,
  370. int level, int *ncmaxp)
  371. {
  372. struct nilfs_btree_node *node;
  373. if (level == nilfs_btree_height(btree) - 1) {
  374. node = nilfs_btree_get_root(btree);
  375. *ncmaxp = NILFS_BTREE_ROOT_NCHILDREN_MAX;
  376. } else {
  377. node = nilfs_btree_get_nonroot_node(path, level);
  378. *ncmaxp = nilfs_btree_nchildren_per_block(btree);
  379. }
  380. return node;
  381. }
  382. static int nilfs_btree_bad_node(const struct nilfs_bmap *btree,
  383. struct nilfs_btree_node *node, int level)
  384. {
  385. if (unlikely(nilfs_btree_node_get_level(node) != level)) {
  386. dump_stack();
  387. nilfs_crit(btree->b_inode->i_sb,
  388. "btree level mismatch (ino=%lu): %d != %d",
  389. btree->b_inode->i_ino,
  390. nilfs_btree_node_get_level(node), level);
  391. return 1;
  392. }
  393. return 0;
  394. }
  395. struct nilfs_btree_readahead_info {
  396. struct nilfs_btree_node *node; /* parent node */
  397. int max_ra_blocks; /* max nof blocks to read ahead */
  398. int index; /* current index on the parent node */
  399. int ncmax; /* nof children in the parent node */
  400. };
  401. static int __nilfs_btree_get_block(const struct nilfs_bmap *btree, __u64 ptr,
  402. struct buffer_head **bhp,
  403. const struct nilfs_btree_readahead_info *ra)
  404. {
  405. struct address_space *btnc = &NILFS_BMAP_I(btree)->i_btnode_cache;
  406. struct buffer_head *bh, *ra_bh;
  407. sector_t submit_ptr = 0;
  408. int ret;
  409. ret = nilfs_btnode_submit_block(btnc, ptr, 0, REQ_OP_READ, 0, &bh,
  410. &submit_ptr);
  411. if (ret) {
  412. if (ret != -EEXIST)
  413. return ret;
  414. goto out_check;
  415. }
  416. if (ra) {
  417. int i, n;
  418. __u64 ptr2;
  419. /* read ahead sibling nodes */
  420. for (n = ra->max_ra_blocks, i = ra->index + 1;
  421. n > 0 && i < ra->ncmax; n--, i++) {
  422. ptr2 = nilfs_btree_node_get_ptr(ra->node, i, ra->ncmax);
  423. ret = nilfs_btnode_submit_block(btnc, ptr2, 0,
  424. REQ_OP_READ, REQ_RAHEAD,
  425. &ra_bh, &submit_ptr);
  426. if (likely(!ret || ret == -EEXIST))
  427. brelse(ra_bh);
  428. else if (ret != -EBUSY)
  429. break;
  430. if (!buffer_locked(bh))
  431. goto out_no_wait;
  432. }
  433. }
  434. wait_on_buffer(bh);
  435. out_no_wait:
  436. if (!buffer_uptodate(bh)) {
  437. nilfs_err(btree->b_inode->i_sb,
  438. "I/O error reading b-tree node block (ino=%lu, blocknr=%llu)",
  439. btree->b_inode->i_ino, (unsigned long long)ptr);
  440. brelse(bh);
  441. return -EIO;
  442. }
  443. out_check:
  444. if (nilfs_btree_broken_node_block(bh)) {
  445. clear_buffer_uptodate(bh);
  446. brelse(bh);
  447. return -EINVAL;
  448. }
  449. *bhp = bh;
  450. return 0;
  451. }
  452. static int nilfs_btree_get_block(const struct nilfs_bmap *btree, __u64 ptr,
  453. struct buffer_head **bhp)
  454. {
  455. return __nilfs_btree_get_block(btree, ptr, bhp, NULL);
  456. }
  457. static int nilfs_btree_do_lookup(const struct nilfs_bmap *btree,
  458. struct nilfs_btree_path *path,
  459. __u64 key, __u64 *ptrp, int minlevel,
  460. int readahead)
  461. {
  462. struct nilfs_btree_node *node;
  463. struct nilfs_btree_readahead_info p, *ra;
  464. __u64 ptr;
  465. int level, index, found, ncmax, ret;
  466. node = nilfs_btree_get_root(btree);
  467. level = nilfs_btree_node_get_level(node);
  468. if (level < minlevel || nilfs_btree_node_get_nchildren(node) <= 0)
  469. return -ENOENT;
  470. found = nilfs_btree_node_lookup(node, key, &index);
  471. ptr = nilfs_btree_node_get_ptr(node, index,
  472. NILFS_BTREE_ROOT_NCHILDREN_MAX);
  473. path[level].bp_bh = NULL;
  474. path[level].bp_index = index;
  475. ncmax = nilfs_btree_nchildren_per_block(btree);
  476. while (--level >= minlevel) {
  477. ra = NULL;
  478. if (level == NILFS_BTREE_LEVEL_NODE_MIN && readahead) {
  479. p.node = nilfs_btree_get_node(btree, path, level + 1,
  480. &p.ncmax);
  481. p.index = index;
  482. p.max_ra_blocks = 7;
  483. ra = &p;
  484. }
  485. ret = __nilfs_btree_get_block(btree, ptr, &path[level].bp_bh,
  486. ra);
  487. if (ret < 0)
  488. return ret;
  489. node = nilfs_btree_get_nonroot_node(path, level);
  490. if (nilfs_btree_bad_node(btree, node, level))
  491. return -EINVAL;
  492. if (!found)
  493. found = nilfs_btree_node_lookup(node, key, &index);
  494. else
  495. index = 0;
  496. if (index < ncmax) {
  497. ptr = nilfs_btree_node_get_ptr(node, index, ncmax);
  498. } else {
  499. WARN_ON(found || level != NILFS_BTREE_LEVEL_NODE_MIN);
  500. /* insert */
  501. ptr = NILFS_BMAP_INVALID_PTR;
  502. }
  503. path[level].bp_index = index;
  504. }
  505. if (!found)
  506. return -ENOENT;
  507. if (ptrp != NULL)
  508. *ptrp = ptr;
  509. return 0;
  510. }
  511. static int nilfs_btree_do_lookup_last(const struct nilfs_bmap *btree,
  512. struct nilfs_btree_path *path,
  513. __u64 *keyp, __u64 *ptrp)
  514. {
  515. struct nilfs_btree_node *node;
  516. __u64 ptr;
  517. int index, level, ncmax, ret;
  518. node = nilfs_btree_get_root(btree);
  519. index = nilfs_btree_node_get_nchildren(node) - 1;
  520. if (index < 0)
  521. return -ENOENT;
  522. level = nilfs_btree_node_get_level(node);
  523. ptr = nilfs_btree_node_get_ptr(node, index,
  524. NILFS_BTREE_ROOT_NCHILDREN_MAX);
  525. path[level].bp_bh = NULL;
  526. path[level].bp_index = index;
  527. ncmax = nilfs_btree_nchildren_per_block(btree);
  528. for (level--; level > 0; level--) {
  529. ret = nilfs_btree_get_block(btree, ptr, &path[level].bp_bh);
  530. if (ret < 0)
  531. return ret;
  532. node = nilfs_btree_get_nonroot_node(path, level);
  533. if (nilfs_btree_bad_node(btree, node, level))
  534. return -EINVAL;
  535. index = nilfs_btree_node_get_nchildren(node) - 1;
  536. ptr = nilfs_btree_node_get_ptr(node, index, ncmax);
  537. path[level].bp_index = index;
  538. }
  539. if (keyp != NULL)
  540. *keyp = nilfs_btree_node_get_key(node, index);
  541. if (ptrp != NULL)
  542. *ptrp = ptr;
  543. return 0;
  544. }
  545. /**
  546. * nilfs_btree_get_next_key - get next valid key from btree path array
  547. * @btree: bmap struct of btree
  548. * @path: array of nilfs_btree_path struct
  549. * @minlevel: start level
  550. * @nextkey: place to store the next valid key
  551. *
  552. * Return Value: If a next key was found, 0 is returned. Otherwise,
  553. * -ENOENT is returned.
  554. */
  555. static int nilfs_btree_get_next_key(const struct nilfs_bmap *btree,
  556. const struct nilfs_btree_path *path,
  557. int minlevel, __u64 *nextkey)
  558. {
  559. struct nilfs_btree_node *node;
  560. int maxlevel = nilfs_btree_height(btree) - 1;
  561. int index, next_adj, level;
  562. /* Next index is already set to bp_index for leaf nodes. */
  563. next_adj = 0;
  564. for (level = minlevel; level <= maxlevel; level++) {
  565. if (level == maxlevel)
  566. node = nilfs_btree_get_root(btree);
  567. else
  568. node = nilfs_btree_get_nonroot_node(path, level);
  569. index = path[level].bp_index + next_adj;
  570. if (index < nilfs_btree_node_get_nchildren(node)) {
  571. /* Next key is in this node */
  572. *nextkey = nilfs_btree_node_get_key(node, index);
  573. return 0;
  574. }
  575. /* For non-leaf nodes, next index is stored at bp_index + 1. */
  576. next_adj = 1;
  577. }
  578. return -ENOENT;
  579. }
  580. static int nilfs_btree_lookup(const struct nilfs_bmap *btree,
  581. __u64 key, int level, __u64 *ptrp)
  582. {
  583. struct nilfs_btree_path *path;
  584. int ret;
  585. path = nilfs_btree_alloc_path();
  586. if (path == NULL)
  587. return -ENOMEM;
  588. ret = nilfs_btree_do_lookup(btree, path, key, ptrp, level, 0);
  589. nilfs_btree_free_path(path);
  590. return ret;
  591. }
  592. static int nilfs_btree_lookup_contig(const struct nilfs_bmap *btree,
  593. __u64 key, __u64 *ptrp,
  594. unsigned int maxblocks)
  595. {
  596. struct nilfs_btree_path *path;
  597. struct nilfs_btree_node *node;
  598. struct inode *dat = NULL;
  599. __u64 ptr, ptr2;
  600. sector_t blocknr;
  601. int level = NILFS_BTREE_LEVEL_NODE_MIN;
  602. int ret, cnt, index, maxlevel, ncmax;
  603. struct nilfs_btree_readahead_info p;
  604. path = nilfs_btree_alloc_path();
  605. if (path == NULL)
  606. return -ENOMEM;
  607. ret = nilfs_btree_do_lookup(btree, path, key, &ptr, level, 1);
  608. if (ret < 0)
  609. goto out;
  610. if (NILFS_BMAP_USE_VBN(btree)) {
  611. dat = nilfs_bmap_get_dat(btree);
  612. ret = nilfs_dat_translate(dat, ptr, &blocknr);
  613. if (ret < 0)
  614. goto out;
  615. ptr = blocknr;
  616. }
  617. cnt = 1;
  618. if (cnt == maxblocks)
  619. goto end;
  620. maxlevel = nilfs_btree_height(btree) - 1;
  621. node = nilfs_btree_get_node(btree, path, level, &ncmax);
  622. index = path[level].bp_index + 1;
  623. for (;;) {
  624. while (index < nilfs_btree_node_get_nchildren(node)) {
  625. if (nilfs_btree_node_get_key(node, index) !=
  626. key + cnt)
  627. goto end;
  628. ptr2 = nilfs_btree_node_get_ptr(node, index, ncmax);
  629. if (dat) {
  630. ret = nilfs_dat_translate(dat, ptr2, &blocknr);
  631. if (ret < 0)
  632. goto out;
  633. ptr2 = blocknr;
  634. }
  635. if (ptr2 != ptr + cnt || ++cnt == maxblocks)
  636. goto end;
  637. index++;
  638. continue;
  639. }
  640. if (level == maxlevel)
  641. break;
  642. /* look-up right sibling node */
  643. p.node = nilfs_btree_get_node(btree, path, level + 1, &p.ncmax);
  644. p.index = path[level + 1].bp_index + 1;
  645. p.max_ra_blocks = 7;
  646. if (p.index >= nilfs_btree_node_get_nchildren(p.node) ||
  647. nilfs_btree_node_get_key(p.node, p.index) != key + cnt)
  648. break;
  649. ptr2 = nilfs_btree_node_get_ptr(p.node, p.index, p.ncmax);
  650. path[level + 1].bp_index = p.index;
  651. brelse(path[level].bp_bh);
  652. path[level].bp_bh = NULL;
  653. ret = __nilfs_btree_get_block(btree, ptr2, &path[level].bp_bh,
  654. &p);
  655. if (ret < 0)
  656. goto out;
  657. node = nilfs_btree_get_nonroot_node(path, level);
  658. ncmax = nilfs_btree_nchildren_per_block(btree);
  659. index = 0;
  660. path[level].bp_index = index;
  661. }
  662. end:
  663. *ptrp = ptr;
  664. ret = cnt;
  665. out:
  666. nilfs_btree_free_path(path);
  667. return ret;
  668. }
  669. static void nilfs_btree_promote_key(struct nilfs_bmap *btree,
  670. struct nilfs_btree_path *path,
  671. int level, __u64 key)
  672. {
  673. if (level < nilfs_btree_height(btree) - 1) {
  674. do {
  675. nilfs_btree_node_set_key(
  676. nilfs_btree_get_nonroot_node(path, level),
  677. path[level].bp_index, key);
  678. if (!buffer_dirty(path[level].bp_bh))
  679. mark_buffer_dirty(path[level].bp_bh);
  680. } while ((path[level].bp_index == 0) &&
  681. (++level < nilfs_btree_height(btree) - 1));
  682. }
  683. /* root */
  684. if (level == nilfs_btree_height(btree) - 1) {
  685. nilfs_btree_node_set_key(nilfs_btree_get_root(btree),
  686. path[level].bp_index, key);
  687. }
  688. }
  689. static void nilfs_btree_do_insert(struct nilfs_bmap *btree,
  690. struct nilfs_btree_path *path,
  691. int level, __u64 *keyp, __u64 *ptrp)
  692. {
  693. struct nilfs_btree_node *node;
  694. int ncblk;
  695. if (level < nilfs_btree_height(btree) - 1) {
  696. node = nilfs_btree_get_nonroot_node(path, level);
  697. ncblk = nilfs_btree_nchildren_per_block(btree);
  698. nilfs_btree_node_insert(node, path[level].bp_index,
  699. *keyp, *ptrp, ncblk);
  700. if (!buffer_dirty(path[level].bp_bh))
  701. mark_buffer_dirty(path[level].bp_bh);
  702. if (path[level].bp_index == 0)
  703. nilfs_btree_promote_key(btree, path, level + 1,
  704. nilfs_btree_node_get_key(node,
  705. 0));
  706. } else {
  707. node = nilfs_btree_get_root(btree);
  708. nilfs_btree_node_insert(node, path[level].bp_index,
  709. *keyp, *ptrp,
  710. NILFS_BTREE_ROOT_NCHILDREN_MAX);
  711. }
  712. }
  713. static void nilfs_btree_carry_left(struct nilfs_bmap *btree,
  714. struct nilfs_btree_path *path,
  715. int level, __u64 *keyp, __u64 *ptrp)
  716. {
  717. struct nilfs_btree_node *node, *left;
  718. int nchildren, lnchildren, n, move, ncblk;
  719. node = nilfs_btree_get_nonroot_node(path, level);
  720. left = nilfs_btree_get_sib_node(path, level);
  721. nchildren = nilfs_btree_node_get_nchildren(node);
  722. lnchildren = nilfs_btree_node_get_nchildren(left);
  723. ncblk = nilfs_btree_nchildren_per_block(btree);
  724. move = 0;
  725. n = (nchildren + lnchildren + 1) / 2 - lnchildren;
  726. if (n > path[level].bp_index) {
  727. /* move insert point */
  728. n--;
  729. move = 1;
  730. }
  731. nilfs_btree_node_move_left(left, node, n, ncblk, ncblk);
  732. if (!buffer_dirty(path[level].bp_bh))
  733. mark_buffer_dirty(path[level].bp_bh);
  734. if (!buffer_dirty(path[level].bp_sib_bh))
  735. mark_buffer_dirty(path[level].bp_sib_bh);
  736. nilfs_btree_promote_key(btree, path, level + 1,
  737. nilfs_btree_node_get_key(node, 0));
  738. if (move) {
  739. brelse(path[level].bp_bh);
  740. path[level].bp_bh = path[level].bp_sib_bh;
  741. path[level].bp_sib_bh = NULL;
  742. path[level].bp_index += lnchildren;
  743. path[level + 1].bp_index--;
  744. } else {
  745. brelse(path[level].bp_sib_bh);
  746. path[level].bp_sib_bh = NULL;
  747. path[level].bp_index -= n;
  748. }
  749. nilfs_btree_do_insert(btree, path, level, keyp, ptrp);
  750. }
  751. static void nilfs_btree_carry_right(struct nilfs_bmap *btree,
  752. struct nilfs_btree_path *path,
  753. int level, __u64 *keyp, __u64 *ptrp)
  754. {
  755. struct nilfs_btree_node *node, *right;
  756. int nchildren, rnchildren, n, move, ncblk;
  757. node = nilfs_btree_get_nonroot_node(path, level);
  758. right = nilfs_btree_get_sib_node(path, level);
  759. nchildren = nilfs_btree_node_get_nchildren(node);
  760. rnchildren = nilfs_btree_node_get_nchildren(right);
  761. ncblk = nilfs_btree_nchildren_per_block(btree);
  762. move = 0;
  763. n = (nchildren + rnchildren + 1) / 2 - rnchildren;
  764. if (n > nchildren - path[level].bp_index) {
  765. /* move insert point */
  766. n--;
  767. move = 1;
  768. }
  769. nilfs_btree_node_move_right(node, right, n, ncblk, ncblk);
  770. if (!buffer_dirty(path[level].bp_bh))
  771. mark_buffer_dirty(path[level].bp_bh);
  772. if (!buffer_dirty(path[level].bp_sib_bh))
  773. mark_buffer_dirty(path[level].bp_sib_bh);
  774. path[level + 1].bp_index++;
  775. nilfs_btree_promote_key(btree, path, level + 1,
  776. nilfs_btree_node_get_key(right, 0));
  777. path[level + 1].bp_index--;
  778. if (move) {
  779. brelse(path[level].bp_bh);
  780. path[level].bp_bh = path[level].bp_sib_bh;
  781. path[level].bp_sib_bh = NULL;
  782. path[level].bp_index -= nilfs_btree_node_get_nchildren(node);
  783. path[level + 1].bp_index++;
  784. } else {
  785. brelse(path[level].bp_sib_bh);
  786. path[level].bp_sib_bh = NULL;
  787. }
  788. nilfs_btree_do_insert(btree, path, level, keyp, ptrp);
  789. }
  790. static void nilfs_btree_split(struct nilfs_bmap *btree,
  791. struct nilfs_btree_path *path,
  792. int level, __u64 *keyp, __u64 *ptrp)
  793. {
  794. struct nilfs_btree_node *node, *right;
  795. int nchildren, n, move, ncblk;
  796. node = nilfs_btree_get_nonroot_node(path, level);
  797. right = nilfs_btree_get_sib_node(path, level);
  798. nchildren = nilfs_btree_node_get_nchildren(node);
  799. ncblk = nilfs_btree_nchildren_per_block(btree);
  800. move = 0;
  801. n = (nchildren + 1) / 2;
  802. if (n > nchildren - path[level].bp_index) {
  803. n--;
  804. move = 1;
  805. }
  806. nilfs_btree_node_move_right(node, right, n, ncblk, ncblk);
  807. if (!buffer_dirty(path[level].bp_bh))
  808. mark_buffer_dirty(path[level].bp_bh);
  809. if (!buffer_dirty(path[level].bp_sib_bh))
  810. mark_buffer_dirty(path[level].bp_sib_bh);
  811. if (move) {
  812. path[level].bp_index -= nilfs_btree_node_get_nchildren(node);
  813. nilfs_btree_node_insert(right, path[level].bp_index,
  814. *keyp, *ptrp, ncblk);
  815. *keyp = nilfs_btree_node_get_key(right, 0);
  816. *ptrp = path[level].bp_newreq.bpr_ptr;
  817. brelse(path[level].bp_bh);
  818. path[level].bp_bh = path[level].bp_sib_bh;
  819. path[level].bp_sib_bh = NULL;
  820. } else {
  821. nilfs_btree_do_insert(btree, path, level, keyp, ptrp);
  822. *keyp = nilfs_btree_node_get_key(right, 0);
  823. *ptrp = path[level].bp_newreq.bpr_ptr;
  824. brelse(path[level].bp_sib_bh);
  825. path[level].bp_sib_bh = NULL;
  826. }
  827. path[level + 1].bp_index++;
  828. }
  829. static void nilfs_btree_grow(struct nilfs_bmap *btree,
  830. struct nilfs_btree_path *path,
  831. int level, __u64 *keyp, __u64 *ptrp)
  832. {
  833. struct nilfs_btree_node *root, *child;
  834. int n, ncblk;
  835. root = nilfs_btree_get_root(btree);
  836. child = nilfs_btree_get_sib_node(path, level);
  837. ncblk = nilfs_btree_nchildren_per_block(btree);
  838. n = nilfs_btree_node_get_nchildren(root);
  839. nilfs_btree_node_move_right(root, child, n,
  840. NILFS_BTREE_ROOT_NCHILDREN_MAX, ncblk);
  841. nilfs_btree_node_set_level(root, level + 1);
  842. if (!buffer_dirty(path[level].bp_sib_bh))
  843. mark_buffer_dirty(path[level].bp_sib_bh);
  844. path[level].bp_bh = path[level].bp_sib_bh;
  845. path[level].bp_sib_bh = NULL;
  846. nilfs_btree_do_insert(btree, path, level, keyp, ptrp);
  847. *keyp = nilfs_btree_node_get_key(child, 0);
  848. *ptrp = path[level].bp_newreq.bpr_ptr;
  849. }
  850. static __u64 nilfs_btree_find_near(const struct nilfs_bmap *btree,
  851. const struct nilfs_btree_path *path)
  852. {
  853. struct nilfs_btree_node *node;
  854. int level, ncmax;
  855. if (path == NULL)
  856. return NILFS_BMAP_INVALID_PTR;
  857. /* left sibling */
  858. level = NILFS_BTREE_LEVEL_NODE_MIN;
  859. if (path[level].bp_index > 0) {
  860. node = nilfs_btree_get_node(btree, path, level, &ncmax);
  861. return nilfs_btree_node_get_ptr(node,
  862. path[level].bp_index - 1,
  863. ncmax);
  864. }
  865. /* parent */
  866. level = NILFS_BTREE_LEVEL_NODE_MIN + 1;
  867. if (level <= nilfs_btree_height(btree) - 1) {
  868. node = nilfs_btree_get_node(btree, path, level, &ncmax);
  869. return nilfs_btree_node_get_ptr(node, path[level].bp_index,
  870. ncmax);
  871. }
  872. return NILFS_BMAP_INVALID_PTR;
  873. }
  874. static __u64 nilfs_btree_find_target_v(const struct nilfs_bmap *btree,
  875. const struct nilfs_btree_path *path,
  876. __u64 key)
  877. {
  878. __u64 ptr;
  879. ptr = nilfs_bmap_find_target_seq(btree, key);
  880. if (ptr != NILFS_BMAP_INVALID_PTR)
  881. /* sequential access */
  882. return ptr;
  883. ptr = nilfs_btree_find_near(btree, path);
  884. if (ptr != NILFS_BMAP_INVALID_PTR)
  885. /* near */
  886. return ptr;
  887. /* block group */
  888. return nilfs_bmap_find_target_in_group(btree);
  889. }
  890. static int nilfs_btree_prepare_insert(struct nilfs_bmap *btree,
  891. struct nilfs_btree_path *path,
  892. int *levelp, __u64 key, __u64 ptr,
  893. struct nilfs_bmap_stats *stats)
  894. {
  895. struct buffer_head *bh;
  896. struct nilfs_btree_node *node, *parent, *sib;
  897. __u64 sibptr;
  898. int pindex, level, ncmax, ncblk, ret;
  899. struct inode *dat = NULL;
  900. stats->bs_nblocks = 0;
  901. level = NILFS_BTREE_LEVEL_DATA;
  902. /* allocate a new ptr for data block */
  903. if (NILFS_BMAP_USE_VBN(btree)) {
  904. path[level].bp_newreq.bpr_ptr =
  905. nilfs_btree_find_target_v(btree, path, key);
  906. dat = nilfs_bmap_get_dat(btree);
  907. }
  908. ret = nilfs_bmap_prepare_alloc_ptr(btree, &path[level].bp_newreq, dat);
  909. if (ret < 0)
  910. goto err_out_data;
  911. ncblk = nilfs_btree_nchildren_per_block(btree);
  912. for (level = NILFS_BTREE_LEVEL_NODE_MIN;
  913. level < nilfs_btree_height(btree) - 1;
  914. level++) {
  915. node = nilfs_btree_get_nonroot_node(path, level);
  916. if (nilfs_btree_node_get_nchildren(node) < ncblk) {
  917. path[level].bp_op = nilfs_btree_do_insert;
  918. stats->bs_nblocks++;
  919. goto out;
  920. }
  921. parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
  922. pindex = path[level + 1].bp_index;
  923. /* left sibling */
  924. if (pindex > 0) {
  925. sibptr = nilfs_btree_node_get_ptr(parent, pindex - 1,
  926. ncmax);
  927. ret = nilfs_btree_get_block(btree, sibptr, &bh);
  928. if (ret < 0)
  929. goto err_out_child_node;
  930. sib = (struct nilfs_btree_node *)bh->b_data;
  931. if (nilfs_btree_node_get_nchildren(sib) < ncblk) {
  932. path[level].bp_sib_bh = bh;
  933. path[level].bp_op = nilfs_btree_carry_left;
  934. stats->bs_nblocks++;
  935. goto out;
  936. } else {
  937. brelse(bh);
  938. }
  939. }
  940. /* right sibling */
  941. if (pindex < nilfs_btree_node_get_nchildren(parent) - 1) {
  942. sibptr = nilfs_btree_node_get_ptr(parent, pindex + 1,
  943. ncmax);
  944. ret = nilfs_btree_get_block(btree, sibptr, &bh);
  945. if (ret < 0)
  946. goto err_out_child_node;
  947. sib = (struct nilfs_btree_node *)bh->b_data;
  948. if (nilfs_btree_node_get_nchildren(sib) < ncblk) {
  949. path[level].bp_sib_bh = bh;
  950. path[level].bp_op = nilfs_btree_carry_right;
  951. stats->bs_nblocks++;
  952. goto out;
  953. } else {
  954. brelse(bh);
  955. }
  956. }
  957. /* split */
  958. path[level].bp_newreq.bpr_ptr =
  959. path[level - 1].bp_newreq.bpr_ptr + 1;
  960. ret = nilfs_bmap_prepare_alloc_ptr(btree,
  961. &path[level].bp_newreq, dat);
  962. if (ret < 0)
  963. goto err_out_child_node;
  964. ret = nilfs_btree_get_new_block(btree,
  965. path[level].bp_newreq.bpr_ptr,
  966. &bh);
  967. if (ret < 0)
  968. goto err_out_curr_node;
  969. stats->bs_nblocks++;
  970. sib = (struct nilfs_btree_node *)bh->b_data;
  971. nilfs_btree_node_init(sib, 0, level, 0, ncblk, NULL, NULL);
  972. path[level].bp_sib_bh = bh;
  973. path[level].bp_op = nilfs_btree_split;
  974. }
  975. /* root */
  976. node = nilfs_btree_get_root(btree);
  977. if (nilfs_btree_node_get_nchildren(node) <
  978. NILFS_BTREE_ROOT_NCHILDREN_MAX) {
  979. path[level].bp_op = nilfs_btree_do_insert;
  980. stats->bs_nblocks++;
  981. goto out;
  982. }
  983. /* grow */
  984. path[level].bp_newreq.bpr_ptr = path[level - 1].bp_newreq.bpr_ptr + 1;
  985. ret = nilfs_bmap_prepare_alloc_ptr(btree, &path[level].bp_newreq, dat);
  986. if (ret < 0)
  987. goto err_out_child_node;
  988. ret = nilfs_btree_get_new_block(btree, path[level].bp_newreq.bpr_ptr,
  989. &bh);
  990. if (ret < 0)
  991. goto err_out_curr_node;
  992. nilfs_btree_node_init((struct nilfs_btree_node *)bh->b_data,
  993. 0, level, 0, ncblk, NULL, NULL);
  994. path[level].bp_sib_bh = bh;
  995. path[level].bp_op = nilfs_btree_grow;
  996. level++;
  997. path[level].bp_op = nilfs_btree_do_insert;
  998. /* a newly-created node block and a data block are added */
  999. stats->bs_nblocks += 2;
  1000. /* success */
  1001. out:
  1002. *levelp = level;
  1003. return ret;
  1004. /* error */
  1005. err_out_curr_node:
  1006. nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat);
  1007. err_out_child_node:
  1008. for (level--; level > NILFS_BTREE_LEVEL_DATA; level--) {
  1009. nilfs_btnode_delete(path[level].bp_sib_bh);
  1010. nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat);
  1011. }
  1012. nilfs_bmap_abort_alloc_ptr(btree, &path[level].bp_newreq, dat);
  1013. err_out_data:
  1014. *levelp = level;
  1015. stats->bs_nblocks = 0;
  1016. return ret;
  1017. }
  1018. static void nilfs_btree_commit_insert(struct nilfs_bmap *btree,
  1019. struct nilfs_btree_path *path,
  1020. int maxlevel, __u64 key, __u64 ptr)
  1021. {
  1022. struct inode *dat = NULL;
  1023. int level;
  1024. set_buffer_nilfs_volatile((struct buffer_head *)((unsigned long)ptr));
  1025. ptr = path[NILFS_BTREE_LEVEL_DATA].bp_newreq.bpr_ptr;
  1026. if (NILFS_BMAP_USE_VBN(btree)) {
  1027. nilfs_bmap_set_target_v(btree, key, ptr);
  1028. dat = nilfs_bmap_get_dat(btree);
  1029. }
  1030. for (level = NILFS_BTREE_LEVEL_NODE_MIN; level <= maxlevel; level++) {
  1031. nilfs_bmap_commit_alloc_ptr(btree,
  1032. &path[level - 1].bp_newreq, dat);
  1033. path[level].bp_op(btree, path, level, &key, &ptr);
  1034. }
  1035. if (!nilfs_bmap_dirty(btree))
  1036. nilfs_bmap_set_dirty(btree);
  1037. }
  1038. static int nilfs_btree_insert(struct nilfs_bmap *btree, __u64 key, __u64 ptr)
  1039. {
  1040. struct nilfs_btree_path *path;
  1041. struct nilfs_bmap_stats stats;
  1042. int level, ret;
  1043. path = nilfs_btree_alloc_path();
  1044. if (path == NULL)
  1045. return -ENOMEM;
  1046. ret = nilfs_btree_do_lookup(btree, path, key, NULL,
  1047. NILFS_BTREE_LEVEL_NODE_MIN, 0);
  1048. if (ret != -ENOENT) {
  1049. if (ret == 0)
  1050. ret = -EEXIST;
  1051. goto out;
  1052. }
  1053. ret = nilfs_btree_prepare_insert(btree, path, &level, key, ptr, &stats);
  1054. if (ret < 0)
  1055. goto out;
  1056. nilfs_btree_commit_insert(btree, path, level, key, ptr);
  1057. nilfs_inode_add_blocks(btree->b_inode, stats.bs_nblocks);
  1058. out:
  1059. nilfs_btree_free_path(path);
  1060. return ret;
  1061. }
  1062. static void nilfs_btree_do_delete(struct nilfs_bmap *btree,
  1063. struct nilfs_btree_path *path,
  1064. int level, __u64 *keyp, __u64 *ptrp)
  1065. {
  1066. struct nilfs_btree_node *node;
  1067. int ncblk;
  1068. if (level < nilfs_btree_height(btree) - 1) {
  1069. node = nilfs_btree_get_nonroot_node(path, level);
  1070. ncblk = nilfs_btree_nchildren_per_block(btree);
  1071. nilfs_btree_node_delete(node, path[level].bp_index,
  1072. keyp, ptrp, ncblk);
  1073. if (!buffer_dirty(path[level].bp_bh))
  1074. mark_buffer_dirty(path[level].bp_bh);
  1075. if (path[level].bp_index == 0)
  1076. nilfs_btree_promote_key(btree, path, level + 1,
  1077. nilfs_btree_node_get_key(node, 0));
  1078. } else {
  1079. node = nilfs_btree_get_root(btree);
  1080. nilfs_btree_node_delete(node, path[level].bp_index,
  1081. keyp, ptrp,
  1082. NILFS_BTREE_ROOT_NCHILDREN_MAX);
  1083. }
  1084. }
  1085. static void nilfs_btree_borrow_left(struct nilfs_bmap *btree,
  1086. struct nilfs_btree_path *path,
  1087. int level, __u64 *keyp, __u64 *ptrp)
  1088. {
  1089. struct nilfs_btree_node *node, *left;
  1090. int nchildren, lnchildren, n, ncblk;
  1091. nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
  1092. node = nilfs_btree_get_nonroot_node(path, level);
  1093. left = nilfs_btree_get_sib_node(path, level);
  1094. nchildren = nilfs_btree_node_get_nchildren(node);
  1095. lnchildren = nilfs_btree_node_get_nchildren(left);
  1096. ncblk = nilfs_btree_nchildren_per_block(btree);
  1097. n = (nchildren + lnchildren) / 2 - nchildren;
  1098. nilfs_btree_node_move_right(left, node, n, ncblk, ncblk);
  1099. if (!buffer_dirty(path[level].bp_bh))
  1100. mark_buffer_dirty(path[level].bp_bh);
  1101. if (!buffer_dirty(path[level].bp_sib_bh))
  1102. mark_buffer_dirty(path[level].bp_sib_bh);
  1103. nilfs_btree_promote_key(btree, path, level + 1,
  1104. nilfs_btree_node_get_key(node, 0));
  1105. brelse(path[level].bp_sib_bh);
  1106. path[level].bp_sib_bh = NULL;
  1107. path[level].bp_index += n;
  1108. }
  1109. static void nilfs_btree_borrow_right(struct nilfs_bmap *btree,
  1110. struct nilfs_btree_path *path,
  1111. int level, __u64 *keyp, __u64 *ptrp)
  1112. {
  1113. struct nilfs_btree_node *node, *right;
  1114. int nchildren, rnchildren, n, ncblk;
  1115. nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
  1116. node = nilfs_btree_get_nonroot_node(path, level);
  1117. right = nilfs_btree_get_sib_node(path, level);
  1118. nchildren = nilfs_btree_node_get_nchildren(node);
  1119. rnchildren = nilfs_btree_node_get_nchildren(right);
  1120. ncblk = nilfs_btree_nchildren_per_block(btree);
  1121. n = (nchildren + rnchildren) / 2 - nchildren;
  1122. nilfs_btree_node_move_left(node, right, n, ncblk, ncblk);
  1123. if (!buffer_dirty(path[level].bp_bh))
  1124. mark_buffer_dirty(path[level].bp_bh);
  1125. if (!buffer_dirty(path[level].bp_sib_bh))
  1126. mark_buffer_dirty(path[level].bp_sib_bh);
  1127. path[level + 1].bp_index++;
  1128. nilfs_btree_promote_key(btree, path, level + 1,
  1129. nilfs_btree_node_get_key(right, 0));
  1130. path[level + 1].bp_index--;
  1131. brelse(path[level].bp_sib_bh);
  1132. path[level].bp_sib_bh = NULL;
  1133. }
  1134. static void nilfs_btree_concat_left(struct nilfs_bmap *btree,
  1135. struct nilfs_btree_path *path,
  1136. int level, __u64 *keyp, __u64 *ptrp)
  1137. {
  1138. struct nilfs_btree_node *node, *left;
  1139. int n, ncblk;
  1140. nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
  1141. node = nilfs_btree_get_nonroot_node(path, level);
  1142. left = nilfs_btree_get_sib_node(path, level);
  1143. ncblk = nilfs_btree_nchildren_per_block(btree);
  1144. n = nilfs_btree_node_get_nchildren(node);
  1145. nilfs_btree_node_move_left(left, node, n, ncblk, ncblk);
  1146. if (!buffer_dirty(path[level].bp_sib_bh))
  1147. mark_buffer_dirty(path[level].bp_sib_bh);
  1148. nilfs_btnode_delete(path[level].bp_bh);
  1149. path[level].bp_bh = path[level].bp_sib_bh;
  1150. path[level].bp_sib_bh = NULL;
  1151. path[level].bp_index += nilfs_btree_node_get_nchildren(left);
  1152. }
  1153. static void nilfs_btree_concat_right(struct nilfs_bmap *btree,
  1154. struct nilfs_btree_path *path,
  1155. int level, __u64 *keyp, __u64 *ptrp)
  1156. {
  1157. struct nilfs_btree_node *node, *right;
  1158. int n, ncblk;
  1159. nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
  1160. node = nilfs_btree_get_nonroot_node(path, level);
  1161. right = nilfs_btree_get_sib_node(path, level);
  1162. ncblk = nilfs_btree_nchildren_per_block(btree);
  1163. n = nilfs_btree_node_get_nchildren(right);
  1164. nilfs_btree_node_move_left(node, right, n, ncblk, ncblk);
  1165. if (!buffer_dirty(path[level].bp_bh))
  1166. mark_buffer_dirty(path[level].bp_bh);
  1167. nilfs_btnode_delete(path[level].bp_sib_bh);
  1168. path[level].bp_sib_bh = NULL;
  1169. path[level + 1].bp_index++;
  1170. }
  1171. static void nilfs_btree_shrink(struct nilfs_bmap *btree,
  1172. struct nilfs_btree_path *path,
  1173. int level, __u64 *keyp, __u64 *ptrp)
  1174. {
  1175. struct nilfs_btree_node *root, *child;
  1176. int n, ncblk;
  1177. nilfs_btree_do_delete(btree, path, level, keyp, ptrp);
  1178. root = nilfs_btree_get_root(btree);
  1179. child = nilfs_btree_get_nonroot_node(path, level);
  1180. ncblk = nilfs_btree_nchildren_per_block(btree);
  1181. nilfs_btree_node_delete(root, 0, NULL, NULL,
  1182. NILFS_BTREE_ROOT_NCHILDREN_MAX);
  1183. nilfs_btree_node_set_level(root, level);
  1184. n = nilfs_btree_node_get_nchildren(child);
  1185. nilfs_btree_node_move_left(root, child, n,
  1186. NILFS_BTREE_ROOT_NCHILDREN_MAX, ncblk);
  1187. nilfs_btnode_delete(path[level].bp_bh);
  1188. path[level].bp_bh = NULL;
  1189. }
  1190. static void nilfs_btree_nop(struct nilfs_bmap *btree,
  1191. struct nilfs_btree_path *path,
  1192. int level, __u64 *keyp, __u64 *ptrp)
  1193. {
  1194. }
  1195. static int nilfs_btree_prepare_delete(struct nilfs_bmap *btree,
  1196. struct nilfs_btree_path *path,
  1197. int *levelp,
  1198. struct nilfs_bmap_stats *stats,
  1199. struct inode *dat)
  1200. {
  1201. struct buffer_head *bh;
  1202. struct nilfs_btree_node *node, *parent, *sib;
  1203. __u64 sibptr;
  1204. int pindex, dindex, level, ncmin, ncmax, ncblk, ret;
  1205. ret = 0;
  1206. stats->bs_nblocks = 0;
  1207. ncmin = NILFS_BTREE_NODE_NCHILDREN_MIN(nilfs_btree_node_size(btree));
  1208. ncblk = nilfs_btree_nchildren_per_block(btree);
  1209. for (level = NILFS_BTREE_LEVEL_NODE_MIN, dindex = path[level].bp_index;
  1210. level < nilfs_btree_height(btree) - 1;
  1211. level++) {
  1212. node = nilfs_btree_get_nonroot_node(path, level);
  1213. path[level].bp_oldreq.bpr_ptr =
  1214. nilfs_btree_node_get_ptr(node, dindex, ncblk);
  1215. ret = nilfs_bmap_prepare_end_ptr(btree,
  1216. &path[level].bp_oldreq, dat);
  1217. if (ret < 0)
  1218. goto err_out_child_node;
  1219. if (nilfs_btree_node_get_nchildren(node) > ncmin) {
  1220. path[level].bp_op = nilfs_btree_do_delete;
  1221. stats->bs_nblocks++;
  1222. goto out;
  1223. }
  1224. parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
  1225. pindex = path[level + 1].bp_index;
  1226. dindex = pindex;
  1227. if (pindex > 0) {
  1228. /* left sibling */
  1229. sibptr = nilfs_btree_node_get_ptr(parent, pindex - 1,
  1230. ncmax);
  1231. ret = nilfs_btree_get_block(btree, sibptr, &bh);
  1232. if (ret < 0)
  1233. goto err_out_curr_node;
  1234. sib = (struct nilfs_btree_node *)bh->b_data;
  1235. if (nilfs_btree_node_get_nchildren(sib) > ncmin) {
  1236. path[level].bp_sib_bh = bh;
  1237. path[level].bp_op = nilfs_btree_borrow_left;
  1238. stats->bs_nblocks++;
  1239. goto out;
  1240. } else {
  1241. path[level].bp_sib_bh = bh;
  1242. path[level].bp_op = nilfs_btree_concat_left;
  1243. stats->bs_nblocks++;
  1244. /* continue; */
  1245. }
  1246. } else if (pindex <
  1247. nilfs_btree_node_get_nchildren(parent) - 1) {
  1248. /* right sibling */
  1249. sibptr = nilfs_btree_node_get_ptr(parent, pindex + 1,
  1250. ncmax);
  1251. ret = nilfs_btree_get_block(btree, sibptr, &bh);
  1252. if (ret < 0)
  1253. goto err_out_curr_node;
  1254. sib = (struct nilfs_btree_node *)bh->b_data;
  1255. if (nilfs_btree_node_get_nchildren(sib) > ncmin) {
  1256. path[level].bp_sib_bh = bh;
  1257. path[level].bp_op = nilfs_btree_borrow_right;
  1258. stats->bs_nblocks++;
  1259. goto out;
  1260. } else {
  1261. path[level].bp_sib_bh = bh;
  1262. path[level].bp_op = nilfs_btree_concat_right;
  1263. stats->bs_nblocks++;
  1264. /*
  1265. * When merging right sibling node
  1266. * into the current node, pointer to
  1267. * the right sibling node must be
  1268. * terminated instead. The adjustment
  1269. * below is required for that.
  1270. */
  1271. dindex = pindex + 1;
  1272. /* continue; */
  1273. }
  1274. } else {
  1275. /* no siblings */
  1276. /* the only child of the root node */
  1277. WARN_ON(level != nilfs_btree_height(btree) - 2);
  1278. if (nilfs_btree_node_get_nchildren(node) - 1 <=
  1279. NILFS_BTREE_ROOT_NCHILDREN_MAX) {
  1280. path[level].bp_op = nilfs_btree_shrink;
  1281. stats->bs_nblocks += 2;
  1282. level++;
  1283. path[level].bp_op = nilfs_btree_nop;
  1284. goto shrink_root_child;
  1285. } else {
  1286. path[level].bp_op = nilfs_btree_do_delete;
  1287. stats->bs_nblocks++;
  1288. goto out;
  1289. }
  1290. }
  1291. }
  1292. /* child of the root node is deleted */
  1293. path[level].bp_op = nilfs_btree_do_delete;
  1294. stats->bs_nblocks++;
  1295. shrink_root_child:
  1296. node = nilfs_btree_get_root(btree);
  1297. path[level].bp_oldreq.bpr_ptr =
  1298. nilfs_btree_node_get_ptr(node, dindex,
  1299. NILFS_BTREE_ROOT_NCHILDREN_MAX);
  1300. ret = nilfs_bmap_prepare_end_ptr(btree, &path[level].bp_oldreq, dat);
  1301. if (ret < 0)
  1302. goto err_out_child_node;
  1303. /* success */
  1304. out:
  1305. *levelp = level;
  1306. return ret;
  1307. /* error */
  1308. err_out_curr_node:
  1309. nilfs_bmap_abort_end_ptr(btree, &path[level].bp_oldreq, dat);
  1310. err_out_child_node:
  1311. for (level--; level >= NILFS_BTREE_LEVEL_NODE_MIN; level--) {
  1312. brelse(path[level].bp_sib_bh);
  1313. nilfs_bmap_abort_end_ptr(btree, &path[level].bp_oldreq, dat);
  1314. }
  1315. *levelp = level;
  1316. stats->bs_nblocks = 0;
  1317. return ret;
  1318. }
  1319. static void nilfs_btree_commit_delete(struct nilfs_bmap *btree,
  1320. struct nilfs_btree_path *path,
  1321. int maxlevel, struct inode *dat)
  1322. {
  1323. int level;
  1324. for (level = NILFS_BTREE_LEVEL_NODE_MIN; level <= maxlevel; level++) {
  1325. nilfs_bmap_commit_end_ptr(btree, &path[level].bp_oldreq, dat);
  1326. path[level].bp_op(btree, path, level, NULL, NULL);
  1327. }
  1328. if (!nilfs_bmap_dirty(btree))
  1329. nilfs_bmap_set_dirty(btree);
  1330. }
  1331. static int nilfs_btree_delete(struct nilfs_bmap *btree, __u64 key)
  1332. {
  1333. struct nilfs_btree_path *path;
  1334. struct nilfs_bmap_stats stats;
  1335. struct inode *dat;
  1336. int level, ret;
  1337. path = nilfs_btree_alloc_path();
  1338. if (path == NULL)
  1339. return -ENOMEM;
  1340. ret = nilfs_btree_do_lookup(btree, path, key, NULL,
  1341. NILFS_BTREE_LEVEL_NODE_MIN, 0);
  1342. if (ret < 0)
  1343. goto out;
  1344. dat = NILFS_BMAP_USE_VBN(btree) ? nilfs_bmap_get_dat(btree) : NULL;
  1345. ret = nilfs_btree_prepare_delete(btree, path, &level, &stats, dat);
  1346. if (ret < 0)
  1347. goto out;
  1348. nilfs_btree_commit_delete(btree, path, level, dat);
  1349. nilfs_inode_sub_blocks(btree->b_inode, stats.bs_nblocks);
  1350. out:
  1351. nilfs_btree_free_path(path);
  1352. return ret;
  1353. }
  1354. static int nilfs_btree_seek_key(const struct nilfs_bmap *btree, __u64 start,
  1355. __u64 *keyp)
  1356. {
  1357. struct nilfs_btree_path *path;
  1358. const int minlevel = NILFS_BTREE_LEVEL_NODE_MIN;
  1359. int ret;
  1360. path = nilfs_btree_alloc_path();
  1361. if (!path)
  1362. return -ENOMEM;
  1363. ret = nilfs_btree_do_lookup(btree, path, start, NULL, minlevel, 0);
  1364. if (!ret)
  1365. *keyp = start;
  1366. else if (ret == -ENOENT)
  1367. ret = nilfs_btree_get_next_key(btree, path, minlevel, keyp);
  1368. nilfs_btree_free_path(path);
  1369. return ret;
  1370. }
  1371. static int nilfs_btree_last_key(const struct nilfs_bmap *btree, __u64 *keyp)
  1372. {
  1373. struct nilfs_btree_path *path;
  1374. int ret;
  1375. path = nilfs_btree_alloc_path();
  1376. if (path == NULL)
  1377. return -ENOMEM;
  1378. ret = nilfs_btree_do_lookup_last(btree, path, keyp, NULL);
  1379. nilfs_btree_free_path(path);
  1380. return ret;
  1381. }
  1382. static int nilfs_btree_check_delete(struct nilfs_bmap *btree, __u64 key)
  1383. {
  1384. struct buffer_head *bh;
  1385. struct nilfs_btree_node *root, *node;
  1386. __u64 maxkey, nextmaxkey;
  1387. __u64 ptr;
  1388. int nchildren, ret;
  1389. root = nilfs_btree_get_root(btree);
  1390. switch (nilfs_btree_height(btree)) {
  1391. case 2:
  1392. bh = NULL;
  1393. node = root;
  1394. break;
  1395. case 3:
  1396. nchildren = nilfs_btree_node_get_nchildren(root);
  1397. if (nchildren > 1)
  1398. return 0;
  1399. ptr = nilfs_btree_node_get_ptr(root, nchildren - 1,
  1400. NILFS_BTREE_ROOT_NCHILDREN_MAX);
  1401. ret = nilfs_btree_get_block(btree, ptr, &bh);
  1402. if (ret < 0)
  1403. return ret;
  1404. node = (struct nilfs_btree_node *)bh->b_data;
  1405. break;
  1406. default:
  1407. return 0;
  1408. }
  1409. nchildren = nilfs_btree_node_get_nchildren(node);
  1410. maxkey = nilfs_btree_node_get_key(node, nchildren - 1);
  1411. nextmaxkey = (nchildren > 1) ?
  1412. nilfs_btree_node_get_key(node, nchildren - 2) : 0;
  1413. if (bh != NULL)
  1414. brelse(bh);
  1415. return (maxkey == key) && (nextmaxkey < NILFS_BMAP_LARGE_LOW);
  1416. }
  1417. static int nilfs_btree_gather_data(struct nilfs_bmap *btree,
  1418. __u64 *keys, __u64 *ptrs, int nitems)
  1419. {
  1420. struct buffer_head *bh;
  1421. struct nilfs_btree_node *node, *root;
  1422. __le64 *dkeys;
  1423. __le64 *dptrs;
  1424. __u64 ptr;
  1425. int nchildren, ncmax, i, ret;
  1426. root = nilfs_btree_get_root(btree);
  1427. switch (nilfs_btree_height(btree)) {
  1428. case 2:
  1429. bh = NULL;
  1430. node = root;
  1431. ncmax = NILFS_BTREE_ROOT_NCHILDREN_MAX;
  1432. break;
  1433. case 3:
  1434. nchildren = nilfs_btree_node_get_nchildren(root);
  1435. WARN_ON(nchildren > 1);
  1436. ptr = nilfs_btree_node_get_ptr(root, nchildren - 1,
  1437. NILFS_BTREE_ROOT_NCHILDREN_MAX);
  1438. ret = nilfs_btree_get_block(btree, ptr, &bh);
  1439. if (ret < 0)
  1440. return ret;
  1441. node = (struct nilfs_btree_node *)bh->b_data;
  1442. ncmax = nilfs_btree_nchildren_per_block(btree);
  1443. break;
  1444. default:
  1445. node = NULL;
  1446. return -EINVAL;
  1447. }
  1448. nchildren = nilfs_btree_node_get_nchildren(node);
  1449. if (nchildren < nitems)
  1450. nitems = nchildren;
  1451. dkeys = nilfs_btree_node_dkeys(node);
  1452. dptrs = nilfs_btree_node_dptrs(node, ncmax);
  1453. for (i = 0; i < nitems; i++) {
  1454. keys[i] = le64_to_cpu(dkeys[i]);
  1455. ptrs[i] = le64_to_cpu(dptrs[i]);
  1456. }
  1457. if (bh != NULL)
  1458. brelse(bh);
  1459. return nitems;
  1460. }
  1461. static int
  1462. nilfs_btree_prepare_convert_and_insert(struct nilfs_bmap *btree, __u64 key,
  1463. union nilfs_bmap_ptr_req *dreq,
  1464. union nilfs_bmap_ptr_req *nreq,
  1465. struct buffer_head **bhp,
  1466. struct nilfs_bmap_stats *stats)
  1467. {
  1468. struct buffer_head *bh;
  1469. struct inode *dat = NULL;
  1470. int ret;
  1471. stats->bs_nblocks = 0;
  1472. /* for data */
  1473. /* cannot find near ptr */
  1474. if (NILFS_BMAP_USE_VBN(btree)) {
  1475. dreq->bpr_ptr = nilfs_btree_find_target_v(btree, NULL, key);
  1476. dat = nilfs_bmap_get_dat(btree);
  1477. }
  1478. ret = nilfs_bmap_prepare_alloc_ptr(btree, dreq, dat);
  1479. if (ret < 0)
  1480. return ret;
  1481. *bhp = NULL;
  1482. stats->bs_nblocks++;
  1483. if (nreq != NULL) {
  1484. nreq->bpr_ptr = dreq->bpr_ptr + 1;
  1485. ret = nilfs_bmap_prepare_alloc_ptr(btree, nreq, dat);
  1486. if (ret < 0)
  1487. goto err_out_dreq;
  1488. ret = nilfs_btree_get_new_block(btree, nreq->bpr_ptr, &bh);
  1489. if (ret < 0)
  1490. goto err_out_nreq;
  1491. *bhp = bh;
  1492. stats->bs_nblocks++;
  1493. }
  1494. /* success */
  1495. return 0;
  1496. /* error */
  1497. err_out_nreq:
  1498. nilfs_bmap_abort_alloc_ptr(btree, nreq, dat);
  1499. err_out_dreq:
  1500. nilfs_bmap_abort_alloc_ptr(btree, dreq, dat);
  1501. stats->bs_nblocks = 0;
  1502. return ret;
  1503. }
  1504. static void
  1505. nilfs_btree_commit_convert_and_insert(struct nilfs_bmap *btree,
  1506. __u64 key, __u64 ptr,
  1507. const __u64 *keys, const __u64 *ptrs,
  1508. int n,
  1509. union nilfs_bmap_ptr_req *dreq,
  1510. union nilfs_bmap_ptr_req *nreq,
  1511. struct buffer_head *bh)
  1512. {
  1513. struct nilfs_btree_node *node;
  1514. struct inode *dat;
  1515. __u64 tmpptr;
  1516. int ncblk;
  1517. /* free resources */
  1518. if (btree->b_ops->bop_clear != NULL)
  1519. btree->b_ops->bop_clear(btree);
  1520. /* ptr must be a pointer to a buffer head. */
  1521. set_buffer_nilfs_volatile((struct buffer_head *)((unsigned long)ptr));
  1522. /* convert and insert */
  1523. dat = NILFS_BMAP_USE_VBN(btree) ? nilfs_bmap_get_dat(btree) : NULL;
  1524. __nilfs_btree_init(btree);
  1525. if (nreq != NULL) {
  1526. nilfs_bmap_commit_alloc_ptr(btree, dreq, dat);
  1527. nilfs_bmap_commit_alloc_ptr(btree, nreq, dat);
  1528. /* create child node at level 1 */
  1529. node = (struct nilfs_btree_node *)bh->b_data;
  1530. ncblk = nilfs_btree_nchildren_per_block(btree);
  1531. nilfs_btree_node_init(node, 0, 1, n, ncblk, keys, ptrs);
  1532. nilfs_btree_node_insert(node, n, key, dreq->bpr_ptr, ncblk);
  1533. if (!buffer_dirty(bh))
  1534. mark_buffer_dirty(bh);
  1535. if (!nilfs_bmap_dirty(btree))
  1536. nilfs_bmap_set_dirty(btree);
  1537. brelse(bh);
  1538. /* create root node at level 2 */
  1539. node = nilfs_btree_get_root(btree);
  1540. tmpptr = nreq->bpr_ptr;
  1541. nilfs_btree_node_init(node, NILFS_BTREE_NODE_ROOT, 2, 1,
  1542. NILFS_BTREE_ROOT_NCHILDREN_MAX,
  1543. &keys[0], &tmpptr);
  1544. } else {
  1545. nilfs_bmap_commit_alloc_ptr(btree, dreq, dat);
  1546. /* create root node at level 1 */
  1547. node = nilfs_btree_get_root(btree);
  1548. nilfs_btree_node_init(node, NILFS_BTREE_NODE_ROOT, 1, n,
  1549. NILFS_BTREE_ROOT_NCHILDREN_MAX,
  1550. keys, ptrs);
  1551. nilfs_btree_node_insert(node, n, key, dreq->bpr_ptr,
  1552. NILFS_BTREE_ROOT_NCHILDREN_MAX);
  1553. if (!nilfs_bmap_dirty(btree))
  1554. nilfs_bmap_set_dirty(btree);
  1555. }
  1556. if (NILFS_BMAP_USE_VBN(btree))
  1557. nilfs_bmap_set_target_v(btree, key, dreq->bpr_ptr);
  1558. }
  1559. /**
  1560. * nilfs_btree_convert_and_insert -
  1561. * @bmap:
  1562. * @key:
  1563. * @ptr:
  1564. * @keys:
  1565. * @ptrs:
  1566. * @n:
  1567. */
  1568. int nilfs_btree_convert_and_insert(struct nilfs_bmap *btree,
  1569. __u64 key, __u64 ptr,
  1570. const __u64 *keys, const __u64 *ptrs, int n)
  1571. {
  1572. struct buffer_head *bh = NULL;
  1573. union nilfs_bmap_ptr_req dreq, nreq, *di, *ni;
  1574. struct nilfs_bmap_stats stats;
  1575. int ret;
  1576. if (n + 1 <= NILFS_BTREE_ROOT_NCHILDREN_MAX) {
  1577. di = &dreq;
  1578. ni = NULL;
  1579. } else if ((n + 1) <= NILFS_BTREE_NODE_NCHILDREN_MAX(
  1580. nilfs_btree_node_size(btree))) {
  1581. di = &dreq;
  1582. ni = &nreq;
  1583. } else {
  1584. di = NULL;
  1585. ni = NULL;
  1586. BUG();
  1587. }
  1588. ret = nilfs_btree_prepare_convert_and_insert(btree, key, di, ni, &bh,
  1589. &stats);
  1590. if (ret < 0)
  1591. return ret;
  1592. nilfs_btree_commit_convert_and_insert(btree, key, ptr, keys, ptrs, n,
  1593. di, ni, bh);
  1594. nilfs_inode_add_blocks(btree->b_inode, stats.bs_nblocks);
  1595. return 0;
  1596. }
  1597. static int nilfs_btree_propagate_p(struct nilfs_bmap *btree,
  1598. struct nilfs_btree_path *path,
  1599. int level,
  1600. struct buffer_head *bh)
  1601. {
  1602. while ((++level < nilfs_btree_height(btree) - 1) &&
  1603. !buffer_dirty(path[level].bp_bh))
  1604. mark_buffer_dirty(path[level].bp_bh);
  1605. return 0;
  1606. }
  1607. static int nilfs_btree_prepare_update_v(struct nilfs_bmap *btree,
  1608. struct nilfs_btree_path *path,
  1609. int level, struct inode *dat)
  1610. {
  1611. struct nilfs_btree_node *parent;
  1612. int ncmax, ret;
  1613. parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
  1614. path[level].bp_oldreq.bpr_ptr =
  1615. nilfs_btree_node_get_ptr(parent, path[level + 1].bp_index,
  1616. ncmax);
  1617. path[level].bp_newreq.bpr_ptr = path[level].bp_oldreq.bpr_ptr + 1;
  1618. ret = nilfs_dat_prepare_update(dat, &path[level].bp_oldreq.bpr_req,
  1619. &path[level].bp_newreq.bpr_req);
  1620. if (ret < 0)
  1621. return ret;
  1622. if (buffer_nilfs_node(path[level].bp_bh)) {
  1623. path[level].bp_ctxt.oldkey = path[level].bp_oldreq.bpr_ptr;
  1624. path[level].bp_ctxt.newkey = path[level].bp_newreq.bpr_ptr;
  1625. path[level].bp_ctxt.bh = path[level].bp_bh;
  1626. ret = nilfs_btnode_prepare_change_key(
  1627. &NILFS_BMAP_I(btree)->i_btnode_cache,
  1628. &path[level].bp_ctxt);
  1629. if (ret < 0) {
  1630. nilfs_dat_abort_update(dat,
  1631. &path[level].bp_oldreq.bpr_req,
  1632. &path[level].bp_newreq.bpr_req);
  1633. return ret;
  1634. }
  1635. }
  1636. return 0;
  1637. }
  1638. static void nilfs_btree_commit_update_v(struct nilfs_bmap *btree,
  1639. struct nilfs_btree_path *path,
  1640. int level, struct inode *dat)
  1641. {
  1642. struct nilfs_btree_node *parent;
  1643. int ncmax;
  1644. nilfs_dat_commit_update(dat, &path[level].bp_oldreq.bpr_req,
  1645. &path[level].bp_newreq.bpr_req,
  1646. btree->b_ptr_type == NILFS_BMAP_PTR_VS);
  1647. if (buffer_nilfs_node(path[level].bp_bh)) {
  1648. nilfs_btnode_commit_change_key(
  1649. &NILFS_BMAP_I(btree)->i_btnode_cache,
  1650. &path[level].bp_ctxt);
  1651. path[level].bp_bh = path[level].bp_ctxt.bh;
  1652. }
  1653. set_buffer_nilfs_volatile(path[level].bp_bh);
  1654. parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
  1655. nilfs_btree_node_set_ptr(parent, path[level + 1].bp_index,
  1656. path[level].bp_newreq.bpr_ptr, ncmax);
  1657. }
  1658. static void nilfs_btree_abort_update_v(struct nilfs_bmap *btree,
  1659. struct nilfs_btree_path *path,
  1660. int level, struct inode *dat)
  1661. {
  1662. nilfs_dat_abort_update(dat, &path[level].bp_oldreq.bpr_req,
  1663. &path[level].bp_newreq.bpr_req);
  1664. if (buffer_nilfs_node(path[level].bp_bh))
  1665. nilfs_btnode_abort_change_key(
  1666. &NILFS_BMAP_I(btree)->i_btnode_cache,
  1667. &path[level].bp_ctxt);
  1668. }
  1669. static int nilfs_btree_prepare_propagate_v(struct nilfs_bmap *btree,
  1670. struct nilfs_btree_path *path,
  1671. int minlevel, int *maxlevelp,
  1672. struct inode *dat)
  1673. {
  1674. int level, ret;
  1675. level = minlevel;
  1676. if (!buffer_nilfs_volatile(path[level].bp_bh)) {
  1677. ret = nilfs_btree_prepare_update_v(btree, path, level, dat);
  1678. if (ret < 0)
  1679. return ret;
  1680. }
  1681. while ((++level < nilfs_btree_height(btree) - 1) &&
  1682. !buffer_dirty(path[level].bp_bh)) {
  1683. WARN_ON(buffer_nilfs_volatile(path[level].bp_bh));
  1684. ret = nilfs_btree_prepare_update_v(btree, path, level, dat);
  1685. if (ret < 0)
  1686. goto out;
  1687. }
  1688. /* success */
  1689. *maxlevelp = level - 1;
  1690. return 0;
  1691. /* error */
  1692. out:
  1693. while (--level > minlevel)
  1694. nilfs_btree_abort_update_v(btree, path, level, dat);
  1695. if (!buffer_nilfs_volatile(path[level].bp_bh))
  1696. nilfs_btree_abort_update_v(btree, path, level, dat);
  1697. return ret;
  1698. }
  1699. static void nilfs_btree_commit_propagate_v(struct nilfs_bmap *btree,
  1700. struct nilfs_btree_path *path,
  1701. int minlevel, int maxlevel,
  1702. struct buffer_head *bh,
  1703. struct inode *dat)
  1704. {
  1705. int level;
  1706. if (!buffer_nilfs_volatile(path[minlevel].bp_bh))
  1707. nilfs_btree_commit_update_v(btree, path, minlevel, dat);
  1708. for (level = minlevel + 1; level <= maxlevel; level++)
  1709. nilfs_btree_commit_update_v(btree, path, level, dat);
  1710. }
  1711. static int nilfs_btree_propagate_v(struct nilfs_bmap *btree,
  1712. struct nilfs_btree_path *path,
  1713. int level, struct buffer_head *bh)
  1714. {
  1715. int maxlevel = 0, ret;
  1716. struct nilfs_btree_node *parent;
  1717. struct inode *dat = nilfs_bmap_get_dat(btree);
  1718. __u64 ptr;
  1719. int ncmax;
  1720. get_bh(bh);
  1721. path[level].bp_bh = bh;
  1722. ret = nilfs_btree_prepare_propagate_v(btree, path, level, &maxlevel,
  1723. dat);
  1724. if (ret < 0)
  1725. goto out;
  1726. if (buffer_nilfs_volatile(path[level].bp_bh)) {
  1727. parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
  1728. ptr = nilfs_btree_node_get_ptr(parent,
  1729. path[level + 1].bp_index,
  1730. ncmax);
  1731. ret = nilfs_dat_mark_dirty(dat, ptr);
  1732. if (ret < 0)
  1733. goto out;
  1734. }
  1735. nilfs_btree_commit_propagate_v(btree, path, level, maxlevel, bh, dat);
  1736. out:
  1737. brelse(path[level].bp_bh);
  1738. path[level].bp_bh = NULL;
  1739. return ret;
  1740. }
  1741. static int nilfs_btree_propagate(struct nilfs_bmap *btree,
  1742. struct buffer_head *bh)
  1743. {
  1744. struct nilfs_btree_path *path;
  1745. struct nilfs_btree_node *node;
  1746. __u64 key;
  1747. int level, ret;
  1748. WARN_ON(!buffer_dirty(bh));
  1749. path = nilfs_btree_alloc_path();
  1750. if (path == NULL)
  1751. return -ENOMEM;
  1752. if (buffer_nilfs_node(bh)) {
  1753. node = (struct nilfs_btree_node *)bh->b_data;
  1754. key = nilfs_btree_node_get_key(node, 0);
  1755. level = nilfs_btree_node_get_level(node);
  1756. } else {
  1757. key = nilfs_bmap_data_get_key(btree, bh);
  1758. level = NILFS_BTREE_LEVEL_DATA;
  1759. }
  1760. ret = nilfs_btree_do_lookup(btree, path, key, NULL, level + 1, 0);
  1761. if (ret < 0) {
  1762. if (unlikely(ret == -ENOENT))
  1763. nilfs_crit(btree->b_inode->i_sb,
  1764. "writing node/leaf block does not appear in b-tree (ino=%lu) at key=%llu, level=%d",
  1765. btree->b_inode->i_ino,
  1766. (unsigned long long)key, level);
  1767. goto out;
  1768. }
  1769. ret = NILFS_BMAP_USE_VBN(btree) ?
  1770. nilfs_btree_propagate_v(btree, path, level, bh) :
  1771. nilfs_btree_propagate_p(btree, path, level, bh);
  1772. out:
  1773. nilfs_btree_free_path(path);
  1774. return ret;
  1775. }
  1776. static int nilfs_btree_propagate_gc(struct nilfs_bmap *btree,
  1777. struct buffer_head *bh)
  1778. {
  1779. return nilfs_dat_mark_dirty(nilfs_bmap_get_dat(btree), bh->b_blocknr);
  1780. }
  1781. static void nilfs_btree_add_dirty_buffer(struct nilfs_bmap *btree,
  1782. struct list_head *lists,
  1783. struct buffer_head *bh)
  1784. {
  1785. struct list_head *head;
  1786. struct buffer_head *cbh;
  1787. struct nilfs_btree_node *node, *cnode;
  1788. __u64 key, ckey;
  1789. int level;
  1790. get_bh(bh);
  1791. node = (struct nilfs_btree_node *)bh->b_data;
  1792. key = nilfs_btree_node_get_key(node, 0);
  1793. level = nilfs_btree_node_get_level(node);
  1794. if (level < NILFS_BTREE_LEVEL_NODE_MIN ||
  1795. level >= NILFS_BTREE_LEVEL_MAX) {
  1796. dump_stack();
  1797. nilfs_warn(btree->b_inode->i_sb,
  1798. "invalid btree level: %d (key=%llu, ino=%lu, blocknr=%llu)",
  1799. level, (unsigned long long)key,
  1800. btree->b_inode->i_ino,
  1801. (unsigned long long)bh->b_blocknr);
  1802. return;
  1803. }
  1804. list_for_each(head, &lists[level]) {
  1805. cbh = list_entry(head, struct buffer_head, b_assoc_buffers);
  1806. cnode = (struct nilfs_btree_node *)cbh->b_data;
  1807. ckey = nilfs_btree_node_get_key(cnode, 0);
  1808. if (key < ckey)
  1809. break;
  1810. }
  1811. list_add_tail(&bh->b_assoc_buffers, head);
  1812. }
  1813. static void nilfs_btree_lookup_dirty_buffers(struct nilfs_bmap *btree,
  1814. struct list_head *listp)
  1815. {
  1816. struct address_space *btcache = &NILFS_BMAP_I(btree)->i_btnode_cache;
  1817. struct list_head lists[NILFS_BTREE_LEVEL_MAX];
  1818. struct pagevec pvec;
  1819. struct buffer_head *bh, *head;
  1820. pgoff_t index = 0;
  1821. int level, i;
  1822. for (level = NILFS_BTREE_LEVEL_NODE_MIN;
  1823. level < NILFS_BTREE_LEVEL_MAX;
  1824. level++)
  1825. INIT_LIST_HEAD(&lists[level]);
  1826. pagevec_init(&pvec);
  1827. while (pagevec_lookup_tag(&pvec, btcache, &index,
  1828. PAGECACHE_TAG_DIRTY)) {
  1829. for (i = 0; i < pagevec_count(&pvec); i++) {
  1830. bh = head = page_buffers(pvec.pages[i]);
  1831. do {
  1832. if (buffer_dirty(bh))
  1833. nilfs_btree_add_dirty_buffer(btree,
  1834. lists, bh);
  1835. } while ((bh = bh->b_this_page) != head);
  1836. }
  1837. pagevec_release(&pvec);
  1838. cond_resched();
  1839. }
  1840. for (level = NILFS_BTREE_LEVEL_NODE_MIN;
  1841. level < NILFS_BTREE_LEVEL_MAX;
  1842. level++)
  1843. list_splice_tail(&lists[level], listp);
  1844. }
  1845. static int nilfs_btree_assign_p(struct nilfs_bmap *btree,
  1846. struct nilfs_btree_path *path,
  1847. int level,
  1848. struct buffer_head **bh,
  1849. sector_t blocknr,
  1850. union nilfs_binfo *binfo)
  1851. {
  1852. struct nilfs_btree_node *parent;
  1853. __u64 key;
  1854. __u64 ptr;
  1855. int ncmax, ret;
  1856. parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
  1857. ptr = nilfs_btree_node_get_ptr(parent, path[level + 1].bp_index,
  1858. ncmax);
  1859. if (buffer_nilfs_node(*bh)) {
  1860. path[level].bp_ctxt.oldkey = ptr;
  1861. path[level].bp_ctxt.newkey = blocknr;
  1862. path[level].bp_ctxt.bh = *bh;
  1863. ret = nilfs_btnode_prepare_change_key(
  1864. &NILFS_BMAP_I(btree)->i_btnode_cache,
  1865. &path[level].bp_ctxt);
  1866. if (ret < 0)
  1867. return ret;
  1868. nilfs_btnode_commit_change_key(
  1869. &NILFS_BMAP_I(btree)->i_btnode_cache,
  1870. &path[level].bp_ctxt);
  1871. *bh = path[level].bp_ctxt.bh;
  1872. }
  1873. nilfs_btree_node_set_ptr(parent, path[level + 1].bp_index, blocknr,
  1874. ncmax);
  1875. key = nilfs_btree_node_get_key(parent, path[level + 1].bp_index);
  1876. /* on-disk format */
  1877. binfo->bi_dat.bi_blkoff = cpu_to_le64(key);
  1878. binfo->bi_dat.bi_level = level;
  1879. return 0;
  1880. }
  1881. static int nilfs_btree_assign_v(struct nilfs_bmap *btree,
  1882. struct nilfs_btree_path *path,
  1883. int level,
  1884. struct buffer_head **bh,
  1885. sector_t blocknr,
  1886. union nilfs_binfo *binfo)
  1887. {
  1888. struct nilfs_btree_node *parent;
  1889. struct inode *dat = nilfs_bmap_get_dat(btree);
  1890. __u64 key;
  1891. __u64 ptr;
  1892. union nilfs_bmap_ptr_req req;
  1893. int ncmax, ret;
  1894. parent = nilfs_btree_get_node(btree, path, level + 1, &ncmax);
  1895. ptr = nilfs_btree_node_get_ptr(parent, path[level + 1].bp_index,
  1896. ncmax);
  1897. req.bpr_ptr = ptr;
  1898. ret = nilfs_dat_prepare_start(dat, &req.bpr_req);
  1899. if (ret < 0)
  1900. return ret;
  1901. nilfs_dat_commit_start(dat, &req.bpr_req, blocknr);
  1902. key = nilfs_btree_node_get_key(parent, path[level + 1].bp_index);
  1903. /* on-disk format */
  1904. binfo->bi_v.bi_vblocknr = cpu_to_le64(ptr);
  1905. binfo->bi_v.bi_blkoff = cpu_to_le64(key);
  1906. return 0;
  1907. }
  1908. static int nilfs_btree_assign(struct nilfs_bmap *btree,
  1909. struct buffer_head **bh,
  1910. sector_t blocknr,
  1911. union nilfs_binfo *binfo)
  1912. {
  1913. struct nilfs_btree_path *path;
  1914. struct nilfs_btree_node *node;
  1915. __u64 key;
  1916. int level, ret;
  1917. path = nilfs_btree_alloc_path();
  1918. if (path == NULL)
  1919. return -ENOMEM;
  1920. if (buffer_nilfs_node(*bh)) {
  1921. node = (struct nilfs_btree_node *)(*bh)->b_data;
  1922. key = nilfs_btree_node_get_key(node, 0);
  1923. level = nilfs_btree_node_get_level(node);
  1924. } else {
  1925. key = nilfs_bmap_data_get_key(btree, *bh);
  1926. level = NILFS_BTREE_LEVEL_DATA;
  1927. }
  1928. ret = nilfs_btree_do_lookup(btree, path, key, NULL, level + 1, 0);
  1929. if (ret < 0) {
  1930. WARN_ON(ret == -ENOENT);
  1931. goto out;
  1932. }
  1933. ret = NILFS_BMAP_USE_VBN(btree) ?
  1934. nilfs_btree_assign_v(btree, path, level, bh, blocknr, binfo) :
  1935. nilfs_btree_assign_p(btree, path, level, bh, blocknr, binfo);
  1936. out:
  1937. nilfs_btree_free_path(path);
  1938. return ret;
  1939. }
  1940. static int nilfs_btree_assign_gc(struct nilfs_bmap *btree,
  1941. struct buffer_head **bh,
  1942. sector_t blocknr,
  1943. union nilfs_binfo *binfo)
  1944. {
  1945. struct nilfs_btree_node *node;
  1946. __u64 key;
  1947. int ret;
  1948. ret = nilfs_dat_move(nilfs_bmap_get_dat(btree), (*bh)->b_blocknr,
  1949. blocknr);
  1950. if (ret < 0)
  1951. return ret;
  1952. if (buffer_nilfs_node(*bh)) {
  1953. node = (struct nilfs_btree_node *)(*bh)->b_data;
  1954. key = nilfs_btree_node_get_key(node, 0);
  1955. } else
  1956. key = nilfs_bmap_data_get_key(btree, *bh);
  1957. /* on-disk format */
  1958. binfo->bi_v.bi_vblocknr = cpu_to_le64((*bh)->b_blocknr);
  1959. binfo->bi_v.bi_blkoff = cpu_to_le64(key);
  1960. return 0;
  1961. }
  1962. static int nilfs_btree_mark(struct nilfs_bmap *btree, __u64 key, int level)
  1963. {
  1964. struct buffer_head *bh;
  1965. struct nilfs_btree_path *path;
  1966. __u64 ptr;
  1967. int ret;
  1968. path = nilfs_btree_alloc_path();
  1969. if (path == NULL)
  1970. return -ENOMEM;
  1971. ret = nilfs_btree_do_lookup(btree, path, key, &ptr, level + 1, 0);
  1972. if (ret < 0) {
  1973. WARN_ON(ret == -ENOENT);
  1974. goto out;
  1975. }
  1976. ret = nilfs_btree_get_block(btree, ptr, &bh);
  1977. if (ret < 0) {
  1978. WARN_ON(ret == -ENOENT);
  1979. goto out;
  1980. }
  1981. if (!buffer_dirty(bh))
  1982. mark_buffer_dirty(bh);
  1983. brelse(bh);
  1984. if (!nilfs_bmap_dirty(btree))
  1985. nilfs_bmap_set_dirty(btree);
  1986. out:
  1987. nilfs_btree_free_path(path);
  1988. return ret;
  1989. }
  1990. static const struct nilfs_bmap_operations nilfs_btree_ops = {
  1991. .bop_lookup = nilfs_btree_lookup,
  1992. .bop_lookup_contig = nilfs_btree_lookup_contig,
  1993. .bop_insert = nilfs_btree_insert,
  1994. .bop_delete = nilfs_btree_delete,
  1995. .bop_clear = NULL,
  1996. .bop_propagate = nilfs_btree_propagate,
  1997. .bop_lookup_dirty_buffers = nilfs_btree_lookup_dirty_buffers,
  1998. .bop_assign = nilfs_btree_assign,
  1999. .bop_mark = nilfs_btree_mark,
  2000. .bop_seek_key = nilfs_btree_seek_key,
  2001. .bop_last_key = nilfs_btree_last_key,
  2002. .bop_check_insert = NULL,
  2003. .bop_check_delete = nilfs_btree_check_delete,
  2004. .bop_gather_data = nilfs_btree_gather_data,
  2005. };
  2006. static const struct nilfs_bmap_operations nilfs_btree_ops_gc = {
  2007. .bop_lookup = NULL,
  2008. .bop_lookup_contig = NULL,
  2009. .bop_insert = NULL,
  2010. .bop_delete = NULL,
  2011. .bop_clear = NULL,
  2012. .bop_propagate = nilfs_btree_propagate_gc,
  2013. .bop_lookup_dirty_buffers = nilfs_btree_lookup_dirty_buffers,
  2014. .bop_assign = nilfs_btree_assign_gc,
  2015. .bop_mark = NULL,
  2016. .bop_seek_key = NULL,
  2017. .bop_last_key = NULL,
  2018. .bop_check_insert = NULL,
  2019. .bop_check_delete = NULL,
  2020. .bop_gather_data = NULL,
  2021. };
  2022. static void __nilfs_btree_init(struct nilfs_bmap *bmap)
  2023. {
  2024. bmap->b_ops = &nilfs_btree_ops;
  2025. bmap->b_nchildren_per_block =
  2026. NILFS_BTREE_NODE_NCHILDREN_MAX(nilfs_btree_node_size(bmap));
  2027. }
  2028. int nilfs_btree_init(struct nilfs_bmap *bmap)
  2029. {
  2030. int ret = 0;
  2031. __nilfs_btree_init(bmap);
  2032. if (nilfs_btree_root_broken(nilfs_btree_get_root(bmap), bmap->b_inode))
  2033. ret = -EIO;
  2034. return ret;
  2035. }
  2036. void nilfs_btree_init_gc(struct nilfs_bmap *bmap)
  2037. {
  2038. bmap->b_ops = &nilfs_btree_ops_gc;
  2039. bmap->b_nchildren_per_block =
  2040. NILFS_BTREE_NODE_NCHILDREN_MAX(nilfs_btree_node_size(bmap));
  2041. }