xfs_alloc_btree.c 64 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994199519961997199819992000200120022003200420052006200720082009201020112012201320142015201620172018201920202021202220232024202520262027202820292030203120322033203420352036203720382039204020412042204320442045204620472048204920502051205220532054205520562057205820592060206120622063206420652066206720682069207020712072207320742075207620772078207920802081208220832084208520862087208820892090209120922093209420952096209720982099210021012102210321042105210621072108210921102111211221132114211521162117211821192120212121222123212421252126212721282129213021312132213321342135213621372138213921402141214221432144214521462147214821492150215121522153215421552156215721582159216021612162216321642165216621672168216921702171217221732174217521762177217821792180218121822183218421852186218721882189219021912192219321942195219621972198219922002201220222032204220522062207
  1. /*
  2. * Copyright (c) 2000-2001,2005 Silicon Graphics, Inc.
  3. * All Rights Reserved.
  4. *
  5. * This program is free software; you can redistribute it and/or
  6. * modify it under the terms of the GNU General Public License as
  7. * published by the Free Software Foundation.
  8. *
  9. * This program is distributed in the hope that it would be useful,
  10. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  12. * GNU General Public License for more details.
  13. *
  14. * You should have received a copy of the GNU General Public License
  15. * along with this program; if not, write the Free Software Foundation,
  16. * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
  17. */
  18. #include "xfs.h"
  19. #include "xfs_fs.h"
  20. #include "xfs_types.h"
  21. #include "xfs_bit.h"
  22. #include "xfs_log.h"
  23. #include "xfs_inum.h"
  24. #include "xfs_trans.h"
  25. #include "xfs_sb.h"
  26. #include "xfs_ag.h"
  27. #include "xfs_dir2.h"
  28. #include "xfs_dmapi.h"
  29. #include "xfs_mount.h"
  30. #include "xfs_bmap_btree.h"
  31. #include "xfs_alloc_btree.h"
  32. #include "xfs_ialloc_btree.h"
  33. #include "xfs_dir2_sf.h"
  34. #include "xfs_attr_sf.h"
  35. #include "xfs_dinode.h"
  36. #include "xfs_inode.h"
  37. #include "xfs_btree.h"
  38. #include "xfs_ialloc.h"
  39. #include "xfs_alloc.h"
  40. #include "xfs_error.h"
  41. /*
  42. * Prototypes for internal functions.
  43. */
  44. STATIC void xfs_alloc_log_block(xfs_trans_t *, xfs_buf_t *, int);
  45. STATIC void xfs_alloc_log_keys(xfs_btree_cur_t *, xfs_buf_t *, int, int);
  46. STATIC void xfs_alloc_log_ptrs(xfs_btree_cur_t *, xfs_buf_t *, int, int);
  47. STATIC void xfs_alloc_log_recs(xfs_btree_cur_t *, xfs_buf_t *, int, int);
  48. STATIC int xfs_alloc_lshift(xfs_btree_cur_t *, int, int *);
  49. STATIC int xfs_alloc_newroot(xfs_btree_cur_t *, int *);
  50. STATIC int xfs_alloc_rshift(xfs_btree_cur_t *, int, int *);
  51. STATIC int xfs_alloc_split(xfs_btree_cur_t *, int, xfs_agblock_t *,
  52. xfs_alloc_key_t *, xfs_btree_cur_t **, int *);
  53. STATIC int xfs_alloc_updkey(xfs_btree_cur_t *, xfs_alloc_key_t *, int);
  54. /*
  55. * Internal functions.
  56. */
  57. /*
  58. * Single level of the xfs_alloc_delete record deletion routine.
  59. * Delete record pointed to by cur/level.
  60. * Remove the record from its block then rebalance the tree.
  61. * Return 0 for error, 1 for done, 2 to go on to the next level.
  62. */
  63. STATIC int /* error */
  64. xfs_alloc_delrec(
  65. xfs_btree_cur_t *cur, /* btree cursor */
  66. int level, /* level removing record from */
  67. int *stat) /* fail/done/go-on */
  68. {
  69. xfs_agf_t *agf; /* allocation group freelist header */
  70. xfs_alloc_block_t *block; /* btree block record/key lives in */
  71. xfs_agblock_t bno; /* btree block number */
  72. xfs_buf_t *bp; /* buffer for block */
  73. int error; /* error return value */
  74. int i; /* loop index */
  75. xfs_alloc_key_t key; /* kp points here if block is level 0 */
  76. xfs_agblock_t lbno; /* left block's block number */
  77. xfs_buf_t *lbp; /* left block's buffer pointer */
  78. xfs_alloc_block_t *left; /* left btree block */
  79. xfs_alloc_key_t *lkp=NULL; /* left block key pointer */
  80. xfs_alloc_ptr_t *lpp=NULL; /* left block address pointer */
  81. int lrecs=0; /* number of records in left block */
  82. xfs_alloc_rec_t *lrp; /* left block record pointer */
  83. xfs_mount_t *mp; /* mount structure */
  84. int ptr; /* index in btree block for this rec */
  85. xfs_agblock_t rbno; /* right block's block number */
  86. xfs_buf_t *rbp; /* right block's buffer pointer */
  87. xfs_alloc_block_t *right; /* right btree block */
  88. xfs_alloc_key_t *rkp; /* right block key pointer */
  89. xfs_alloc_ptr_t *rpp; /* right block address pointer */
  90. int rrecs=0; /* number of records in right block */
  91. int numrecs;
  92. xfs_alloc_rec_t *rrp; /* right block record pointer */
  93. xfs_btree_cur_t *tcur; /* temporary btree cursor */
  94. /*
  95. * Get the index of the entry being deleted, check for nothing there.
  96. */
  97. ptr = cur->bc_ptrs[level];
  98. if (ptr == 0) {
  99. *stat = 0;
  100. return 0;
  101. }
  102. /*
  103. * Get the buffer & block containing the record or key/ptr.
  104. */
  105. bp = cur->bc_bufs[level];
  106. block = XFS_BUF_TO_ALLOC_BLOCK(bp);
  107. #ifdef DEBUG
  108. if ((error = xfs_btree_check_sblock(cur, block, level, bp)))
  109. return error;
  110. #endif
  111. /*
  112. * Fail if we're off the end of the block.
  113. */
  114. numrecs = be16_to_cpu(block->bb_numrecs);
  115. if (ptr > numrecs) {
  116. *stat = 0;
  117. return 0;
  118. }
  119. XFS_STATS_INC(xs_abt_delrec);
  120. /*
  121. * It's a nonleaf. Excise the key and ptr being deleted, by
  122. * sliding the entries past them down one.
  123. * Log the changed areas of the block.
  124. */
  125. if (level > 0) {
  126. lkp = XFS_ALLOC_KEY_ADDR(block, 1, cur);
  127. lpp = XFS_ALLOC_PTR_ADDR(block, 1, cur);
  128. #ifdef DEBUG
  129. for (i = ptr; i < numrecs; i++) {
  130. if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(lpp[i]), level)))
  131. return error;
  132. }
  133. #endif
  134. if (ptr < numrecs) {
  135. memmove(&lkp[ptr - 1], &lkp[ptr],
  136. (numrecs - ptr) * sizeof(*lkp));
  137. memmove(&lpp[ptr - 1], &lpp[ptr],
  138. (numrecs - ptr) * sizeof(*lpp));
  139. xfs_alloc_log_ptrs(cur, bp, ptr, numrecs - 1);
  140. xfs_alloc_log_keys(cur, bp, ptr, numrecs - 1);
  141. }
  142. }
  143. /*
  144. * It's a leaf. Excise the record being deleted, by sliding the
  145. * entries past it down one. Log the changed areas of the block.
  146. */
  147. else {
  148. lrp = XFS_ALLOC_REC_ADDR(block, 1, cur);
  149. if (ptr < numrecs) {
  150. memmove(&lrp[ptr - 1], &lrp[ptr],
  151. (numrecs - ptr) * sizeof(*lrp));
  152. xfs_alloc_log_recs(cur, bp, ptr, numrecs - 1);
  153. }
  154. /*
  155. * If it's the first record in the block, we'll need a key
  156. * structure to pass up to the next level (updkey).
  157. */
  158. if (ptr == 1) {
  159. key.ar_startblock = lrp->ar_startblock;
  160. key.ar_blockcount = lrp->ar_blockcount;
  161. lkp = &key;
  162. }
  163. }
  164. /*
  165. * Decrement and log the number of entries in the block.
  166. */
  167. numrecs--;
  168. block->bb_numrecs = cpu_to_be16(numrecs);
  169. xfs_alloc_log_block(cur->bc_tp, bp, XFS_BB_NUMRECS);
  170. /*
  171. * See if the longest free extent in the allocation group was
  172. * changed by this operation. True if it's the by-size btree, and
  173. * this is the leaf level, and there is no right sibling block,
  174. * and this was the last record.
  175. */
  176. agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
  177. mp = cur->bc_mp;
  178. if (level == 0 &&
  179. cur->bc_btnum == XFS_BTNUM_CNT &&
  180. be32_to_cpu(block->bb_rightsib) == NULLAGBLOCK &&
  181. ptr > numrecs) {
  182. ASSERT(ptr == numrecs + 1);
  183. /*
  184. * There are still records in the block. Grab the size
  185. * from the last one.
  186. */
  187. if (numrecs) {
  188. rrp = XFS_ALLOC_REC_ADDR(block, numrecs, cur);
  189. agf->agf_longest = rrp->ar_blockcount;
  190. }
  191. /*
  192. * No free extents left.
  193. */
  194. else
  195. agf->agf_longest = 0;
  196. mp->m_perag[be32_to_cpu(agf->agf_seqno)].pagf_longest =
  197. be32_to_cpu(agf->agf_longest);
  198. xfs_alloc_log_agf(cur->bc_tp, cur->bc_private.a.agbp,
  199. XFS_AGF_LONGEST);
  200. }
  201. /*
  202. * Is this the root level? If so, we're almost done.
  203. */
  204. if (level == cur->bc_nlevels - 1) {
  205. /*
  206. * If this is the root level,
  207. * and there's only one entry left,
  208. * and it's NOT the leaf level,
  209. * then we can get rid of this level.
  210. */
  211. if (numrecs == 1 && level > 0) {
  212. /*
  213. * lpp is still set to the first pointer in the block.
  214. * Make it the new root of the btree.
  215. */
  216. bno = be32_to_cpu(agf->agf_roots[cur->bc_btnum]);
  217. agf->agf_roots[cur->bc_btnum] = *lpp;
  218. be32_add(&agf->agf_levels[cur->bc_btnum], -1);
  219. mp->m_perag[be32_to_cpu(agf->agf_seqno)].pagf_levels[cur->bc_btnum]--;
  220. /*
  221. * Put this buffer/block on the ag's freelist.
  222. */
  223. if ((error = xfs_alloc_put_freelist(cur->bc_tp,
  224. cur->bc_private.a.agbp, NULL, bno)))
  225. return error;
  226. /*
  227. * Since blocks move to the free list without the
  228. * coordination used in xfs_bmap_finish, we can't allow
  229. * block to be available for reallocation and
  230. * non-transaction writing (user data) until we know
  231. * that the transaction that moved it to the free list
  232. * is permanently on disk. We track the blocks by
  233. * declaring these blocks as "busy"; the busy list is
  234. * maintained on a per-ag basis and each transaction
  235. * records which entries should be removed when the
  236. * iclog commits to disk. If a busy block is
  237. * allocated, the iclog is pushed up to the LSN
  238. * that freed the block.
  239. */
  240. xfs_alloc_mark_busy(cur->bc_tp,
  241. be32_to_cpu(agf->agf_seqno), bno, 1);
  242. xfs_trans_agbtree_delta(cur->bc_tp, -1);
  243. xfs_alloc_log_agf(cur->bc_tp, cur->bc_private.a.agbp,
  244. XFS_AGF_ROOTS | XFS_AGF_LEVELS);
  245. /*
  246. * Update the cursor so there's one fewer level.
  247. */
  248. xfs_btree_setbuf(cur, level, NULL);
  249. cur->bc_nlevels--;
  250. } else if (level > 0 &&
  251. (error = xfs_alloc_decrement(cur, level, &i)))
  252. return error;
  253. *stat = 1;
  254. return 0;
  255. }
  256. /*
  257. * If we deleted the leftmost entry in the block, update the
  258. * key values above us in the tree.
  259. */
  260. if (ptr == 1 && (error = xfs_alloc_updkey(cur, lkp, level + 1)))
  261. return error;
  262. /*
  263. * If the number of records remaining in the block is at least
  264. * the minimum, we're done.
  265. */
  266. if (numrecs >= XFS_ALLOC_BLOCK_MINRECS(level, cur)) {
  267. if (level > 0 && (error = xfs_alloc_decrement(cur, level, &i)))
  268. return error;
  269. *stat = 1;
  270. return 0;
  271. }
  272. /*
  273. * Otherwise, we have to move some records around to keep the
  274. * tree balanced. Look at the left and right sibling blocks to
  275. * see if we can re-balance by moving only one record.
  276. */
  277. rbno = be32_to_cpu(block->bb_rightsib);
  278. lbno = be32_to_cpu(block->bb_leftsib);
  279. bno = NULLAGBLOCK;
  280. ASSERT(rbno != NULLAGBLOCK || lbno != NULLAGBLOCK);
  281. /*
  282. * Duplicate the cursor so our btree manipulations here won't
  283. * disrupt the next level up.
  284. */
  285. if ((error = xfs_btree_dup_cursor(cur, &tcur)))
  286. return error;
  287. /*
  288. * If there's a right sibling, see if it's ok to shift an entry
  289. * out of it.
  290. */
  291. if (rbno != NULLAGBLOCK) {
  292. /*
  293. * Move the temp cursor to the last entry in the next block.
  294. * Actually any entry but the first would suffice.
  295. */
  296. i = xfs_btree_lastrec(tcur, level);
  297. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  298. if ((error = xfs_alloc_increment(tcur, level, &i)))
  299. goto error0;
  300. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  301. i = xfs_btree_lastrec(tcur, level);
  302. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  303. /*
  304. * Grab a pointer to the block.
  305. */
  306. rbp = tcur->bc_bufs[level];
  307. right = XFS_BUF_TO_ALLOC_BLOCK(rbp);
  308. #ifdef DEBUG
  309. if ((error = xfs_btree_check_sblock(cur, right, level, rbp)))
  310. goto error0;
  311. #endif
  312. /*
  313. * Grab the current block number, for future use.
  314. */
  315. bno = be32_to_cpu(right->bb_leftsib);
  316. /*
  317. * If right block is full enough so that removing one entry
  318. * won't make it too empty, and left-shifting an entry out
  319. * of right to us works, we're done.
  320. */
  321. if (be16_to_cpu(right->bb_numrecs) - 1 >=
  322. XFS_ALLOC_BLOCK_MINRECS(level, cur)) {
  323. if ((error = xfs_alloc_lshift(tcur, level, &i)))
  324. goto error0;
  325. if (i) {
  326. ASSERT(be16_to_cpu(block->bb_numrecs) >=
  327. XFS_ALLOC_BLOCK_MINRECS(level, cur));
  328. xfs_btree_del_cursor(tcur,
  329. XFS_BTREE_NOERROR);
  330. if (level > 0 &&
  331. (error = xfs_alloc_decrement(cur, level,
  332. &i)))
  333. return error;
  334. *stat = 1;
  335. return 0;
  336. }
  337. }
  338. /*
  339. * Otherwise, grab the number of records in right for
  340. * future reference, and fix up the temp cursor to point
  341. * to our block again (last record).
  342. */
  343. rrecs = be16_to_cpu(right->bb_numrecs);
  344. if (lbno != NULLAGBLOCK) {
  345. i = xfs_btree_firstrec(tcur, level);
  346. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  347. if ((error = xfs_alloc_decrement(tcur, level, &i)))
  348. goto error0;
  349. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  350. }
  351. }
  352. /*
  353. * If there's a left sibling, see if it's ok to shift an entry
  354. * out of it.
  355. */
  356. if (lbno != NULLAGBLOCK) {
  357. /*
  358. * Move the temp cursor to the first entry in the
  359. * previous block.
  360. */
  361. i = xfs_btree_firstrec(tcur, level);
  362. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  363. if ((error = xfs_alloc_decrement(tcur, level, &i)))
  364. goto error0;
  365. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  366. xfs_btree_firstrec(tcur, level);
  367. /*
  368. * Grab a pointer to the block.
  369. */
  370. lbp = tcur->bc_bufs[level];
  371. left = XFS_BUF_TO_ALLOC_BLOCK(lbp);
  372. #ifdef DEBUG
  373. if ((error = xfs_btree_check_sblock(cur, left, level, lbp)))
  374. goto error0;
  375. #endif
  376. /*
  377. * Grab the current block number, for future use.
  378. */
  379. bno = be32_to_cpu(left->bb_rightsib);
  380. /*
  381. * If left block is full enough so that removing one entry
  382. * won't make it too empty, and right-shifting an entry out
  383. * of left to us works, we're done.
  384. */
  385. if (be16_to_cpu(left->bb_numrecs) - 1 >=
  386. XFS_ALLOC_BLOCK_MINRECS(level, cur)) {
  387. if ((error = xfs_alloc_rshift(tcur, level, &i)))
  388. goto error0;
  389. if (i) {
  390. ASSERT(be16_to_cpu(block->bb_numrecs) >=
  391. XFS_ALLOC_BLOCK_MINRECS(level, cur));
  392. xfs_btree_del_cursor(tcur,
  393. XFS_BTREE_NOERROR);
  394. if (level == 0)
  395. cur->bc_ptrs[0]++;
  396. *stat = 1;
  397. return 0;
  398. }
  399. }
  400. /*
  401. * Otherwise, grab the number of records in right for
  402. * future reference.
  403. */
  404. lrecs = be16_to_cpu(left->bb_numrecs);
  405. }
  406. /*
  407. * Delete the temp cursor, we're done with it.
  408. */
  409. xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
  410. /*
  411. * If here, we need to do a join to keep the tree balanced.
  412. */
  413. ASSERT(bno != NULLAGBLOCK);
  414. /*
  415. * See if we can join with the left neighbor block.
  416. */
  417. if (lbno != NULLAGBLOCK &&
  418. lrecs + numrecs <= XFS_ALLOC_BLOCK_MAXRECS(level, cur)) {
  419. /*
  420. * Set "right" to be the starting block,
  421. * "left" to be the left neighbor.
  422. */
  423. rbno = bno;
  424. right = block;
  425. rrecs = be16_to_cpu(right->bb_numrecs);
  426. rbp = bp;
  427. if ((error = xfs_btree_read_bufs(mp, cur->bc_tp,
  428. cur->bc_private.a.agno, lbno, 0, &lbp,
  429. XFS_ALLOC_BTREE_REF)))
  430. return error;
  431. left = XFS_BUF_TO_ALLOC_BLOCK(lbp);
  432. lrecs = be16_to_cpu(left->bb_numrecs);
  433. if ((error = xfs_btree_check_sblock(cur, left, level, lbp)))
  434. return error;
  435. }
  436. /*
  437. * If that won't work, see if we can join with the right neighbor block.
  438. */
  439. else if (rbno != NULLAGBLOCK &&
  440. rrecs + numrecs <= XFS_ALLOC_BLOCK_MAXRECS(level, cur)) {
  441. /*
  442. * Set "left" to be the starting block,
  443. * "right" to be the right neighbor.
  444. */
  445. lbno = bno;
  446. left = block;
  447. lrecs = be16_to_cpu(left->bb_numrecs);
  448. lbp = bp;
  449. if ((error = xfs_btree_read_bufs(mp, cur->bc_tp,
  450. cur->bc_private.a.agno, rbno, 0, &rbp,
  451. XFS_ALLOC_BTREE_REF)))
  452. return error;
  453. right = XFS_BUF_TO_ALLOC_BLOCK(rbp);
  454. rrecs = be16_to_cpu(right->bb_numrecs);
  455. if ((error = xfs_btree_check_sblock(cur, right, level, rbp)))
  456. return error;
  457. }
  458. /*
  459. * Otherwise, we can't fix the imbalance.
  460. * Just return. This is probably a logic error, but it's not fatal.
  461. */
  462. else {
  463. if (level > 0 && (error = xfs_alloc_decrement(cur, level, &i)))
  464. return error;
  465. *stat = 1;
  466. return 0;
  467. }
  468. /*
  469. * We're now going to join "left" and "right" by moving all the stuff
  470. * in "right" to "left" and deleting "right".
  471. */
  472. if (level > 0) {
  473. /*
  474. * It's a non-leaf. Move keys and pointers.
  475. */
  476. lkp = XFS_ALLOC_KEY_ADDR(left, lrecs + 1, cur);
  477. lpp = XFS_ALLOC_PTR_ADDR(left, lrecs + 1, cur);
  478. rkp = XFS_ALLOC_KEY_ADDR(right, 1, cur);
  479. rpp = XFS_ALLOC_PTR_ADDR(right, 1, cur);
  480. #ifdef DEBUG
  481. for (i = 0; i < rrecs; i++) {
  482. if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(rpp[i]), level)))
  483. return error;
  484. }
  485. #endif
  486. memcpy(lkp, rkp, rrecs * sizeof(*lkp));
  487. memcpy(lpp, rpp, rrecs * sizeof(*lpp));
  488. xfs_alloc_log_keys(cur, lbp, lrecs + 1, lrecs + rrecs);
  489. xfs_alloc_log_ptrs(cur, lbp, lrecs + 1, lrecs + rrecs);
  490. } else {
  491. /*
  492. * It's a leaf. Move records.
  493. */
  494. lrp = XFS_ALLOC_REC_ADDR(left, lrecs + 1, cur);
  495. rrp = XFS_ALLOC_REC_ADDR(right, 1, cur);
  496. memcpy(lrp, rrp, rrecs * sizeof(*lrp));
  497. xfs_alloc_log_recs(cur, lbp, lrecs + 1, lrecs + rrecs);
  498. }
  499. /*
  500. * If we joined with the left neighbor, set the buffer in the
  501. * cursor to the left block, and fix up the index.
  502. */
  503. if (bp != lbp) {
  504. xfs_btree_setbuf(cur, level, lbp);
  505. cur->bc_ptrs[level] += lrecs;
  506. }
  507. /*
  508. * If we joined with the right neighbor and there's a level above
  509. * us, increment the cursor at that level.
  510. */
  511. else if (level + 1 < cur->bc_nlevels &&
  512. (error = xfs_alloc_increment(cur, level + 1, &i)))
  513. return error;
  514. /*
  515. * Fix up the number of records in the surviving block.
  516. */
  517. lrecs += rrecs;
  518. left->bb_numrecs = cpu_to_be16(lrecs);
  519. /*
  520. * Fix up the right block pointer in the surviving block, and log it.
  521. */
  522. left->bb_rightsib = right->bb_rightsib;
  523. xfs_alloc_log_block(cur->bc_tp, lbp, XFS_BB_NUMRECS | XFS_BB_RIGHTSIB);
  524. /*
  525. * If there is a right sibling now, make it point to the
  526. * remaining block.
  527. */
  528. if (be32_to_cpu(left->bb_rightsib) != NULLAGBLOCK) {
  529. xfs_alloc_block_t *rrblock;
  530. xfs_buf_t *rrbp;
  531. if ((error = xfs_btree_read_bufs(mp, cur->bc_tp,
  532. cur->bc_private.a.agno, be32_to_cpu(left->bb_rightsib), 0,
  533. &rrbp, XFS_ALLOC_BTREE_REF)))
  534. return error;
  535. rrblock = XFS_BUF_TO_ALLOC_BLOCK(rrbp);
  536. if ((error = xfs_btree_check_sblock(cur, rrblock, level, rrbp)))
  537. return error;
  538. rrblock->bb_leftsib = cpu_to_be32(lbno);
  539. xfs_alloc_log_block(cur->bc_tp, rrbp, XFS_BB_LEFTSIB);
  540. }
  541. /*
  542. * Free the deleting block by putting it on the freelist.
  543. */
  544. if ((error = xfs_alloc_put_freelist(cur->bc_tp, cur->bc_private.a.agbp,
  545. NULL, rbno)))
  546. return error;
  547. /*
  548. * Since blocks move to the free list without the coordination
  549. * used in xfs_bmap_finish, we can't allow block to be available
  550. * for reallocation and non-transaction writing (user data)
  551. * until we know that the transaction that moved it to the free
  552. * list is permanently on disk. We track the blocks by declaring
  553. * these blocks as "busy"; the busy list is maintained on a
  554. * per-ag basis and each transaction records which entries
  555. * should be removed when the iclog commits to disk. If a
  556. * busy block is allocated, the iclog is pushed up to the
  557. * LSN that freed the block.
  558. */
  559. xfs_alloc_mark_busy(cur->bc_tp, be32_to_cpu(agf->agf_seqno), bno, 1);
  560. xfs_trans_agbtree_delta(cur->bc_tp, -1);
  561. /*
  562. * Adjust the current level's cursor so that we're left referring
  563. * to the right node, after we're done.
  564. * If this leaves the ptr value 0 our caller will fix it up.
  565. */
  566. if (level > 0)
  567. cur->bc_ptrs[level]--;
  568. /*
  569. * Return value means the next level up has something to do.
  570. */
  571. *stat = 2;
  572. return 0;
  573. error0:
  574. xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
  575. return error;
  576. }
  577. /*
  578. * Insert one record/level. Return information to the caller
  579. * allowing the next level up to proceed if necessary.
  580. */
  581. STATIC int /* error */
  582. xfs_alloc_insrec(
  583. xfs_btree_cur_t *cur, /* btree cursor */
  584. int level, /* level to insert record at */
  585. xfs_agblock_t *bnop, /* i/o: block number inserted */
  586. xfs_alloc_rec_t *recp, /* i/o: record data inserted */
  587. xfs_btree_cur_t **curp, /* output: new cursor replacing cur */
  588. int *stat) /* output: success/failure */
  589. {
  590. xfs_agf_t *agf; /* allocation group freelist header */
  591. xfs_alloc_block_t *block; /* btree block record/key lives in */
  592. xfs_buf_t *bp; /* buffer for block */
  593. int error; /* error return value */
  594. int i; /* loop index */
  595. xfs_alloc_key_t key; /* key value being inserted */
  596. xfs_alloc_key_t *kp; /* pointer to btree keys */
  597. xfs_agblock_t nbno; /* block number of allocated block */
  598. xfs_btree_cur_t *ncur; /* new cursor to be used at next lvl */
  599. xfs_alloc_key_t nkey; /* new key value, from split */
  600. xfs_alloc_rec_t nrec; /* new record value, for caller */
  601. int numrecs;
  602. int optr; /* old ptr value */
  603. xfs_alloc_ptr_t *pp; /* pointer to btree addresses */
  604. int ptr; /* index in btree block for this rec */
  605. xfs_alloc_rec_t *rp; /* pointer to btree records */
  606. ASSERT(be32_to_cpu(recp->ar_blockcount) > 0);
  607. /*
  608. * GCC doesn't understand the (arguably complex) control flow in
  609. * this function and complains about uninitialized structure fields
  610. * without this.
  611. */
  612. memset(&nrec, 0, sizeof(nrec));
  613. /*
  614. * If we made it to the root level, allocate a new root block
  615. * and we're done.
  616. */
  617. if (level >= cur->bc_nlevels) {
  618. XFS_STATS_INC(xs_abt_insrec);
  619. if ((error = xfs_alloc_newroot(cur, &i)))
  620. return error;
  621. *bnop = NULLAGBLOCK;
  622. *stat = i;
  623. return 0;
  624. }
  625. /*
  626. * Make a key out of the record data to be inserted, and save it.
  627. */
  628. key.ar_startblock = recp->ar_startblock;
  629. key.ar_blockcount = recp->ar_blockcount;
  630. optr = ptr = cur->bc_ptrs[level];
  631. /*
  632. * If we're off the left edge, return failure.
  633. */
  634. if (ptr == 0) {
  635. *stat = 0;
  636. return 0;
  637. }
  638. XFS_STATS_INC(xs_abt_insrec);
  639. /*
  640. * Get pointers to the btree buffer and block.
  641. */
  642. bp = cur->bc_bufs[level];
  643. block = XFS_BUF_TO_ALLOC_BLOCK(bp);
  644. numrecs = be16_to_cpu(block->bb_numrecs);
  645. #ifdef DEBUG
  646. if ((error = xfs_btree_check_sblock(cur, block, level, bp)))
  647. return error;
  648. /*
  649. * Check that the new entry is being inserted in the right place.
  650. */
  651. if (ptr <= numrecs) {
  652. if (level == 0) {
  653. rp = XFS_ALLOC_REC_ADDR(block, ptr, cur);
  654. xfs_btree_check_rec(cur->bc_btnum, recp, rp);
  655. } else {
  656. kp = XFS_ALLOC_KEY_ADDR(block, ptr, cur);
  657. xfs_btree_check_key(cur->bc_btnum, &key, kp);
  658. }
  659. }
  660. #endif
  661. nbno = NULLAGBLOCK;
  662. ncur = NULL;
  663. /*
  664. * If the block is full, we can't insert the new entry until we
  665. * make the block un-full.
  666. */
  667. if (numrecs == XFS_ALLOC_BLOCK_MAXRECS(level, cur)) {
  668. /*
  669. * First, try shifting an entry to the right neighbor.
  670. */
  671. if ((error = xfs_alloc_rshift(cur, level, &i)))
  672. return error;
  673. if (i) {
  674. /* nothing */
  675. }
  676. /*
  677. * Next, try shifting an entry to the left neighbor.
  678. */
  679. else {
  680. if ((error = xfs_alloc_lshift(cur, level, &i)))
  681. return error;
  682. if (i)
  683. optr = ptr = cur->bc_ptrs[level];
  684. else {
  685. /*
  686. * Next, try splitting the current block in
  687. * half. If this works we have to re-set our
  688. * variables because we could be in a
  689. * different block now.
  690. */
  691. if ((error = xfs_alloc_split(cur, level, &nbno,
  692. &nkey, &ncur, &i)))
  693. return error;
  694. if (i) {
  695. bp = cur->bc_bufs[level];
  696. block = XFS_BUF_TO_ALLOC_BLOCK(bp);
  697. #ifdef DEBUG
  698. if ((error =
  699. xfs_btree_check_sblock(cur,
  700. block, level, bp)))
  701. return error;
  702. #endif
  703. ptr = cur->bc_ptrs[level];
  704. nrec.ar_startblock = nkey.ar_startblock;
  705. nrec.ar_blockcount = nkey.ar_blockcount;
  706. }
  707. /*
  708. * Otherwise the insert fails.
  709. */
  710. else {
  711. *stat = 0;
  712. return 0;
  713. }
  714. }
  715. }
  716. }
  717. /*
  718. * At this point we know there's room for our new entry in the block
  719. * we're pointing at.
  720. */
  721. numrecs = be16_to_cpu(block->bb_numrecs);
  722. if (level > 0) {
  723. /*
  724. * It's a non-leaf entry. Make a hole for the new data
  725. * in the key and ptr regions of the block.
  726. */
  727. kp = XFS_ALLOC_KEY_ADDR(block, 1, cur);
  728. pp = XFS_ALLOC_PTR_ADDR(block, 1, cur);
  729. #ifdef DEBUG
  730. for (i = numrecs; i >= ptr; i--) {
  731. if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(pp[i - 1]), level)))
  732. return error;
  733. }
  734. #endif
  735. memmove(&kp[ptr], &kp[ptr - 1],
  736. (numrecs - ptr + 1) * sizeof(*kp));
  737. memmove(&pp[ptr], &pp[ptr - 1],
  738. (numrecs - ptr + 1) * sizeof(*pp));
  739. #ifdef DEBUG
  740. if ((error = xfs_btree_check_sptr(cur, *bnop, level)))
  741. return error;
  742. #endif
  743. /*
  744. * Now stuff the new data in, bump numrecs and log the new data.
  745. */
  746. kp[ptr - 1] = key;
  747. pp[ptr - 1] = cpu_to_be32(*bnop);
  748. numrecs++;
  749. block->bb_numrecs = cpu_to_be16(numrecs);
  750. xfs_alloc_log_keys(cur, bp, ptr, numrecs);
  751. xfs_alloc_log_ptrs(cur, bp, ptr, numrecs);
  752. #ifdef DEBUG
  753. if (ptr < numrecs)
  754. xfs_btree_check_key(cur->bc_btnum, kp + ptr - 1,
  755. kp + ptr);
  756. #endif
  757. } else {
  758. /*
  759. * It's a leaf entry. Make a hole for the new record.
  760. */
  761. rp = XFS_ALLOC_REC_ADDR(block, 1, cur);
  762. memmove(&rp[ptr], &rp[ptr - 1],
  763. (numrecs - ptr + 1) * sizeof(*rp));
  764. /*
  765. * Now stuff the new record in, bump numrecs
  766. * and log the new data.
  767. */
  768. rp[ptr - 1] = *recp;
  769. numrecs++;
  770. block->bb_numrecs = cpu_to_be16(numrecs);
  771. xfs_alloc_log_recs(cur, bp, ptr, numrecs);
  772. #ifdef DEBUG
  773. if (ptr < numrecs)
  774. xfs_btree_check_rec(cur->bc_btnum, rp + ptr - 1,
  775. rp + ptr);
  776. #endif
  777. }
  778. /*
  779. * Log the new number of records in the btree header.
  780. */
  781. xfs_alloc_log_block(cur->bc_tp, bp, XFS_BB_NUMRECS);
  782. /*
  783. * If we inserted at the start of a block, update the parents' keys.
  784. */
  785. if (optr == 1 && (error = xfs_alloc_updkey(cur, &key, level + 1)))
  786. return error;
  787. /*
  788. * Look to see if the longest extent in the allocation group
  789. * needs to be updated.
  790. */
  791. agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
  792. if (level == 0 &&
  793. cur->bc_btnum == XFS_BTNUM_CNT &&
  794. be32_to_cpu(block->bb_rightsib) == NULLAGBLOCK &&
  795. be32_to_cpu(recp->ar_blockcount) > be32_to_cpu(agf->agf_longest)) {
  796. /*
  797. * If this is a leaf in the by-size btree and there
  798. * is no right sibling block and this block is bigger
  799. * than the previous longest block, update it.
  800. */
  801. agf->agf_longest = recp->ar_blockcount;
  802. cur->bc_mp->m_perag[be32_to_cpu(agf->agf_seqno)].pagf_longest
  803. = be32_to_cpu(recp->ar_blockcount);
  804. xfs_alloc_log_agf(cur->bc_tp, cur->bc_private.a.agbp,
  805. XFS_AGF_LONGEST);
  806. }
  807. /*
  808. * Return the new block number, if any.
  809. * If there is one, give back a record value and a cursor too.
  810. */
  811. *bnop = nbno;
  812. if (nbno != NULLAGBLOCK) {
  813. *recp = nrec;
  814. *curp = ncur;
  815. }
  816. *stat = 1;
  817. return 0;
  818. }
  819. /*
  820. * Log header fields from a btree block.
  821. */
  822. STATIC void
  823. xfs_alloc_log_block(
  824. xfs_trans_t *tp, /* transaction pointer */
  825. xfs_buf_t *bp, /* buffer containing btree block */
  826. int fields) /* mask of fields: XFS_BB_... */
  827. {
  828. int first; /* first byte offset logged */
  829. int last; /* last byte offset logged */
  830. static const short offsets[] = { /* table of offsets */
  831. offsetof(xfs_alloc_block_t, bb_magic),
  832. offsetof(xfs_alloc_block_t, bb_level),
  833. offsetof(xfs_alloc_block_t, bb_numrecs),
  834. offsetof(xfs_alloc_block_t, bb_leftsib),
  835. offsetof(xfs_alloc_block_t, bb_rightsib),
  836. sizeof(xfs_alloc_block_t)
  837. };
  838. xfs_btree_offsets(fields, offsets, XFS_BB_NUM_BITS, &first, &last);
  839. xfs_trans_log_buf(tp, bp, first, last);
  840. }
  841. /*
  842. * Log keys from a btree block (nonleaf).
  843. */
  844. STATIC void
  845. xfs_alloc_log_keys(
  846. xfs_btree_cur_t *cur, /* btree cursor */
  847. xfs_buf_t *bp, /* buffer containing btree block */
  848. int kfirst, /* index of first key to log */
  849. int klast) /* index of last key to log */
  850. {
  851. xfs_alloc_block_t *block; /* btree block to log from */
  852. int first; /* first byte offset logged */
  853. xfs_alloc_key_t *kp; /* key pointer in btree block */
  854. int last; /* last byte offset logged */
  855. block = XFS_BUF_TO_ALLOC_BLOCK(bp);
  856. kp = XFS_ALLOC_KEY_ADDR(block, 1, cur);
  857. first = (int)((xfs_caddr_t)&kp[kfirst - 1] - (xfs_caddr_t)block);
  858. last = (int)(((xfs_caddr_t)&kp[klast] - 1) - (xfs_caddr_t)block);
  859. xfs_trans_log_buf(cur->bc_tp, bp, first, last);
  860. }
  861. /*
  862. * Log block pointer fields from a btree block (nonleaf).
  863. */
  864. STATIC void
  865. xfs_alloc_log_ptrs(
  866. xfs_btree_cur_t *cur, /* btree cursor */
  867. xfs_buf_t *bp, /* buffer containing btree block */
  868. int pfirst, /* index of first pointer to log */
  869. int plast) /* index of last pointer to log */
  870. {
  871. xfs_alloc_block_t *block; /* btree block to log from */
  872. int first; /* first byte offset logged */
  873. int last; /* last byte offset logged */
  874. xfs_alloc_ptr_t *pp; /* block-pointer pointer in btree blk */
  875. block = XFS_BUF_TO_ALLOC_BLOCK(bp);
  876. pp = XFS_ALLOC_PTR_ADDR(block, 1, cur);
  877. first = (int)((xfs_caddr_t)&pp[pfirst - 1] - (xfs_caddr_t)block);
  878. last = (int)(((xfs_caddr_t)&pp[plast] - 1) - (xfs_caddr_t)block);
  879. xfs_trans_log_buf(cur->bc_tp, bp, first, last);
  880. }
  881. /*
  882. * Log records from a btree block (leaf).
  883. */
  884. STATIC void
  885. xfs_alloc_log_recs(
  886. xfs_btree_cur_t *cur, /* btree cursor */
  887. xfs_buf_t *bp, /* buffer containing btree block */
  888. int rfirst, /* index of first record to log */
  889. int rlast) /* index of last record to log */
  890. {
  891. xfs_alloc_block_t *block; /* btree block to log from */
  892. int first; /* first byte offset logged */
  893. int last; /* last byte offset logged */
  894. xfs_alloc_rec_t *rp; /* record pointer for btree block */
  895. block = XFS_BUF_TO_ALLOC_BLOCK(bp);
  896. rp = XFS_ALLOC_REC_ADDR(block, 1, cur);
  897. #ifdef DEBUG
  898. {
  899. xfs_agf_t *agf;
  900. xfs_alloc_rec_t *p;
  901. agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
  902. for (p = &rp[rfirst - 1]; p <= &rp[rlast - 1]; p++)
  903. ASSERT(be32_to_cpu(p->ar_startblock) +
  904. be32_to_cpu(p->ar_blockcount) <=
  905. be32_to_cpu(agf->agf_length));
  906. }
  907. #endif
  908. first = (int)((xfs_caddr_t)&rp[rfirst - 1] - (xfs_caddr_t)block);
  909. last = (int)(((xfs_caddr_t)&rp[rlast] - 1) - (xfs_caddr_t)block);
  910. xfs_trans_log_buf(cur->bc_tp, bp, first, last);
  911. }
  912. /*
  913. * Lookup the record. The cursor is made to point to it, based on dir.
  914. * Return 0 if can't find any such record, 1 for success.
  915. */
  916. STATIC int /* error */
  917. xfs_alloc_lookup(
  918. xfs_btree_cur_t *cur, /* btree cursor */
  919. xfs_lookup_t dir, /* <=, ==, or >= */
  920. int *stat) /* success/failure */
  921. {
  922. xfs_agblock_t agbno; /* a.g. relative btree block number */
  923. xfs_agnumber_t agno; /* allocation group number */
  924. xfs_alloc_block_t *block=NULL; /* current btree block */
  925. int diff; /* difference for the current key */
  926. int error; /* error return value */
  927. int keyno=0; /* current key number */
  928. int level; /* level in the btree */
  929. xfs_mount_t *mp; /* file system mount point */
  930. XFS_STATS_INC(xs_abt_lookup);
  931. /*
  932. * Get the allocation group header, and the root block number.
  933. */
  934. mp = cur->bc_mp;
  935. {
  936. xfs_agf_t *agf; /* a.g. freespace header */
  937. agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
  938. agno = be32_to_cpu(agf->agf_seqno);
  939. agbno = be32_to_cpu(agf->agf_roots[cur->bc_btnum]);
  940. }
  941. /*
  942. * Iterate over each level in the btree, starting at the root.
  943. * For each level above the leaves, find the key we need, based
  944. * on the lookup record, then follow the corresponding block
  945. * pointer down to the next level.
  946. */
  947. for (level = cur->bc_nlevels - 1, diff = 1; level >= 0; level--) {
  948. xfs_buf_t *bp; /* buffer pointer for btree block */
  949. xfs_daddr_t d; /* disk address of btree block */
  950. /*
  951. * Get the disk address we're looking for.
  952. */
  953. d = XFS_AGB_TO_DADDR(mp, agno, agbno);
  954. /*
  955. * If the old buffer at this level is for a different block,
  956. * throw it away, otherwise just use it.
  957. */
  958. bp = cur->bc_bufs[level];
  959. if (bp && XFS_BUF_ADDR(bp) != d)
  960. bp = NULL;
  961. if (!bp) {
  962. /*
  963. * Need to get a new buffer. Read it, then
  964. * set it in the cursor, releasing the old one.
  965. */
  966. if ((error = xfs_btree_read_bufs(mp, cur->bc_tp, agno,
  967. agbno, 0, &bp, XFS_ALLOC_BTREE_REF)))
  968. return error;
  969. xfs_btree_setbuf(cur, level, bp);
  970. /*
  971. * Point to the btree block, now that we have the buffer
  972. */
  973. block = XFS_BUF_TO_ALLOC_BLOCK(bp);
  974. if ((error = xfs_btree_check_sblock(cur, block, level,
  975. bp)))
  976. return error;
  977. } else
  978. block = XFS_BUF_TO_ALLOC_BLOCK(bp);
  979. /*
  980. * If we already had a key match at a higher level, we know
  981. * we need to use the first entry in this block.
  982. */
  983. if (diff == 0)
  984. keyno = 1;
  985. /*
  986. * Otherwise we need to search this block. Do a binary search.
  987. */
  988. else {
  989. int high; /* high entry number */
  990. xfs_alloc_key_t *kkbase=NULL;/* base of keys in block */
  991. xfs_alloc_rec_t *krbase=NULL;/* base of records in block */
  992. int low; /* low entry number */
  993. /*
  994. * Get a pointer to keys or records.
  995. */
  996. if (level > 0)
  997. kkbase = XFS_ALLOC_KEY_ADDR(block, 1, cur);
  998. else
  999. krbase = XFS_ALLOC_REC_ADDR(block, 1, cur);
  1000. /*
  1001. * Set low and high entry numbers, 1-based.
  1002. */
  1003. low = 1;
  1004. if (!(high = be16_to_cpu(block->bb_numrecs))) {
  1005. /*
  1006. * If the block is empty, the tree must
  1007. * be an empty leaf.
  1008. */
  1009. ASSERT(level == 0 && cur->bc_nlevels == 1);
  1010. cur->bc_ptrs[0] = dir != XFS_LOOKUP_LE;
  1011. *stat = 0;
  1012. return 0;
  1013. }
  1014. /*
  1015. * Binary search the block.
  1016. */
  1017. while (low <= high) {
  1018. xfs_extlen_t blockcount; /* key value */
  1019. xfs_agblock_t startblock; /* key value */
  1020. XFS_STATS_INC(xs_abt_compare);
  1021. /*
  1022. * keyno is average of low and high.
  1023. */
  1024. keyno = (low + high) >> 1;
  1025. /*
  1026. * Get startblock & blockcount.
  1027. */
  1028. if (level > 0) {
  1029. xfs_alloc_key_t *kkp;
  1030. kkp = kkbase + keyno - 1;
  1031. startblock = be32_to_cpu(kkp->ar_startblock);
  1032. blockcount = be32_to_cpu(kkp->ar_blockcount);
  1033. } else {
  1034. xfs_alloc_rec_t *krp;
  1035. krp = krbase + keyno - 1;
  1036. startblock = be32_to_cpu(krp->ar_startblock);
  1037. blockcount = be32_to_cpu(krp->ar_blockcount);
  1038. }
  1039. /*
  1040. * Compute difference to get next direction.
  1041. */
  1042. if (cur->bc_btnum == XFS_BTNUM_BNO)
  1043. diff = (int)startblock -
  1044. (int)cur->bc_rec.a.ar_startblock;
  1045. else if (!(diff = (int)blockcount -
  1046. (int)cur->bc_rec.a.ar_blockcount))
  1047. diff = (int)startblock -
  1048. (int)cur->bc_rec.a.ar_startblock;
  1049. /*
  1050. * Less than, move right.
  1051. */
  1052. if (diff < 0)
  1053. low = keyno + 1;
  1054. /*
  1055. * Greater than, move left.
  1056. */
  1057. else if (diff > 0)
  1058. high = keyno - 1;
  1059. /*
  1060. * Equal, we're done.
  1061. */
  1062. else
  1063. break;
  1064. }
  1065. }
  1066. /*
  1067. * If there are more levels, set up for the next level
  1068. * by getting the block number and filling in the cursor.
  1069. */
  1070. if (level > 0) {
  1071. /*
  1072. * If we moved left, need the previous key number,
  1073. * unless there isn't one.
  1074. */
  1075. if (diff > 0 && --keyno < 1)
  1076. keyno = 1;
  1077. agbno = be32_to_cpu(*XFS_ALLOC_PTR_ADDR(block, keyno, cur));
  1078. #ifdef DEBUG
  1079. if ((error = xfs_btree_check_sptr(cur, agbno, level)))
  1080. return error;
  1081. #endif
  1082. cur->bc_ptrs[level] = keyno;
  1083. }
  1084. }
  1085. /*
  1086. * Done with the search.
  1087. * See if we need to adjust the results.
  1088. */
  1089. if (dir != XFS_LOOKUP_LE && diff < 0) {
  1090. keyno++;
  1091. /*
  1092. * If ge search and we went off the end of the block, but it's
  1093. * not the last block, we're in the wrong block.
  1094. */
  1095. if (dir == XFS_LOOKUP_GE &&
  1096. keyno > be16_to_cpu(block->bb_numrecs) &&
  1097. be32_to_cpu(block->bb_rightsib) != NULLAGBLOCK) {
  1098. int i;
  1099. cur->bc_ptrs[0] = keyno;
  1100. if ((error = xfs_alloc_increment(cur, 0, &i)))
  1101. return error;
  1102. XFS_WANT_CORRUPTED_RETURN(i == 1);
  1103. *stat = 1;
  1104. return 0;
  1105. }
  1106. }
  1107. else if (dir == XFS_LOOKUP_LE && diff > 0)
  1108. keyno--;
  1109. cur->bc_ptrs[0] = keyno;
  1110. /*
  1111. * Return if we succeeded or not.
  1112. */
  1113. if (keyno == 0 || keyno > be16_to_cpu(block->bb_numrecs))
  1114. *stat = 0;
  1115. else
  1116. *stat = ((dir != XFS_LOOKUP_EQ) || (diff == 0));
  1117. return 0;
  1118. }
  1119. /*
  1120. * Move 1 record left from cur/level if possible.
  1121. * Update cur to reflect the new path.
  1122. */
  1123. STATIC int /* error */
  1124. xfs_alloc_lshift(
  1125. xfs_btree_cur_t *cur, /* btree cursor */
  1126. int level, /* level to shift record on */
  1127. int *stat) /* success/failure */
  1128. {
  1129. int error; /* error return value */
  1130. #ifdef DEBUG
  1131. int i; /* loop index */
  1132. #endif
  1133. xfs_alloc_key_t key; /* key value for leaf level upward */
  1134. xfs_buf_t *lbp; /* buffer for left neighbor block */
  1135. xfs_alloc_block_t *left; /* left neighbor btree block */
  1136. int nrec; /* new number of left block entries */
  1137. xfs_buf_t *rbp; /* buffer for right (current) block */
  1138. xfs_alloc_block_t *right; /* right (current) btree block */
  1139. xfs_alloc_key_t *rkp=NULL; /* key pointer for right block */
  1140. xfs_alloc_ptr_t *rpp=NULL; /* address pointer for right block */
  1141. xfs_alloc_rec_t *rrp=NULL; /* record pointer for right block */
  1142. /*
  1143. * Set up variables for this block as "right".
  1144. */
  1145. rbp = cur->bc_bufs[level];
  1146. right = XFS_BUF_TO_ALLOC_BLOCK(rbp);
  1147. #ifdef DEBUG
  1148. if ((error = xfs_btree_check_sblock(cur, right, level, rbp)))
  1149. return error;
  1150. #endif
  1151. /*
  1152. * If we've got no left sibling then we can't shift an entry left.
  1153. */
  1154. if (be32_to_cpu(right->bb_leftsib) == NULLAGBLOCK) {
  1155. *stat = 0;
  1156. return 0;
  1157. }
  1158. /*
  1159. * If the cursor entry is the one that would be moved, don't
  1160. * do it... it's too complicated.
  1161. */
  1162. if (cur->bc_ptrs[level] <= 1) {
  1163. *stat = 0;
  1164. return 0;
  1165. }
  1166. /*
  1167. * Set up the left neighbor as "left".
  1168. */
  1169. if ((error = xfs_btree_read_bufs(cur->bc_mp, cur->bc_tp,
  1170. cur->bc_private.a.agno, be32_to_cpu(right->bb_leftsib),
  1171. 0, &lbp, XFS_ALLOC_BTREE_REF)))
  1172. return error;
  1173. left = XFS_BUF_TO_ALLOC_BLOCK(lbp);
  1174. if ((error = xfs_btree_check_sblock(cur, left, level, lbp)))
  1175. return error;
  1176. /*
  1177. * If it's full, it can't take another entry.
  1178. */
  1179. if (be16_to_cpu(left->bb_numrecs) == XFS_ALLOC_BLOCK_MAXRECS(level, cur)) {
  1180. *stat = 0;
  1181. return 0;
  1182. }
  1183. nrec = be16_to_cpu(left->bb_numrecs) + 1;
  1184. /*
  1185. * If non-leaf, copy a key and a ptr to the left block.
  1186. */
  1187. if (level > 0) {
  1188. xfs_alloc_key_t *lkp; /* key pointer for left block */
  1189. xfs_alloc_ptr_t *lpp; /* address pointer for left block */
  1190. lkp = XFS_ALLOC_KEY_ADDR(left, nrec, cur);
  1191. rkp = XFS_ALLOC_KEY_ADDR(right, 1, cur);
  1192. *lkp = *rkp;
  1193. xfs_alloc_log_keys(cur, lbp, nrec, nrec);
  1194. lpp = XFS_ALLOC_PTR_ADDR(left, nrec, cur);
  1195. rpp = XFS_ALLOC_PTR_ADDR(right, 1, cur);
  1196. #ifdef DEBUG
  1197. if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(*rpp), level)))
  1198. return error;
  1199. #endif
  1200. *lpp = *rpp;
  1201. xfs_alloc_log_ptrs(cur, lbp, nrec, nrec);
  1202. xfs_btree_check_key(cur->bc_btnum, lkp - 1, lkp);
  1203. }
  1204. /*
  1205. * If leaf, copy a record to the left block.
  1206. */
  1207. else {
  1208. xfs_alloc_rec_t *lrp; /* record pointer for left block */
  1209. lrp = XFS_ALLOC_REC_ADDR(left, nrec, cur);
  1210. rrp = XFS_ALLOC_REC_ADDR(right, 1, cur);
  1211. *lrp = *rrp;
  1212. xfs_alloc_log_recs(cur, lbp, nrec, nrec);
  1213. xfs_btree_check_rec(cur->bc_btnum, lrp - 1, lrp);
  1214. }
  1215. /*
  1216. * Bump and log left's numrecs, decrement and log right's numrecs.
  1217. */
  1218. be16_add(&left->bb_numrecs, 1);
  1219. xfs_alloc_log_block(cur->bc_tp, lbp, XFS_BB_NUMRECS);
  1220. be16_add(&right->bb_numrecs, -1);
  1221. xfs_alloc_log_block(cur->bc_tp, rbp, XFS_BB_NUMRECS);
  1222. /*
  1223. * Slide the contents of right down one entry.
  1224. */
  1225. if (level > 0) {
  1226. #ifdef DEBUG
  1227. for (i = 0; i < be16_to_cpu(right->bb_numrecs); i++) {
  1228. if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(rpp[i + 1]),
  1229. level)))
  1230. return error;
  1231. }
  1232. #endif
  1233. memmove(rkp, rkp + 1, be16_to_cpu(right->bb_numrecs) * sizeof(*rkp));
  1234. memmove(rpp, rpp + 1, be16_to_cpu(right->bb_numrecs) * sizeof(*rpp));
  1235. xfs_alloc_log_keys(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
  1236. xfs_alloc_log_ptrs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
  1237. } else {
  1238. memmove(rrp, rrp + 1, be16_to_cpu(right->bb_numrecs) * sizeof(*rrp));
  1239. xfs_alloc_log_recs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
  1240. key.ar_startblock = rrp->ar_startblock;
  1241. key.ar_blockcount = rrp->ar_blockcount;
  1242. rkp = &key;
  1243. }
  1244. /*
  1245. * Update the parent key values of right.
  1246. */
  1247. if ((error = xfs_alloc_updkey(cur, rkp, level + 1)))
  1248. return error;
  1249. /*
  1250. * Slide the cursor value left one.
  1251. */
  1252. cur->bc_ptrs[level]--;
  1253. *stat = 1;
  1254. return 0;
  1255. }
  1256. /*
  1257. * Allocate a new root block, fill it in.
  1258. */
  1259. STATIC int /* error */
  1260. xfs_alloc_newroot(
  1261. xfs_btree_cur_t *cur, /* btree cursor */
  1262. int *stat) /* success/failure */
  1263. {
  1264. int error; /* error return value */
  1265. xfs_agblock_t lbno; /* left block number */
  1266. xfs_buf_t *lbp; /* left btree buffer */
  1267. xfs_alloc_block_t *left; /* left btree block */
  1268. xfs_mount_t *mp; /* mount structure */
  1269. xfs_agblock_t nbno; /* new block number */
  1270. xfs_buf_t *nbp; /* new (root) buffer */
  1271. xfs_alloc_block_t *new; /* new (root) btree block */
  1272. int nptr; /* new value for key index, 1 or 2 */
  1273. xfs_agblock_t rbno; /* right block number */
  1274. xfs_buf_t *rbp; /* right btree buffer */
  1275. xfs_alloc_block_t *right; /* right btree block */
  1276. mp = cur->bc_mp;
  1277. ASSERT(cur->bc_nlevels < XFS_AG_MAXLEVELS(mp));
  1278. /*
  1279. * Get a buffer from the freelist blocks, for the new root.
  1280. */
  1281. if ((error = xfs_alloc_get_freelist(cur->bc_tp, cur->bc_private.a.agbp,
  1282. &nbno)))
  1283. return error;
  1284. /*
  1285. * None available, we fail.
  1286. */
  1287. if (nbno == NULLAGBLOCK) {
  1288. *stat = 0;
  1289. return 0;
  1290. }
  1291. xfs_trans_agbtree_delta(cur->bc_tp, 1);
  1292. nbp = xfs_btree_get_bufs(mp, cur->bc_tp, cur->bc_private.a.agno, nbno,
  1293. 0);
  1294. new = XFS_BUF_TO_ALLOC_BLOCK(nbp);
  1295. /*
  1296. * Set the root data in the a.g. freespace structure.
  1297. */
  1298. {
  1299. xfs_agf_t *agf; /* a.g. freespace header */
  1300. xfs_agnumber_t seqno;
  1301. agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
  1302. agf->agf_roots[cur->bc_btnum] = cpu_to_be32(nbno);
  1303. be32_add(&agf->agf_levels[cur->bc_btnum], 1);
  1304. seqno = be32_to_cpu(agf->agf_seqno);
  1305. mp->m_perag[seqno].pagf_levels[cur->bc_btnum]++;
  1306. xfs_alloc_log_agf(cur->bc_tp, cur->bc_private.a.agbp,
  1307. XFS_AGF_ROOTS | XFS_AGF_LEVELS);
  1308. }
  1309. /*
  1310. * At the previous root level there are now two blocks: the old
  1311. * root, and the new block generated when it was split.
  1312. * We don't know which one the cursor is pointing at, so we
  1313. * set up variables "left" and "right" for each case.
  1314. */
  1315. lbp = cur->bc_bufs[cur->bc_nlevels - 1];
  1316. left = XFS_BUF_TO_ALLOC_BLOCK(lbp);
  1317. #ifdef DEBUG
  1318. if ((error = xfs_btree_check_sblock(cur, left, cur->bc_nlevels - 1, lbp)))
  1319. return error;
  1320. #endif
  1321. if (be32_to_cpu(left->bb_rightsib) != NULLAGBLOCK) {
  1322. /*
  1323. * Our block is left, pick up the right block.
  1324. */
  1325. lbno = XFS_DADDR_TO_AGBNO(mp, XFS_BUF_ADDR(lbp));
  1326. rbno = be32_to_cpu(left->bb_rightsib);
  1327. if ((error = xfs_btree_read_bufs(mp, cur->bc_tp,
  1328. cur->bc_private.a.agno, rbno, 0, &rbp,
  1329. XFS_ALLOC_BTREE_REF)))
  1330. return error;
  1331. right = XFS_BUF_TO_ALLOC_BLOCK(rbp);
  1332. if ((error = xfs_btree_check_sblock(cur, right,
  1333. cur->bc_nlevels - 1, rbp)))
  1334. return error;
  1335. nptr = 1;
  1336. } else {
  1337. /*
  1338. * Our block is right, pick up the left block.
  1339. */
  1340. rbp = lbp;
  1341. right = left;
  1342. rbno = XFS_DADDR_TO_AGBNO(mp, XFS_BUF_ADDR(rbp));
  1343. lbno = be32_to_cpu(right->bb_leftsib);
  1344. if ((error = xfs_btree_read_bufs(mp, cur->bc_tp,
  1345. cur->bc_private.a.agno, lbno, 0, &lbp,
  1346. XFS_ALLOC_BTREE_REF)))
  1347. return error;
  1348. left = XFS_BUF_TO_ALLOC_BLOCK(lbp);
  1349. if ((error = xfs_btree_check_sblock(cur, left,
  1350. cur->bc_nlevels - 1, lbp)))
  1351. return error;
  1352. nptr = 2;
  1353. }
  1354. /*
  1355. * Fill in the new block's btree header and log it.
  1356. */
  1357. new->bb_magic = cpu_to_be32(xfs_magics[cur->bc_btnum]);
  1358. new->bb_level = cpu_to_be16(cur->bc_nlevels);
  1359. new->bb_numrecs = cpu_to_be16(2);
  1360. new->bb_leftsib = cpu_to_be32(NULLAGBLOCK);
  1361. new->bb_rightsib = cpu_to_be32(NULLAGBLOCK);
  1362. xfs_alloc_log_block(cur->bc_tp, nbp, XFS_BB_ALL_BITS);
  1363. ASSERT(lbno != NULLAGBLOCK && rbno != NULLAGBLOCK);
  1364. /*
  1365. * Fill in the key data in the new root.
  1366. */
  1367. {
  1368. xfs_alloc_key_t *kp; /* btree key pointer */
  1369. kp = XFS_ALLOC_KEY_ADDR(new, 1, cur);
  1370. if (be16_to_cpu(left->bb_level) > 0) {
  1371. kp[0] = *XFS_ALLOC_KEY_ADDR(left, 1, cur);
  1372. kp[1] = *XFS_ALLOC_KEY_ADDR(right, 1, cur);
  1373. } else {
  1374. xfs_alloc_rec_t *rp; /* btree record pointer */
  1375. rp = XFS_ALLOC_REC_ADDR(left, 1, cur);
  1376. kp[0].ar_startblock = rp->ar_startblock;
  1377. kp[0].ar_blockcount = rp->ar_blockcount;
  1378. rp = XFS_ALLOC_REC_ADDR(right, 1, cur);
  1379. kp[1].ar_startblock = rp->ar_startblock;
  1380. kp[1].ar_blockcount = rp->ar_blockcount;
  1381. }
  1382. }
  1383. xfs_alloc_log_keys(cur, nbp, 1, 2);
  1384. /*
  1385. * Fill in the pointer data in the new root.
  1386. */
  1387. {
  1388. xfs_alloc_ptr_t *pp; /* btree address pointer */
  1389. pp = XFS_ALLOC_PTR_ADDR(new, 1, cur);
  1390. pp[0] = cpu_to_be32(lbno);
  1391. pp[1] = cpu_to_be32(rbno);
  1392. }
  1393. xfs_alloc_log_ptrs(cur, nbp, 1, 2);
  1394. /*
  1395. * Fix up the cursor.
  1396. */
  1397. xfs_btree_setbuf(cur, cur->bc_nlevels, nbp);
  1398. cur->bc_ptrs[cur->bc_nlevels] = nptr;
  1399. cur->bc_nlevels++;
  1400. *stat = 1;
  1401. return 0;
  1402. }
  1403. /*
  1404. * Move 1 record right from cur/level if possible.
  1405. * Update cur to reflect the new path.
  1406. */
  1407. STATIC int /* error */
  1408. xfs_alloc_rshift(
  1409. xfs_btree_cur_t *cur, /* btree cursor */
  1410. int level, /* level to shift record on */
  1411. int *stat) /* success/failure */
  1412. {
  1413. int error; /* error return value */
  1414. int i; /* loop index */
  1415. xfs_alloc_key_t key; /* key value for leaf level upward */
  1416. xfs_buf_t *lbp; /* buffer for left (current) block */
  1417. xfs_alloc_block_t *left; /* left (current) btree block */
  1418. xfs_buf_t *rbp; /* buffer for right neighbor block */
  1419. xfs_alloc_block_t *right; /* right neighbor btree block */
  1420. xfs_alloc_key_t *rkp; /* key pointer for right block */
  1421. xfs_btree_cur_t *tcur; /* temporary cursor */
  1422. /*
  1423. * Set up variables for this block as "left".
  1424. */
  1425. lbp = cur->bc_bufs[level];
  1426. left = XFS_BUF_TO_ALLOC_BLOCK(lbp);
  1427. #ifdef DEBUG
  1428. if ((error = xfs_btree_check_sblock(cur, left, level, lbp)))
  1429. return error;
  1430. #endif
  1431. /*
  1432. * If we've got no right sibling then we can't shift an entry right.
  1433. */
  1434. if (be32_to_cpu(left->bb_rightsib) == NULLAGBLOCK) {
  1435. *stat = 0;
  1436. return 0;
  1437. }
  1438. /*
  1439. * If the cursor entry is the one that would be moved, don't
  1440. * do it... it's too complicated.
  1441. */
  1442. if (cur->bc_ptrs[level] >= be16_to_cpu(left->bb_numrecs)) {
  1443. *stat = 0;
  1444. return 0;
  1445. }
  1446. /*
  1447. * Set up the right neighbor as "right".
  1448. */
  1449. if ((error = xfs_btree_read_bufs(cur->bc_mp, cur->bc_tp,
  1450. cur->bc_private.a.agno, be32_to_cpu(left->bb_rightsib),
  1451. 0, &rbp, XFS_ALLOC_BTREE_REF)))
  1452. return error;
  1453. right = XFS_BUF_TO_ALLOC_BLOCK(rbp);
  1454. if ((error = xfs_btree_check_sblock(cur, right, level, rbp)))
  1455. return error;
  1456. /*
  1457. * If it's full, it can't take another entry.
  1458. */
  1459. if (be16_to_cpu(right->bb_numrecs) == XFS_ALLOC_BLOCK_MAXRECS(level, cur)) {
  1460. *stat = 0;
  1461. return 0;
  1462. }
  1463. /*
  1464. * Make a hole at the start of the right neighbor block, then
  1465. * copy the last left block entry to the hole.
  1466. */
  1467. if (level > 0) {
  1468. xfs_alloc_key_t *lkp; /* key pointer for left block */
  1469. xfs_alloc_ptr_t *lpp; /* address pointer for left block */
  1470. xfs_alloc_ptr_t *rpp; /* address pointer for right block */
  1471. lkp = XFS_ALLOC_KEY_ADDR(left, be16_to_cpu(left->bb_numrecs), cur);
  1472. lpp = XFS_ALLOC_PTR_ADDR(left, be16_to_cpu(left->bb_numrecs), cur);
  1473. rkp = XFS_ALLOC_KEY_ADDR(right, 1, cur);
  1474. rpp = XFS_ALLOC_PTR_ADDR(right, 1, cur);
  1475. #ifdef DEBUG
  1476. for (i = be16_to_cpu(right->bb_numrecs) - 1; i >= 0; i--) {
  1477. if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(rpp[i]), level)))
  1478. return error;
  1479. }
  1480. #endif
  1481. memmove(rkp + 1, rkp, be16_to_cpu(right->bb_numrecs) * sizeof(*rkp));
  1482. memmove(rpp + 1, rpp, be16_to_cpu(right->bb_numrecs) * sizeof(*rpp));
  1483. #ifdef DEBUG
  1484. if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(*lpp), level)))
  1485. return error;
  1486. #endif
  1487. *rkp = *lkp;
  1488. *rpp = *lpp;
  1489. xfs_alloc_log_keys(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1);
  1490. xfs_alloc_log_ptrs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1);
  1491. xfs_btree_check_key(cur->bc_btnum, rkp, rkp + 1);
  1492. } else {
  1493. xfs_alloc_rec_t *lrp; /* record pointer for left block */
  1494. xfs_alloc_rec_t *rrp; /* record pointer for right block */
  1495. lrp = XFS_ALLOC_REC_ADDR(left, be16_to_cpu(left->bb_numrecs), cur);
  1496. rrp = XFS_ALLOC_REC_ADDR(right, 1, cur);
  1497. memmove(rrp + 1, rrp, be16_to_cpu(right->bb_numrecs) * sizeof(*rrp));
  1498. *rrp = *lrp;
  1499. xfs_alloc_log_recs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1);
  1500. key.ar_startblock = rrp->ar_startblock;
  1501. key.ar_blockcount = rrp->ar_blockcount;
  1502. rkp = &key;
  1503. xfs_btree_check_rec(cur->bc_btnum, rrp, rrp + 1);
  1504. }
  1505. /*
  1506. * Decrement and log left's numrecs, bump and log right's numrecs.
  1507. */
  1508. be16_add(&left->bb_numrecs, -1);
  1509. xfs_alloc_log_block(cur->bc_tp, lbp, XFS_BB_NUMRECS);
  1510. be16_add(&right->bb_numrecs, 1);
  1511. xfs_alloc_log_block(cur->bc_tp, rbp, XFS_BB_NUMRECS);
  1512. /*
  1513. * Using a temporary cursor, update the parent key values of the
  1514. * block on the right.
  1515. */
  1516. if ((error = xfs_btree_dup_cursor(cur, &tcur)))
  1517. return error;
  1518. i = xfs_btree_lastrec(tcur, level);
  1519. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  1520. if ((error = xfs_alloc_increment(tcur, level, &i)) ||
  1521. (error = xfs_alloc_updkey(tcur, rkp, level + 1)))
  1522. goto error0;
  1523. xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
  1524. *stat = 1;
  1525. return 0;
  1526. error0:
  1527. xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
  1528. return error;
  1529. }
  1530. /*
  1531. * Split cur/level block in half.
  1532. * Return new block number and its first record (to be inserted into parent).
  1533. */
  1534. STATIC int /* error */
  1535. xfs_alloc_split(
  1536. xfs_btree_cur_t *cur, /* btree cursor */
  1537. int level, /* level to split */
  1538. xfs_agblock_t *bnop, /* output: block number allocated */
  1539. xfs_alloc_key_t *keyp, /* output: first key of new block */
  1540. xfs_btree_cur_t **curp, /* output: new cursor */
  1541. int *stat) /* success/failure */
  1542. {
  1543. int error; /* error return value */
  1544. int i; /* loop index/record number */
  1545. xfs_agblock_t lbno; /* left (current) block number */
  1546. xfs_buf_t *lbp; /* buffer for left block */
  1547. xfs_alloc_block_t *left; /* left (current) btree block */
  1548. xfs_agblock_t rbno; /* right (new) block number */
  1549. xfs_buf_t *rbp; /* buffer for right block */
  1550. xfs_alloc_block_t *right; /* right (new) btree block */
  1551. /*
  1552. * Allocate the new block from the freelist.
  1553. * If we can't do it, we're toast. Give up.
  1554. */
  1555. if ((error = xfs_alloc_get_freelist(cur->bc_tp, cur->bc_private.a.agbp,
  1556. &rbno)))
  1557. return error;
  1558. if (rbno == NULLAGBLOCK) {
  1559. *stat = 0;
  1560. return 0;
  1561. }
  1562. xfs_trans_agbtree_delta(cur->bc_tp, 1);
  1563. rbp = xfs_btree_get_bufs(cur->bc_mp, cur->bc_tp, cur->bc_private.a.agno,
  1564. rbno, 0);
  1565. /*
  1566. * Set up the new block as "right".
  1567. */
  1568. right = XFS_BUF_TO_ALLOC_BLOCK(rbp);
  1569. /*
  1570. * "Left" is the current (according to the cursor) block.
  1571. */
  1572. lbp = cur->bc_bufs[level];
  1573. left = XFS_BUF_TO_ALLOC_BLOCK(lbp);
  1574. #ifdef DEBUG
  1575. if ((error = xfs_btree_check_sblock(cur, left, level, lbp)))
  1576. return error;
  1577. #endif
  1578. /*
  1579. * Fill in the btree header for the new block.
  1580. */
  1581. right->bb_magic = cpu_to_be32(xfs_magics[cur->bc_btnum]);
  1582. right->bb_level = left->bb_level;
  1583. right->bb_numrecs = cpu_to_be16(be16_to_cpu(left->bb_numrecs) / 2);
  1584. /*
  1585. * Make sure that if there's an odd number of entries now, that
  1586. * each new block will have the same number of entries.
  1587. */
  1588. if ((be16_to_cpu(left->bb_numrecs) & 1) &&
  1589. cur->bc_ptrs[level] <= be16_to_cpu(right->bb_numrecs) + 1)
  1590. be16_add(&right->bb_numrecs, 1);
  1591. i = be16_to_cpu(left->bb_numrecs) - be16_to_cpu(right->bb_numrecs) + 1;
  1592. /*
  1593. * For non-leaf blocks, copy keys and addresses over to the new block.
  1594. */
  1595. if (level > 0) {
  1596. xfs_alloc_key_t *lkp; /* left btree key pointer */
  1597. xfs_alloc_ptr_t *lpp; /* left btree address pointer */
  1598. xfs_alloc_key_t *rkp; /* right btree key pointer */
  1599. xfs_alloc_ptr_t *rpp; /* right btree address pointer */
  1600. lkp = XFS_ALLOC_KEY_ADDR(left, i, cur);
  1601. lpp = XFS_ALLOC_PTR_ADDR(left, i, cur);
  1602. rkp = XFS_ALLOC_KEY_ADDR(right, 1, cur);
  1603. rpp = XFS_ALLOC_PTR_ADDR(right, 1, cur);
  1604. #ifdef DEBUG
  1605. for (i = 0; i < be16_to_cpu(right->bb_numrecs); i++) {
  1606. if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(lpp[i]), level)))
  1607. return error;
  1608. }
  1609. #endif
  1610. memcpy(rkp, lkp, be16_to_cpu(right->bb_numrecs) * sizeof(*rkp));
  1611. memcpy(rpp, lpp, be16_to_cpu(right->bb_numrecs) * sizeof(*rpp));
  1612. xfs_alloc_log_keys(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
  1613. xfs_alloc_log_ptrs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
  1614. *keyp = *rkp;
  1615. }
  1616. /*
  1617. * For leaf blocks, copy records over to the new block.
  1618. */
  1619. else {
  1620. xfs_alloc_rec_t *lrp; /* left btree record pointer */
  1621. xfs_alloc_rec_t *rrp; /* right btree record pointer */
  1622. lrp = XFS_ALLOC_REC_ADDR(left, i, cur);
  1623. rrp = XFS_ALLOC_REC_ADDR(right, 1, cur);
  1624. memcpy(rrp, lrp, be16_to_cpu(right->bb_numrecs) * sizeof(*rrp));
  1625. xfs_alloc_log_recs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
  1626. keyp->ar_startblock = rrp->ar_startblock;
  1627. keyp->ar_blockcount = rrp->ar_blockcount;
  1628. }
  1629. /*
  1630. * Find the left block number by looking in the buffer.
  1631. * Adjust numrecs, sibling pointers.
  1632. */
  1633. lbno = XFS_DADDR_TO_AGBNO(cur->bc_mp, XFS_BUF_ADDR(lbp));
  1634. be16_add(&left->bb_numrecs, -(be16_to_cpu(right->bb_numrecs)));
  1635. right->bb_rightsib = left->bb_rightsib;
  1636. left->bb_rightsib = cpu_to_be32(rbno);
  1637. right->bb_leftsib = cpu_to_be32(lbno);
  1638. xfs_alloc_log_block(cur->bc_tp, rbp, XFS_BB_ALL_BITS);
  1639. xfs_alloc_log_block(cur->bc_tp, lbp, XFS_BB_NUMRECS | XFS_BB_RIGHTSIB);
  1640. /*
  1641. * If there's a block to the new block's right, make that block
  1642. * point back to right instead of to left.
  1643. */
  1644. if (be32_to_cpu(right->bb_rightsib) != NULLAGBLOCK) {
  1645. xfs_alloc_block_t *rrblock; /* rr btree block */
  1646. xfs_buf_t *rrbp; /* buffer for rrblock */
  1647. if ((error = xfs_btree_read_bufs(cur->bc_mp, cur->bc_tp,
  1648. cur->bc_private.a.agno, be32_to_cpu(right->bb_rightsib), 0,
  1649. &rrbp, XFS_ALLOC_BTREE_REF)))
  1650. return error;
  1651. rrblock = XFS_BUF_TO_ALLOC_BLOCK(rrbp);
  1652. if ((error = xfs_btree_check_sblock(cur, rrblock, level, rrbp)))
  1653. return error;
  1654. rrblock->bb_leftsib = cpu_to_be32(rbno);
  1655. xfs_alloc_log_block(cur->bc_tp, rrbp, XFS_BB_LEFTSIB);
  1656. }
  1657. /*
  1658. * If the cursor is really in the right block, move it there.
  1659. * If it's just pointing past the last entry in left, then we'll
  1660. * insert there, so don't change anything in that case.
  1661. */
  1662. if (cur->bc_ptrs[level] > be16_to_cpu(left->bb_numrecs) + 1) {
  1663. xfs_btree_setbuf(cur, level, rbp);
  1664. cur->bc_ptrs[level] -= be16_to_cpu(left->bb_numrecs);
  1665. }
  1666. /*
  1667. * If there are more levels, we'll need another cursor which refers to
  1668. * the right block, no matter where this cursor was.
  1669. */
  1670. if (level + 1 < cur->bc_nlevels) {
  1671. if ((error = xfs_btree_dup_cursor(cur, curp)))
  1672. return error;
  1673. (*curp)->bc_ptrs[level + 1]++;
  1674. }
  1675. *bnop = rbno;
  1676. *stat = 1;
  1677. return 0;
  1678. }
  1679. /*
  1680. * Update keys at all levels from here to the root along the cursor's path.
  1681. */
  1682. STATIC int /* error */
  1683. xfs_alloc_updkey(
  1684. xfs_btree_cur_t *cur, /* btree cursor */
  1685. xfs_alloc_key_t *keyp, /* new key value to update to */
  1686. int level) /* starting level for update */
  1687. {
  1688. int ptr; /* index of key in block */
  1689. /*
  1690. * Go up the tree from this level toward the root.
  1691. * At each level, update the key value to the value input.
  1692. * Stop when we reach a level where the cursor isn't pointing
  1693. * at the first entry in the block.
  1694. */
  1695. for (ptr = 1; ptr == 1 && level < cur->bc_nlevels; level++) {
  1696. xfs_alloc_block_t *block; /* btree block */
  1697. xfs_buf_t *bp; /* buffer for block */
  1698. #ifdef DEBUG
  1699. int error; /* error return value */
  1700. #endif
  1701. xfs_alloc_key_t *kp; /* ptr to btree block keys */
  1702. bp = cur->bc_bufs[level];
  1703. block = XFS_BUF_TO_ALLOC_BLOCK(bp);
  1704. #ifdef DEBUG
  1705. if ((error = xfs_btree_check_sblock(cur, block, level, bp)))
  1706. return error;
  1707. #endif
  1708. ptr = cur->bc_ptrs[level];
  1709. kp = XFS_ALLOC_KEY_ADDR(block, ptr, cur);
  1710. *kp = *keyp;
  1711. xfs_alloc_log_keys(cur, bp, ptr, ptr);
  1712. }
  1713. return 0;
  1714. }
  1715. /*
  1716. * Externally visible routines.
  1717. */
  1718. /*
  1719. * Decrement cursor by one record at the level.
  1720. * For nonzero levels the leaf-ward information is untouched.
  1721. */
  1722. int /* error */
  1723. xfs_alloc_decrement(
  1724. xfs_btree_cur_t *cur, /* btree cursor */
  1725. int level, /* level in btree, 0 is leaf */
  1726. int *stat) /* success/failure */
  1727. {
  1728. xfs_alloc_block_t *block; /* btree block */
  1729. int error; /* error return value */
  1730. int lev; /* btree level */
  1731. ASSERT(level < cur->bc_nlevels);
  1732. /*
  1733. * Read-ahead to the left at this level.
  1734. */
  1735. xfs_btree_readahead(cur, level, XFS_BTCUR_LEFTRA);
  1736. /*
  1737. * Decrement the ptr at this level. If we're still in the block
  1738. * then we're done.
  1739. */
  1740. if (--cur->bc_ptrs[level] > 0) {
  1741. *stat = 1;
  1742. return 0;
  1743. }
  1744. /*
  1745. * Get a pointer to the btree block.
  1746. */
  1747. block = XFS_BUF_TO_ALLOC_BLOCK(cur->bc_bufs[level]);
  1748. #ifdef DEBUG
  1749. if ((error = xfs_btree_check_sblock(cur, block, level,
  1750. cur->bc_bufs[level])))
  1751. return error;
  1752. #endif
  1753. /*
  1754. * If we just went off the left edge of the tree, return failure.
  1755. */
  1756. if (be32_to_cpu(block->bb_leftsib) == NULLAGBLOCK) {
  1757. *stat = 0;
  1758. return 0;
  1759. }
  1760. /*
  1761. * March up the tree decrementing pointers.
  1762. * Stop when we don't go off the left edge of a block.
  1763. */
  1764. for (lev = level + 1; lev < cur->bc_nlevels; lev++) {
  1765. if (--cur->bc_ptrs[lev] > 0)
  1766. break;
  1767. /*
  1768. * Read-ahead the left block, we're going to read it
  1769. * in the next loop.
  1770. */
  1771. xfs_btree_readahead(cur, lev, XFS_BTCUR_LEFTRA);
  1772. }
  1773. /*
  1774. * If we went off the root then we are seriously confused.
  1775. */
  1776. ASSERT(lev < cur->bc_nlevels);
  1777. /*
  1778. * Now walk back down the tree, fixing up the cursor's buffer
  1779. * pointers and key numbers.
  1780. */
  1781. for (block = XFS_BUF_TO_ALLOC_BLOCK(cur->bc_bufs[lev]); lev > level; ) {
  1782. xfs_agblock_t agbno; /* block number of btree block */
  1783. xfs_buf_t *bp; /* buffer pointer for block */
  1784. agbno = be32_to_cpu(*XFS_ALLOC_PTR_ADDR(block, cur->bc_ptrs[lev], cur));
  1785. if ((error = xfs_btree_read_bufs(cur->bc_mp, cur->bc_tp,
  1786. cur->bc_private.a.agno, agbno, 0, &bp,
  1787. XFS_ALLOC_BTREE_REF)))
  1788. return error;
  1789. lev--;
  1790. xfs_btree_setbuf(cur, lev, bp);
  1791. block = XFS_BUF_TO_ALLOC_BLOCK(bp);
  1792. if ((error = xfs_btree_check_sblock(cur, block, lev, bp)))
  1793. return error;
  1794. cur->bc_ptrs[lev] = be16_to_cpu(block->bb_numrecs);
  1795. }
  1796. *stat = 1;
  1797. return 0;
  1798. }
  1799. /*
  1800. * Delete the record pointed to by cur.
  1801. * The cursor refers to the place where the record was (could be inserted)
  1802. * when the operation returns.
  1803. */
  1804. int /* error */
  1805. xfs_alloc_delete(
  1806. xfs_btree_cur_t *cur, /* btree cursor */
  1807. int *stat) /* success/failure */
  1808. {
  1809. int error; /* error return value */
  1810. int i; /* result code */
  1811. int level; /* btree level */
  1812. /*
  1813. * Go up the tree, starting at leaf level.
  1814. * If 2 is returned then a join was done; go to the next level.
  1815. * Otherwise we are done.
  1816. */
  1817. for (level = 0, i = 2; i == 2; level++) {
  1818. if ((error = xfs_alloc_delrec(cur, level, &i)))
  1819. return error;
  1820. }
  1821. if (i == 0) {
  1822. for (level = 1; level < cur->bc_nlevels; level++) {
  1823. if (cur->bc_ptrs[level] == 0) {
  1824. if ((error = xfs_alloc_decrement(cur, level, &i)))
  1825. return error;
  1826. break;
  1827. }
  1828. }
  1829. }
  1830. *stat = i;
  1831. return 0;
  1832. }
  1833. /*
  1834. * Get the data from the pointed-to record.
  1835. */
  1836. int /* error */
  1837. xfs_alloc_get_rec(
  1838. xfs_btree_cur_t *cur, /* btree cursor */
  1839. xfs_agblock_t *bno, /* output: starting block of extent */
  1840. xfs_extlen_t *len, /* output: length of extent */
  1841. int *stat) /* output: success/failure */
  1842. {
  1843. xfs_alloc_block_t *block; /* btree block */
  1844. #ifdef DEBUG
  1845. int error; /* error return value */
  1846. #endif
  1847. int ptr; /* record number */
  1848. ptr = cur->bc_ptrs[0];
  1849. block = XFS_BUF_TO_ALLOC_BLOCK(cur->bc_bufs[0]);
  1850. #ifdef DEBUG
  1851. if ((error = xfs_btree_check_sblock(cur, block, 0, cur->bc_bufs[0])))
  1852. return error;
  1853. #endif
  1854. /*
  1855. * Off the right end or left end, return failure.
  1856. */
  1857. if (ptr > be16_to_cpu(block->bb_numrecs) || ptr <= 0) {
  1858. *stat = 0;
  1859. return 0;
  1860. }
  1861. /*
  1862. * Point to the record and extract its data.
  1863. */
  1864. {
  1865. xfs_alloc_rec_t *rec; /* record data */
  1866. rec = XFS_ALLOC_REC_ADDR(block, ptr, cur);
  1867. *bno = be32_to_cpu(rec->ar_startblock);
  1868. *len = be32_to_cpu(rec->ar_blockcount);
  1869. }
  1870. *stat = 1;
  1871. return 0;
  1872. }
  1873. /*
  1874. * Increment cursor by one record at the level.
  1875. * For nonzero levels the leaf-ward information is untouched.
  1876. */
  1877. int /* error */
  1878. xfs_alloc_increment(
  1879. xfs_btree_cur_t *cur, /* btree cursor */
  1880. int level, /* level in btree, 0 is leaf */
  1881. int *stat) /* success/failure */
  1882. {
  1883. xfs_alloc_block_t *block; /* btree block */
  1884. xfs_buf_t *bp; /* tree block buffer */
  1885. int error; /* error return value */
  1886. int lev; /* btree level */
  1887. ASSERT(level < cur->bc_nlevels);
  1888. /*
  1889. * Read-ahead to the right at this level.
  1890. */
  1891. xfs_btree_readahead(cur, level, XFS_BTCUR_RIGHTRA);
  1892. /*
  1893. * Get a pointer to the btree block.
  1894. */
  1895. bp = cur->bc_bufs[level];
  1896. block = XFS_BUF_TO_ALLOC_BLOCK(bp);
  1897. #ifdef DEBUG
  1898. if ((error = xfs_btree_check_sblock(cur, block, level, bp)))
  1899. return error;
  1900. #endif
  1901. /*
  1902. * Increment the ptr at this level. If we're still in the block
  1903. * then we're done.
  1904. */
  1905. if (++cur->bc_ptrs[level] <= be16_to_cpu(block->bb_numrecs)) {
  1906. *stat = 1;
  1907. return 0;
  1908. }
  1909. /*
  1910. * If we just went off the right edge of the tree, return failure.
  1911. */
  1912. if (be32_to_cpu(block->bb_rightsib) == NULLAGBLOCK) {
  1913. *stat = 0;
  1914. return 0;
  1915. }
  1916. /*
  1917. * March up the tree incrementing pointers.
  1918. * Stop when we don't go off the right edge of a block.
  1919. */
  1920. for (lev = level + 1; lev < cur->bc_nlevels; lev++) {
  1921. bp = cur->bc_bufs[lev];
  1922. block = XFS_BUF_TO_ALLOC_BLOCK(bp);
  1923. #ifdef DEBUG
  1924. if ((error = xfs_btree_check_sblock(cur, block, lev, bp)))
  1925. return error;
  1926. #endif
  1927. if (++cur->bc_ptrs[lev] <= be16_to_cpu(block->bb_numrecs))
  1928. break;
  1929. /*
  1930. * Read-ahead the right block, we're going to read it
  1931. * in the next loop.
  1932. */
  1933. xfs_btree_readahead(cur, lev, XFS_BTCUR_RIGHTRA);
  1934. }
  1935. /*
  1936. * If we went off the root then we are seriously confused.
  1937. */
  1938. ASSERT(lev < cur->bc_nlevels);
  1939. /*
  1940. * Now walk back down the tree, fixing up the cursor's buffer
  1941. * pointers and key numbers.
  1942. */
  1943. for (bp = cur->bc_bufs[lev], block = XFS_BUF_TO_ALLOC_BLOCK(bp);
  1944. lev > level; ) {
  1945. xfs_agblock_t agbno; /* block number of btree block */
  1946. agbno = be32_to_cpu(*XFS_ALLOC_PTR_ADDR(block, cur->bc_ptrs[lev], cur));
  1947. if ((error = xfs_btree_read_bufs(cur->bc_mp, cur->bc_tp,
  1948. cur->bc_private.a.agno, agbno, 0, &bp,
  1949. XFS_ALLOC_BTREE_REF)))
  1950. return error;
  1951. lev--;
  1952. xfs_btree_setbuf(cur, lev, bp);
  1953. block = XFS_BUF_TO_ALLOC_BLOCK(bp);
  1954. if ((error = xfs_btree_check_sblock(cur, block, lev, bp)))
  1955. return error;
  1956. cur->bc_ptrs[lev] = 1;
  1957. }
  1958. *stat = 1;
  1959. return 0;
  1960. }
  1961. /*
  1962. * Insert the current record at the point referenced by cur.
  1963. * The cursor may be inconsistent on return if splits have been done.
  1964. */
  1965. int /* error */
  1966. xfs_alloc_insert(
  1967. xfs_btree_cur_t *cur, /* btree cursor */
  1968. int *stat) /* success/failure */
  1969. {
  1970. int error; /* error return value */
  1971. int i; /* result value, 0 for failure */
  1972. int level; /* current level number in btree */
  1973. xfs_agblock_t nbno; /* new block number (split result) */
  1974. xfs_btree_cur_t *ncur; /* new cursor (split result) */
  1975. xfs_alloc_rec_t nrec; /* record being inserted this level */
  1976. xfs_btree_cur_t *pcur; /* previous level's cursor */
  1977. level = 0;
  1978. nbno = NULLAGBLOCK;
  1979. nrec.ar_startblock = cpu_to_be32(cur->bc_rec.a.ar_startblock);
  1980. nrec.ar_blockcount = cpu_to_be32(cur->bc_rec.a.ar_blockcount);
  1981. ncur = NULL;
  1982. pcur = cur;
  1983. /*
  1984. * Loop going up the tree, starting at the leaf level.
  1985. * Stop when we don't get a split block, that must mean that
  1986. * the insert is finished with this level.
  1987. */
  1988. do {
  1989. /*
  1990. * Insert nrec/nbno into this level of the tree.
  1991. * Note if we fail, nbno will be null.
  1992. */
  1993. if ((error = xfs_alloc_insrec(pcur, level++, &nbno, &nrec, &ncur,
  1994. &i))) {
  1995. if (pcur != cur)
  1996. xfs_btree_del_cursor(pcur, XFS_BTREE_ERROR);
  1997. return error;
  1998. }
  1999. /*
  2000. * See if the cursor we just used is trash.
  2001. * Can't trash the caller's cursor, but otherwise we should
  2002. * if ncur is a new cursor or we're about to be done.
  2003. */
  2004. if (pcur != cur && (ncur || nbno == NULLAGBLOCK)) {
  2005. cur->bc_nlevels = pcur->bc_nlevels;
  2006. xfs_btree_del_cursor(pcur, XFS_BTREE_NOERROR);
  2007. }
  2008. /*
  2009. * If we got a new cursor, switch to it.
  2010. */
  2011. if (ncur) {
  2012. pcur = ncur;
  2013. ncur = NULL;
  2014. }
  2015. } while (nbno != NULLAGBLOCK);
  2016. *stat = i;
  2017. return 0;
  2018. }
  2019. /*
  2020. * Lookup the record equal to [bno, len] in the btree given by cur.
  2021. */
  2022. int /* error */
  2023. xfs_alloc_lookup_eq(
  2024. xfs_btree_cur_t *cur, /* btree cursor */
  2025. xfs_agblock_t bno, /* starting block of extent */
  2026. xfs_extlen_t len, /* length of extent */
  2027. int *stat) /* success/failure */
  2028. {
  2029. cur->bc_rec.a.ar_startblock = bno;
  2030. cur->bc_rec.a.ar_blockcount = len;
  2031. return xfs_alloc_lookup(cur, XFS_LOOKUP_EQ, stat);
  2032. }
  2033. /*
  2034. * Lookup the first record greater than or equal to [bno, len]
  2035. * in the btree given by cur.
  2036. */
  2037. int /* error */
  2038. xfs_alloc_lookup_ge(
  2039. xfs_btree_cur_t *cur, /* btree cursor */
  2040. xfs_agblock_t bno, /* starting block of extent */
  2041. xfs_extlen_t len, /* length of extent */
  2042. int *stat) /* success/failure */
  2043. {
  2044. cur->bc_rec.a.ar_startblock = bno;
  2045. cur->bc_rec.a.ar_blockcount = len;
  2046. return xfs_alloc_lookup(cur, XFS_LOOKUP_GE, stat);
  2047. }
  2048. /*
  2049. * Lookup the first record less than or equal to [bno, len]
  2050. * in the btree given by cur.
  2051. */
  2052. int /* error */
  2053. xfs_alloc_lookup_le(
  2054. xfs_btree_cur_t *cur, /* btree cursor */
  2055. xfs_agblock_t bno, /* starting block of extent */
  2056. xfs_extlen_t len, /* length of extent */
  2057. int *stat) /* success/failure */
  2058. {
  2059. cur->bc_rec.a.ar_startblock = bno;
  2060. cur->bc_rec.a.ar_blockcount = len;
  2061. return xfs_alloc_lookup(cur, XFS_LOOKUP_LE, stat);
  2062. }
  2063. /*
  2064. * Update the record referred to by cur, to the value given by [bno, len].
  2065. * This either works (return 0) or gets an EFSCORRUPTED error.
  2066. */
  2067. int /* error */
  2068. xfs_alloc_update(
  2069. xfs_btree_cur_t *cur, /* btree cursor */
  2070. xfs_agblock_t bno, /* starting block of extent */
  2071. xfs_extlen_t len) /* length of extent */
  2072. {
  2073. xfs_alloc_block_t *block; /* btree block to update */
  2074. int error; /* error return value */
  2075. int ptr; /* current record number (updating) */
  2076. ASSERT(len > 0);
  2077. /*
  2078. * Pick up the a.g. freelist struct and the current block.
  2079. */
  2080. block = XFS_BUF_TO_ALLOC_BLOCK(cur->bc_bufs[0]);
  2081. #ifdef DEBUG
  2082. if ((error = xfs_btree_check_sblock(cur, block, 0, cur->bc_bufs[0])))
  2083. return error;
  2084. #endif
  2085. /*
  2086. * Get the address of the rec to be updated.
  2087. */
  2088. ptr = cur->bc_ptrs[0];
  2089. {
  2090. xfs_alloc_rec_t *rp; /* pointer to updated record */
  2091. rp = XFS_ALLOC_REC_ADDR(block, ptr, cur);
  2092. /*
  2093. * Fill in the new contents and log them.
  2094. */
  2095. rp->ar_startblock = cpu_to_be32(bno);
  2096. rp->ar_blockcount = cpu_to_be32(len);
  2097. xfs_alloc_log_recs(cur, cur->bc_bufs[0], ptr, ptr);
  2098. }
  2099. /*
  2100. * If it's the by-size btree and it's the last leaf block and
  2101. * it's the last record... then update the size of the longest
  2102. * extent in the a.g., which we cache in the a.g. freelist header.
  2103. */
  2104. if (cur->bc_btnum == XFS_BTNUM_CNT &&
  2105. be32_to_cpu(block->bb_rightsib) == NULLAGBLOCK &&
  2106. ptr == be16_to_cpu(block->bb_numrecs)) {
  2107. xfs_agf_t *agf; /* a.g. freespace header */
  2108. xfs_agnumber_t seqno;
  2109. agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
  2110. seqno = be32_to_cpu(agf->agf_seqno);
  2111. cur->bc_mp->m_perag[seqno].pagf_longest = len;
  2112. agf->agf_longest = cpu_to_be32(len);
  2113. xfs_alloc_log_agf(cur->bc_tp, cur->bc_private.a.agbp,
  2114. XFS_AGF_LONGEST);
  2115. }
  2116. /*
  2117. * Updating first record in leaf. Pass new key value up to our parent.
  2118. */
  2119. if (ptr == 1) {
  2120. xfs_alloc_key_t key; /* key containing [bno, len] */
  2121. key.ar_startblock = cpu_to_be32(bno);
  2122. key.ar_blockcount = cpu_to_be32(len);
  2123. if ((error = xfs_alloc_updkey(cur, &key, 1)))
  2124. return error;
  2125. }
  2126. return 0;
  2127. }