xfs_alloc_btree.c 56 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910
  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. /*
  54. * Internal functions.
  55. */
  56. /*
  57. * Single level of the xfs_alloc_delete record deletion routine.
  58. * Delete record pointed to by cur/level.
  59. * Remove the record from its block then rebalance the tree.
  60. * Return 0 for error, 1 for done, 2 to go on to the next level.
  61. */
  62. STATIC int /* error */
  63. xfs_alloc_delrec(
  64. xfs_btree_cur_t *cur, /* btree cursor */
  65. int level, /* level removing record from */
  66. int *stat) /* fail/done/go-on */
  67. {
  68. xfs_agf_t *agf; /* allocation group freelist header */
  69. xfs_alloc_block_t *block; /* btree block record/key lives in */
  70. xfs_agblock_t bno; /* btree block number */
  71. xfs_buf_t *bp; /* buffer for block */
  72. int error; /* error return value */
  73. int i; /* loop index */
  74. xfs_alloc_key_t key; /* kp points here if block is level 0 */
  75. xfs_agblock_t lbno; /* left block's block number */
  76. xfs_buf_t *lbp; /* left block's buffer pointer */
  77. xfs_alloc_block_t *left; /* left btree block */
  78. xfs_alloc_key_t *lkp=NULL; /* left block key pointer */
  79. xfs_alloc_ptr_t *lpp=NULL; /* left block address pointer */
  80. int lrecs=0; /* number of records in left block */
  81. xfs_alloc_rec_t *lrp; /* left block record pointer */
  82. xfs_mount_t *mp; /* mount structure */
  83. int ptr; /* index in btree block for this rec */
  84. xfs_agblock_t rbno; /* right block's block number */
  85. xfs_buf_t *rbp; /* right block's buffer pointer */
  86. xfs_alloc_block_t *right; /* right btree block */
  87. xfs_alloc_key_t *rkp; /* right block key pointer */
  88. xfs_alloc_ptr_t *rpp; /* right block address pointer */
  89. int rrecs=0; /* number of records in right block */
  90. int numrecs;
  91. xfs_alloc_rec_t *rrp; /* right block record pointer */
  92. xfs_btree_cur_t *tcur; /* temporary btree cursor */
  93. /*
  94. * Get the index of the entry being deleted, check for nothing there.
  95. */
  96. ptr = cur->bc_ptrs[level];
  97. if (ptr == 0) {
  98. *stat = 0;
  99. return 0;
  100. }
  101. /*
  102. * Get the buffer & block containing the record or key/ptr.
  103. */
  104. bp = cur->bc_bufs[level];
  105. block = XFS_BUF_TO_ALLOC_BLOCK(bp);
  106. #ifdef DEBUG
  107. if ((error = xfs_btree_check_sblock(cur, block, level, bp)))
  108. return error;
  109. #endif
  110. /*
  111. * Fail if we're off the end of the block.
  112. */
  113. numrecs = be16_to_cpu(block->bb_numrecs);
  114. if (ptr > numrecs) {
  115. *stat = 0;
  116. return 0;
  117. }
  118. XFS_STATS_INC(xs_abt_delrec);
  119. /*
  120. * It's a nonleaf. Excise the key and ptr being deleted, by
  121. * sliding the entries past them down one.
  122. * Log the changed areas of the block.
  123. */
  124. if (level > 0) {
  125. lkp = XFS_ALLOC_KEY_ADDR(block, 1, cur);
  126. lpp = XFS_ALLOC_PTR_ADDR(block, 1, cur);
  127. #ifdef DEBUG
  128. for (i = ptr; i < numrecs; i++) {
  129. if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(lpp[i]), level)))
  130. return error;
  131. }
  132. #endif
  133. if (ptr < numrecs) {
  134. memmove(&lkp[ptr - 1], &lkp[ptr],
  135. (numrecs - ptr) * sizeof(*lkp));
  136. memmove(&lpp[ptr - 1], &lpp[ptr],
  137. (numrecs - ptr) * sizeof(*lpp));
  138. xfs_alloc_log_ptrs(cur, bp, ptr, numrecs - 1);
  139. xfs_alloc_log_keys(cur, bp, ptr, numrecs - 1);
  140. }
  141. }
  142. /*
  143. * It's a leaf. Excise the record being deleted, by sliding the
  144. * entries past it down one. Log the changed areas of the block.
  145. */
  146. else {
  147. lrp = XFS_ALLOC_REC_ADDR(block, 1, cur);
  148. if (ptr < numrecs) {
  149. memmove(&lrp[ptr - 1], &lrp[ptr],
  150. (numrecs - ptr) * sizeof(*lrp));
  151. xfs_alloc_log_recs(cur, bp, ptr, numrecs - 1);
  152. }
  153. /*
  154. * If it's the first record in the block, we'll need a key
  155. * structure to pass up to the next level (updkey).
  156. */
  157. if (ptr == 1) {
  158. key.ar_startblock = lrp->ar_startblock;
  159. key.ar_blockcount = lrp->ar_blockcount;
  160. lkp = &key;
  161. }
  162. }
  163. /*
  164. * Decrement and log the number of entries in the block.
  165. */
  166. numrecs--;
  167. block->bb_numrecs = cpu_to_be16(numrecs);
  168. xfs_alloc_log_block(cur->bc_tp, bp, XFS_BB_NUMRECS);
  169. /*
  170. * See if the longest free extent in the allocation group was
  171. * changed by this operation. True if it's the by-size btree, and
  172. * this is the leaf level, and there is no right sibling block,
  173. * and this was the last record.
  174. */
  175. agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
  176. mp = cur->bc_mp;
  177. if (level == 0 &&
  178. cur->bc_btnum == XFS_BTNUM_CNT &&
  179. be32_to_cpu(block->bb_rightsib) == NULLAGBLOCK &&
  180. ptr > numrecs) {
  181. ASSERT(ptr == numrecs + 1);
  182. /*
  183. * There are still records in the block. Grab the size
  184. * from the last one.
  185. */
  186. if (numrecs) {
  187. rrp = XFS_ALLOC_REC_ADDR(block, numrecs, cur);
  188. agf->agf_longest = rrp->ar_blockcount;
  189. }
  190. /*
  191. * No free extents left.
  192. */
  193. else
  194. agf->agf_longest = 0;
  195. mp->m_perag[be32_to_cpu(agf->agf_seqno)].pagf_longest =
  196. be32_to_cpu(agf->agf_longest);
  197. xfs_alloc_log_agf(cur->bc_tp, cur->bc_private.a.agbp,
  198. XFS_AGF_LONGEST);
  199. }
  200. /*
  201. * Is this the root level? If so, we're almost done.
  202. */
  203. if (level == cur->bc_nlevels - 1) {
  204. /*
  205. * If this is the root level,
  206. * and there's only one entry left,
  207. * and it's NOT the leaf level,
  208. * then we can get rid of this level.
  209. */
  210. if (numrecs == 1 && level > 0) {
  211. /*
  212. * lpp is still set to the first pointer in the block.
  213. * Make it the new root of the btree.
  214. */
  215. bno = be32_to_cpu(agf->agf_roots[cur->bc_btnum]);
  216. agf->agf_roots[cur->bc_btnum] = *lpp;
  217. be32_add_cpu(&agf->agf_levels[cur->bc_btnum], -1);
  218. mp->m_perag[be32_to_cpu(agf->agf_seqno)].pagf_levels[cur->bc_btnum]--;
  219. /*
  220. * Put this buffer/block on the ag's freelist.
  221. */
  222. error = xfs_alloc_put_freelist(cur->bc_tp,
  223. cur->bc_private.a.agbp, NULL, bno, 1);
  224. if (error)
  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_btree_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_btree_updkey(cur, (union xfs_btree_key *)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_btree_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_btree_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_btree_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_btree_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_btree_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_btree_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_btree_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. error = xfs_alloc_put_freelist(cur->bc_tp,
  545. cur->bc_private.a.agbp, NULL, rbno, 1);
  546. if (error)
  547. return error;
  548. /*
  549. * Since blocks move to the free list without the coordination
  550. * used in xfs_bmap_finish, we can't allow block to be available
  551. * for reallocation and non-transaction writing (user data)
  552. * until we know that the transaction that moved it to the free
  553. * list is permanently on disk. We track the blocks by declaring
  554. * these blocks as "busy"; the busy list is maintained on a
  555. * per-ag basis and each transaction records which entries
  556. * should be removed when the iclog commits to disk. If a
  557. * busy block is allocated, the iclog is pushed up to the
  558. * LSN that freed the block.
  559. */
  560. xfs_alloc_mark_busy(cur->bc_tp, be32_to_cpu(agf->agf_seqno), bno, 1);
  561. xfs_trans_agbtree_delta(cur->bc_tp, -1);
  562. /*
  563. * Adjust the current level's cursor so that we're left referring
  564. * to the right node, after we're done.
  565. * If this leaves the ptr value 0 our caller will fix it up.
  566. */
  567. if (level > 0)
  568. cur->bc_ptrs[level]--;
  569. /*
  570. * Return value means the next level up has something to do.
  571. */
  572. *stat = 2;
  573. return 0;
  574. error0:
  575. xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
  576. return error;
  577. }
  578. /*
  579. * Insert one record/level. Return information to the caller
  580. * allowing the next level up to proceed if necessary.
  581. */
  582. STATIC int /* error */
  583. xfs_alloc_insrec(
  584. xfs_btree_cur_t *cur, /* btree cursor */
  585. int level, /* level to insert record at */
  586. xfs_agblock_t *bnop, /* i/o: block number inserted */
  587. xfs_alloc_rec_t *recp, /* i/o: record data inserted */
  588. xfs_btree_cur_t **curp, /* output: new cursor replacing cur */
  589. int *stat) /* output: success/failure */
  590. {
  591. xfs_agf_t *agf; /* allocation group freelist header */
  592. xfs_alloc_block_t *block; /* btree block record/key lives in */
  593. xfs_buf_t *bp; /* buffer for block */
  594. int error; /* error return value */
  595. int i; /* loop index */
  596. xfs_alloc_key_t key; /* key value being inserted */
  597. xfs_alloc_key_t *kp; /* pointer to btree keys */
  598. xfs_agblock_t nbno; /* block number of allocated block */
  599. xfs_btree_cur_t *ncur; /* new cursor to be used at next lvl */
  600. xfs_alloc_key_t nkey; /* new key value, from split */
  601. xfs_alloc_rec_t nrec; /* new record value, for caller */
  602. int numrecs;
  603. int optr; /* old ptr value */
  604. xfs_alloc_ptr_t *pp; /* pointer to btree addresses */
  605. int ptr; /* index in btree block for this rec */
  606. xfs_alloc_rec_t *rp; /* pointer to btree records */
  607. ASSERT(be32_to_cpu(recp->ar_blockcount) > 0);
  608. /*
  609. * GCC doesn't understand the (arguably complex) control flow in
  610. * this function and complains about uninitialized structure fields
  611. * without this.
  612. */
  613. memset(&nrec, 0, sizeof(nrec));
  614. /*
  615. * If we made it to the root level, allocate a new root block
  616. * and we're done.
  617. */
  618. if (level >= cur->bc_nlevels) {
  619. XFS_STATS_INC(xs_abt_insrec);
  620. if ((error = xfs_alloc_newroot(cur, &i)))
  621. return error;
  622. *bnop = NULLAGBLOCK;
  623. *stat = i;
  624. return 0;
  625. }
  626. /*
  627. * Make a key out of the record data to be inserted, and save it.
  628. */
  629. key.ar_startblock = recp->ar_startblock;
  630. key.ar_blockcount = recp->ar_blockcount;
  631. optr = ptr = cur->bc_ptrs[level];
  632. /*
  633. * If we're off the left edge, return failure.
  634. */
  635. if (ptr == 0) {
  636. *stat = 0;
  637. return 0;
  638. }
  639. XFS_STATS_INC(xs_abt_insrec);
  640. /*
  641. * Get pointers to the btree buffer and block.
  642. */
  643. bp = cur->bc_bufs[level];
  644. block = XFS_BUF_TO_ALLOC_BLOCK(bp);
  645. numrecs = be16_to_cpu(block->bb_numrecs);
  646. #ifdef DEBUG
  647. if ((error = xfs_btree_check_sblock(cur, block, level, bp)))
  648. return error;
  649. /*
  650. * Check that the new entry is being inserted in the right place.
  651. */
  652. if (ptr <= numrecs) {
  653. if (level == 0) {
  654. rp = XFS_ALLOC_REC_ADDR(block, ptr, cur);
  655. xfs_btree_check_rec(cur->bc_btnum, recp, rp);
  656. } else {
  657. kp = XFS_ALLOC_KEY_ADDR(block, ptr, cur);
  658. xfs_btree_check_key(cur->bc_btnum, &key, kp);
  659. }
  660. }
  661. #endif
  662. nbno = NULLAGBLOCK;
  663. ncur = NULL;
  664. /*
  665. * If the block is full, we can't insert the new entry until we
  666. * make the block un-full.
  667. */
  668. if (numrecs == XFS_ALLOC_BLOCK_MAXRECS(level, cur)) {
  669. /*
  670. * First, try shifting an entry to the right neighbor.
  671. */
  672. if ((error = xfs_alloc_rshift(cur, level, &i)))
  673. return error;
  674. if (i) {
  675. /* nothing */
  676. }
  677. /*
  678. * Next, try shifting an entry to the left neighbor.
  679. */
  680. else {
  681. if ((error = xfs_alloc_lshift(cur, level, &i)))
  682. return error;
  683. if (i)
  684. optr = ptr = cur->bc_ptrs[level];
  685. else {
  686. /*
  687. * Next, try splitting the current block in
  688. * half. If this works we have to re-set our
  689. * variables because we could be in a
  690. * different block now.
  691. */
  692. if ((error = xfs_alloc_split(cur, level, &nbno,
  693. &nkey, &ncur, &i)))
  694. return error;
  695. if (i) {
  696. bp = cur->bc_bufs[level];
  697. block = XFS_BUF_TO_ALLOC_BLOCK(bp);
  698. #ifdef DEBUG
  699. if ((error =
  700. xfs_btree_check_sblock(cur,
  701. block, level, bp)))
  702. return error;
  703. #endif
  704. ptr = cur->bc_ptrs[level];
  705. nrec.ar_startblock = nkey.ar_startblock;
  706. nrec.ar_blockcount = nkey.ar_blockcount;
  707. }
  708. /*
  709. * Otherwise the insert fails.
  710. */
  711. else {
  712. *stat = 0;
  713. return 0;
  714. }
  715. }
  716. }
  717. }
  718. /*
  719. * At this point we know there's room for our new entry in the block
  720. * we're pointing at.
  721. */
  722. numrecs = be16_to_cpu(block->bb_numrecs);
  723. if (level > 0) {
  724. /*
  725. * It's a non-leaf entry. Make a hole for the new data
  726. * in the key and ptr regions of the block.
  727. */
  728. kp = XFS_ALLOC_KEY_ADDR(block, 1, cur);
  729. pp = XFS_ALLOC_PTR_ADDR(block, 1, cur);
  730. #ifdef DEBUG
  731. for (i = numrecs; i >= ptr; i--) {
  732. if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(pp[i - 1]), level)))
  733. return error;
  734. }
  735. #endif
  736. memmove(&kp[ptr], &kp[ptr - 1],
  737. (numrecs - ptr + 1) * sizeof(*kp));
  738. memmove(&pp[ptr], &pp[ptr - 1],
  739. (numrecs - ptr + 1) * sizeof(*pp));
  740. #ifdef DEBUG
  741. if ((error = xfs_btree_check_sptr(cur, *bnop, level)))
  742. return error;
  743. #endif
  744. /*
  745. * Now stuff the new data in, bump numrecs and log the new data.
  746. */
  747. kp[ptr - 1] = key;
  748. pp[ptr - 1] = cpu_to_be32(*bnop);
  749. numrecs++;
  750. block->bb_numrecs = cpu_to_be16(numrecs);
  751. xfs_alloc_log_keys(cur, bp, ptr, numrecs);
  752. xfs_alloc_log_ptrs(cur, bp, ptr, numrecs);
  753. #ifdef DEBUG
  754. if (ptr < numrecs)
  755. xfs_btree_check_key(cur->bc_btnum, kp + ptr - 1,
  756. kp + ptr);
  757. #endif
  758. } else {
  759. /*
  760. * It's a leaf entry. Make a hole for the new record.
  761. */
  762. rp = XFS_ALLOC_REC_ADDR(block, 1, cur);
  763. memmove(&rp[ptr], &rp[ptr - 1],
  764. (numrecs - ptr + 1) * sizeof(*rp));
  765. /*
  766. * Now stuff the new record in, bump numrecs
  767. * and log the new data.
  768. */
  769. rp[ptr - 1] = *recp;
  770. numrecs++;
  771. block->bb_numrecs = cpu_to_be16(numrecs);
  772. xfs_alloc_log_recs(cur, bp, ptr, numrecs);
  773. #ifdef DEBUG
  774. if (ptr < numrecs)
  775. xfs_btree_check_rec(cur->bc_btnum, rp + ptr - 1,
  776. rp + ptr);
  777. #endif
  778. }
  779. /*
  780. * Log the new number of records in the btree header.
  781. */
  782. xfs_alloc_log_block(cur->bc_tp, bp, XFS_BB_NUMRECS);
  783. /*
  784. * If we inserted at the start of a block, update the parents' keys.
  785. */
  786. if (optr == 1 && (error = xfs_btree_updkey(cur, (union xfs_btree_key *)&key, level + 1)))
  787. return error;
  788. /*
  789. * Look to see if the longest extent in the allocation group
  790. * needs to be updated.
  791. */
  792. agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
  793. if (level == 0 &&
  794. cur->bc_btnum == XFS_BTNUM_CNT &&
  795. be32_to_cpu(block->bb_rightsib) == NULLAGBLOCK &&
  796. be32_to_cpu(recp->ar_blockcount) > be32_to_cpu(agf->agf_longest)) {
  797. /*
  798. * If this is a leaf in the by-size btree and there
  799. * is no right sibling block and this block is bigger
  800. * than the previous longest block, update it.
  801. */
  802. agf->agf_longest = recp->ar_blockcount;
  803. cur->bc_mp->m_perag[be32_to_cpu(agf->agf_seqno)].pagf_longest
  804. = be32_to_cpu(recp->ar_blockcount);
  805. xfs_alloc_log_agf(cur->bc_tp, cur->bc_private.a.agbp,
  806. XFS_AGF_LONGEST);
  807. }
  808. /*
  809. * Return the new block number, if any.
  810. * If there is one, give back a record value and a cursor too.
  811. */
  812. *bnop = nbno;
  813. if (nbno != NULLAGBLOCK) {
  814. *recp = nrec;
  815. *curp = ncur;
  816. }
  817. *stat = 1;
  818. return 0;
  819. }
  820. /*
  821. * Log header fields from a btree block.
  822. */
  823. STATIC void
  824. xfs_alloc_log_block(
  825. xfs_trans_t *tp, /* transaction pointer */
  826. xfs_buf_t *bp, /* buffer containing btree block */
  827. int fields) /* mask of fields: XFS_BB_... */
  828. {
  829. int first; /* first byte offset logged */
  830. int last; /* last byte offset logged */
  831. static const short offsets[] = { /* table of offsets */
  832. offsetof(xfs_alloc_block_t, bb_magic),
  833. offsetof(xfs_alloc_block_t, bb_level),
  834. offsetof(xfs_alloc_block_t, bb_numrecs),
  835. offsetof(xfs_alloc_block_t, bb_leftsib),
  836. offsetof(xfs_alloc_block_t, bb_rightsib),
  837. sizeof(xfs_alloc_block_t)
  838. };
  839. xfs_btree_offsets(fields, offsets, XFS_BB_NUM_BITS, &first, &last);
  840. xfs_trans_log_buf(tp, bp, first, last);
  841. }
  842. /*
  843. * Log keys from a btree block (nonleaf).
  844. */
  845. STATIC void
  846. xfs_alloc_log_keys(
  847. xfs_btree_cur_t *cur, /* btree cursor */
  848. xfs_buf_t *bp, /* buffer containing btree block */
  849. int kfirst, /* index of first key to log */
  850. int klast) /* index of last key to log */
  851. {
  852. xfs_alloc_block_t *block; /* btree block to log from */
  853. int first; /* first byte offset logged */
  854. xfs_alloc_key_t *kp; /* key pointer in btree block */
  855. int last; /* last byte offset logged */
  856. block = XFS_BUF_TO_ALLOC_BLOCK(bp);
  857. kp = XFS_ALLOC_KEY_ADDR(block, 1, cur);
  858. first = (int)((xfs_caddr_t)&kp[kfirst - 1] - (xfs_caddr_t)block);
  859. last = (int)(((xfs_caddr_t)&kp[klast] - 1) - (xfs_caddr_t)block);
  860. xfs_trans_log_buf(cur->bc_tp, bp, first, last);
  861. }
  862. /*
  863. * Log block pointer fields from a btree block (nonleaf).
  864. */
  865. STATIC void
  866. xfs_alloc_log_ptrs(
  867. xfs_btree_cur_t *cur, /* btree cursor */
  868. xfs_buf_t *bp, /* buffer containing btree block */
  869. int pfirst, /* index of first pointer to log */
  870. int plast) /* index of last pointer to log */
  871. {
  872. xfs_alloc_block_t *block; /* btree block to log from */
  873. int first; /* first byte offset logged */
  874. int last; /* last byte offset logged */
  875. xfs_alloc_ptr_t *pp; /* block-pointer pointer in btree blk */
  876. block = XFS_BUF_TO_ALLOC_BLOCK(bp);
  877. pp = XFS_ALLOC_PTR_ADDR(block, 1, cur);
  878. first = (int)((xfs_caddr_t)&pp[pfirst - 1] - (xfs_caddr_t)block);
  879. last = (int)(((xfs_caddr_t)&pp[plast] - 1) - (xfs_caddr_t)block);
  880. xfs_trans_log_buf(cur->bc_tp, bp, first, last);
  881. }
  882. /*
  883. * Log records from a btree block (leaf).
  884. */
  885. STATIC void
  886. xfs_alloc_log_recs(
  887. xfs_btree_cur_t *cur, /* btree cursor */
  888. xfs_buf_t *bp, /* buffer containing btree block */
  889. int rfirst, /* index of first record to log */
  890. int rlast) /* index of last record to log */
  891. {
  892. xfs_alloc_block_t *block; /* btree block to log from */
  893. int first; /* first byte offset logged */
  894. int last; /* last byte offset logged */
  895. xfs_alloc_rec_t *rp; /* record pointer for btree block */
  896. block = XFS_BUF_TO_ALLOC_BLOCK(bp);
  897. rp = XFS_ALLOC_REC_ADDR(block, 1, cur);
  898. #ifdef DEBUG
  899. {
  900. xfs_agf_t *agf;
  901. xfs_alloc_rec_t *p;
  902. agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
  903. for (p = &rp[rfirst - 1]; p <= &rp[rlast - 1]; p++)
  904. ASSERT(be32_to_cpu(p->ar_startblock) +
  905. be32_to_cpu(p->ar_blockcount) <=
  906. be32_to_cpu(agf->agf_length));
  907. }
  908. #endif
  909. first = (int)((xfs_caddr_t)&rp[rfirst - 1] - (xfs_caddr_t)block);
  910. last = (int)(((xfs_caddr_t)&rp[rlast] - 1) - (xfs_caddr_t)block);
  911. xfs_trans_log_buf(cur->bc_tp, bp, first, last);
  912. }
  913. /*
  914. * Move 1 record left from cur/level if possible.
  915. * Update cur to reflect the new path.
  916. */
  917. STATIC int /* error */
  918. xfs_alloc_lshift(
  919. xfs_btree_cur_t *cur, /* btree cursor */
  920. int level, /* level to shift record on */
  921. int *stat) /* success/failure */
  922. {
  923. int error; /* error return value */
  924. #ifdef DEBUG
  925. int i; /* loop index */
  926. #endif
  927. xfs_alloc_key_t key; /* key value for leaf level upward */
  928. xfs_buf_t *lbp; /* buffer for left neighbor block */
  929. xfs_alloc_block_t *left; /* left neighbor btree block */
  930. int nrec; /* new number of left block entries */
  931. xfs_buf_t *rbp; /* buffer for right (current) block */
  932. xfs_alloc_block_t *right; /* right (current) btree block */
  933. xfs_alloc_key_t *rkp=NULL; /* key pointer for right block */
  934. xfs_alloc_ptr_t *rpp=NULL; /* address pointer for right block */
  935. xfs_alloc_rec_t *rrp=NULL; /* record pointer for right block */
  936. /*
  937. * Set up variables for this block as "right".
  938. */
  939. rbp = cur->bc_bufs[level];
  940. right = XFS_BUF_TO_ALLOC_BLOCK(rbp);
  941. #ifdef DEBUG
  942. if ((error = xfs_btree_check_sblock(cur, right, level, rbp)))
  943. return error;
  944. #endif
  945. /*
  946. * If we've got no left sibling then we can't shift an entry left.
  947. */
  948. if (be32_to_cpu(right->bb_leftsib) == NULLAGBLOCK) {
  949. *stat = 0;
  950. return 0;
  951. }
  952. /*
  953. * If the cursor entry is the one that would be moved, don't
  954. * do it... it's too complicated.
  955. */
  956. if (cur->bc_ptrs[level] <= 1) {
  957. *stat = 0;
  958. return 0;
  959. }
  960. /*
  961. * Set up the left neighbor as "left".
  962. */
  963. if ((error = xfs_btree_read_bufs(cur->bc_mp, cur->bc_tp,
  964. cur->bc_private.a.agno, be32_to_cpu(right->bb_leftsib),
  965. 0, &lbp, XFS_ALLOC_BTREE_REF)))
  966. return error;
  967. left = XFS_BUF_TO_ALLOC_BLOCK(lbp);
  968. if ((error = xfs_btree_check_sblock(cur, left, level, lbp)))
  969. return error;
  970. /*
  971. * If it's full, it can't take another entry.
  972. */
  973. if (be16_to_cpu(left->bb_numrecs) == XFS_ALLOC_BLOCK_MAXRECS(level, cur)) {
  974. *stat = 0;
  975. return 0;
  976. }
  977. nrec = be16_to_cpu(left->bb_numrecs) + 1;
  978. /*
  979. * If non-leaf, copy a key and a ptr to the left block.
  980. */
  981. if (level > 0) {
  982. xfs_alloc_key_t *lkp; /* key pointer for left block */
  983. xfs_alloc_ptr_t *lpp; /* address pointer for left block */
  984. lkp = XFS_ALLOC_KEY_ADDR(left, nrec, cur);
  985. rkp = XFS_ALLOC_KEY_ADDR(right, 1, cur);
  986. *lkp = *rkp;
  987. xfs_alloc_log_keys(cur, lbp, nrec, nrec);
  988. lpp = XFS_ALLOC_PTR_ADDR(left, nrec, cur);
  989. rpp = XFS_ALLOC_PTR_ADDR(right, 1, cur);
  990. #ifdef DEBUG
  991. if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(*rpp), level)))
  992. return error;
  993. #endif
  994. *lpp = *rpp;
  995. xfs_alloc_log_ptrs(cur, lbp, nrec, nrec);
  996. xfs_btree_check_key(cur->bc_btnum, lkp - 1, lkp);
  997. }
  998. /*
  999. * If leaf, copy a record to the left block.
  1000. */
  1001. else {
  1002. xfs_alloc_rec_t *lrp; /* record pointer for left block */
  1003. lrp = XFS_ALLOC_REC_ADDR(left, nrec, cur);
  1004. rrp = XFS_ALLOC_REC_ADDR(right, 1, cur);
  1005. *lrp = *rrp;
  1006. xfs_alloc_log_recs(cur, lbp, nrec, nrec);
  1007. xfs_btree_check_rec(cur->bc_btnum, lrp - 1, lrp);
  1008. }
  1009. /*
  1010. * Bump and log left's numrecs, decrement and log right's numrecs.
  1011. */
  1012. be16_add_cpu(&left->bb_numrecs, 1);
  1013. xfs_alloc_log_block(cur->bc_tp, lbp, XFS_BB_NUMRECS);
  1014. be16_add_cpu(&right->bb_numrecs, -1);
  1015. xfs_alloc_log_block(cur->bc_tp, rbp, XFS_BB_NUMRECS);
  1016. /*
  1017. * Slide the contents of right down one entry.
  1018. */
  1019. if (level > 0) {
  1020. #ifdef DEBUG
  1021. for (i = 0; i < be16_to_cpu(right->bb_numrecs); i++) {
  1022. if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(rpp[i + 1]),
  1023. level)))
  1024. return error;
  1025. }
  1026. #endif
  1027. memmove(rkp, rkp + 1, be16_to_cpu(right->bb_numrecs) * sizeof(*rkp));
  1028. memmove(rpp, rpp + 1, be16_to_cpu(right->bb_numrecs) * sizeof(*rpp));
  1029. xfs_alloc_log_keys(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
  1030. xfs_alloc_log_ptrs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
  1031. } else {
  1032. memmove(rrp, rrp + 1, be16_to_cpu(right->bb_numrecs) * sizeof(*rrp));
  1033. xfs_alloc_log_recs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
  1034. key.ar_startblock = rrp->ar_startblock;
  1035. key.ar_blockcount = rrp->ar_blockcount;
  1036. rkp = &key;
  1037. }
  1038. /*
  1039. * Update the parent key values of right.
  1040. */
  1041. if ((error = xfs_btree_updkey(cur, (union xfs_btree_key *)rkp, level + 1)))
  1042. return error;
  1043. /*
  1044. * Slide the cursor value left one.
  1045. */
  1046. cur->bc_ptrs[level]--;
  1047. *stat = 1;
  1048. return 0;
  1049. }
  1050. /*
  1051. * Allocate a new root block, fill it in.
  1052. */
  1053. STATIC int /* error */
  1054. xfs_alloc_newroot(
  1055. xfs_btree_cur_t *cur, /* btree cursor */
  1056. int *stat) /* success/failure */
  1057. {
  1058. int error; /* error return value */
  1059. xfs_agblock_t lbno; /* left block number */
  1060. xfs_buf_t *lbp; /* left btree buffer */
  1061. xfs_alloc_block_t *left; /* left btree block */
  1062. xfs_mount_t *mp; /* mount structure */
  1063. xfs_agblock_t nbno; /* new block number */
  1064. xfs_buf_t *nbp; /* new (root) buffer */
  1065. xfs_alloc_block_t *new; /* new (root) btree block */
  1066. int nptr; /* new value for key index, 1 or 2 */
  1067. xfs_agblock_t rbno; /* right block number */
  1068. xfs_buf_t *rbp; /* right btree buffer */
  1069. xfs_alloc_block_t *right; /* right btree block */
  1070. mp = cur->bc_mp;
  1071. ASSERT(cur->bc_nlevels < XFS_AG_MAXLEVELS(mp));
  1072. /*
  1073. * Get a buffer from the freelist blocks, for the new root.
  1074. */
  1075. error = xfs_alloc_get_freelist(cur->bc_tp,
  1076. cur->bc_private.a.agbp, &nbno, 1);
  1077. if (error)
  1078. return error;
  1079. /*
  1080. * None available, we fail.
  1081. */
  1082. if (nbno == NULLAGBLOCK) {
  1083. *stat = 0;
  1084. return 0;
  1085. }
  1086. xfs_trans_agbtree_delta(cur->bc_tp, 1);
  1087. nbp = xfs_btree_get_bufs(mp, cur->bc_tp, cur->bc_private.a.agno, nbno,
  1088. 0);
  1089. new = XFS_BUF_TO_ALLOC_BLOCK(nbp);
  1090. /*
  1091. * Set the root data in the a.g. freespace structure.
  1092. */
  1093. {
  1094. xfs_agf_t *agf; /* a.g. freespace header */
  1095. xfs_agnumber_t seqno;
  1096. agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
  1097. agf->agf_roots[cur->bc_btnum] = cpu_to_be32(nbno);
  1098. be32_add_cpu(&agf->agf_levels[cur->bc_btnum], 1);
  1099. seqno = be32_to_cpu(agf->agf_seqno);
  1100. mp->m_perag[seqno].pagf_levels[cur->bc_btnum]++;
  1101. xfs_alloc_log_agf(cur->bc_tp, cur->bc_private.a.agbp,
  1102. XFS_AGF_ROOTS | XFS_AGF_LEVELS);
  1103. }
  1104. /*
  1105. * At the previous root level there are now two blocks: the old
  1106. * root, and the new block generated when it was split.
  1107. * We don't know which one the cursor is pointing at, so we
  1108. * set up variables "left" and "right" for each case.
  1109. */
  1110. lbp = cur->bc_bufs[cur->bc_nlevels - 1];
  1111. left = XFS_BUF_TO_ALLOC_BLOCK(lbp);
  1112. #ifdef DEBUG
  1113. if ((error = xfs_btree_check_sblock(cur, left, cur->bc_nlevels - 1, lbp)))
  1114. return error;
  1115. #endif
  1116. if (be32_to_cpu(left->bb_rightsib) != NULLAGBLOCK) {
  1117. /*
  1118. * Our block is left, pick up the right block.
  1119. */
  1120. lbno = XFS_DADDR_TO_AGBNO(mp, XFS_BUF_ADDR(lbp));
  1121. rbno = be32_to_cpu(left->bb_rightsib);
  1122. if ((error = xfs_btree_read_bufs(mp, cur->bc_tp,
  1123. cur->bc_private.a.agno, rbno, 0, &rbp,
  1124. XFS_ALLOC_BTREE_REF)))
  1125. return error;
  1126. right = XFS_BUF_TO_ALLOC_BLOCK(rbp);
  1127. if ((error = xfs_btree_check_sblock(cur, right,
  1128. cur->bc_nlevels - 1, rbp)))
  1129. return error;
  1130. nptr = 1;
  1131. } else {
  1132. /*
  1133. * Our block is right, pick up the left block.
  1134. */
  1135. rbp = lbp;
  1136. right = left;
  1137. rbno = XFS_DADDR_TO_AGBNO(mp, XFS_BUF_ADDR(rbp));
  1138. lbno = be32_to_cpu(right->bb_leftsib);
  1139. if ((error = xfs_btree_read_bufs(mp, cur->bc_tp,
  1140. cur->bc_private.a.agno, lbno, 0, &lbp,
  1141. XFS_ALLOC_BTREE_REF)))
  1142. return error;
  1143. left = XFS_BUF_TO_ALLOC_BLOCK(lbp);
  1144. if ((error = xfs_btree_check_sblock(cur, left,
  1145. cur->bc_nlevels - 1, lbp)))
  1146. return error;
  1147. nptr = 2;
  1148. }
  1149. /*
  1150. * Fill in the new block's btree header and log it.
  1151. */
  1152. new->bb_magic = cpu_to_be32(xfs_magics[cur->bc_btnum]);
  1153. new->bb_level = cpu_to_be16(cur->bc_nlevels);
  1154. new->bb_numrecs = cpu_to_be16(2);
  1155. new->bb_leftsib = cpu_to_be32(NULLAGBLOCK);
  1156. new->bb_rightsib = cpu_to_be32(NULLAGBLOCK);
  1157. xfs_alloc_log_block(cur->bc_tp, nbp, XFS_BB_ALL_BITS);
  1158. ASSERT(lbno != NULLAGBLOCK && rbno != NULLAGBLOCK);
  1159. /*
  1160. * Fill in the key data in the new root.
  1161. */
  1162. {
  1163. xfs_alloc_key_t *kp; /* btree key pointer */
  1164. kp = XFS_ALLOC_KEY_ADDR(new, 1, cur);
  1165. if (be16_to_cpu(left->bb_level) > 0) {
  1166. kp[0] = *XFS_ALLOC_KEY_ADDR(left, 1, cur);
  1167. kp[1] = *XFS_ALLOC_KEY_ADDR(right, 1, cur);
  1168. } else {
  1169. xfs_alloc_rec_t *rp; /* btree record pointer */
  1170. rp = XFS_ALLOC_REC_ADDR(left, 1, cur);
  1171. kp[0].ar_startblock = rp->ar_startblock;
  1172. kp[0].ar_blockcount = rp->ar_blockcount;
  1173. rp = XFS_ALLOC_REC_ADDR(right, 1, cur);
  1174. kp[1].ar_startblock = rp->ar_startblock;
  1175. kp[1].ar_blockcount = rp->ar_blockcount;
  1176. }
  1177. }
  1178. xfs_alloc_log_keys(cur, nbp, 1, 2);
  1179. /*
  1180. * Fill in the pointer data in the new root.
  1181. */
  1182. {
  1183. xfs_alloc_ptr_t *pp; /* btree address pointer */
  1184. pp = XFS_ALLOC_PTR_ADDR(new, 1, cur);
  1185. pp[0] = cpu_to_be32(lbno);
  1186. pp[1] = cpu_to_be32(rbno);
  1187. }
  1188. xfs_alloc_log_ptrs(cur, nbp, 1, 2);
  1189. /*
  1190. * Fix up the cursor.
  1191. */
  1192. xfs_btree_setbuf(cur, cur->bc_nlevels, nbp);
  1193. cur->bc_ptrs[cur->bc_nlevels] = nptr;
  1194. cur->bc_nlevels++;
  1195. *stat = 1;
  1196. return 0;
  1197. }
  1198. /*
  1199. * Move 1 record right from cur/level if possible.
  1200. * Update cur to reflect the new path.
  1201. */
  1202. STATIC int /* error */
  1203. xfs_alloc_rshift(
  1204. xfs_btree_cur_t *cur, /* btree cursor */
  1205. int level, /* level to shift record on */
  1206. int *stat) /* success/failure */
  1207. {
  1208. int error; /* error return value */
  1209. int i; /* loop index */
  1210. xfs_alloc_key_t key; /* key value for leaf level upward */
  1211. xfs_buf_t *lbp; /* buffer for left (current) block */
  1212. xfs_alloc_block_t *left; /* left (current) btree block */
  1213. xfs_buf_t *rbp; /* buffer for right neighbor block */
  1214. xfs_alloc_block_t *right; /* right neighbor btree block */
  1215. xfs_alloc_key_t *rkp; /* key pointer for right block */
  1216. xfs_btree_cur_t *tcur; /* temporary cursor */
  1217. /*
  1218. * Set up variables for this block as "left".
  1219. */
  1220. lbp = cur->bc_bufs[level];
  1221. left = XFS_BUF_TO_ALLOC_BLOCK(lbp);
  1222. #ifdef DEBUG
  1223. if ((error = xfs_btree_check_sblock(cur, left, level, lbp)))
  1224. return error;
  1225. #endif
  1226. /*
  1227. * If we've got no right sibling then we can't shift an entry right.
  1228. */
  1229. if (be32_to_cpu(left->bb_rightsib) == NULLAGBLOCK) {
  1230. *stat = 0;
  1231. return 0;
  1232. }
  1233. /*
  1234. * If the cursor entry is the one that would be moved, don't
  1235. * do it... it's too complicated.
  1236. */
  1237. if (cur->bc_ptrs[level] >= be16_to_cpu(left->bb_numrecs)) {
  1238. *stat = 0;
  1239. return 0;
  1240. }
  1241. /*
  1242. * Set up the right neighbor as "right".
  1243. */
  1244. if ((error = xfs_btree_read_bufs(cur->bc_mp, cur->bc_tp,
  1245. cur->bc_private.a.agno, be32_to_cpu(left->bb_rightsib),
  1246. 0, &rbp, XFS_ALLOC_BTREE_REF)))
  1247. return error;
  1248. right = XFS_BUF_TO_ALLOC_BLOCK(rbp);
  1249. if ((error = xfs_btree_check_sblock(cur, right, level, rbp)))
  1250. return error;
  1251. /*
  1252. * If it's full, it can't take another entry.
  1253. */
  1254. if (be16_to_cpu(right->bb_numrecs) == XFS_ALLOC_BLOCK_MAXRECS(level, cur)) {
  1255. *stat = 0;
  1256. return 0;
  1257. }
  1258. /*
  1259. * Make a hole at the start of the right neighbor block, then
  1260. * copy the last left block entry to the hole.
  1261. */
  1262. if (level > 0) {
  1263. xfs_alloc_key_t *lkp; /* key pointer for left block */
  1264. xfs_alloc_ptr_t *lpp; /* address pointer for left block */
  1265. xfs_alloc_ptr_t *rpp; /* address pointer for right block */
  1266. lkp = XFS_ALLOC_KEY_ADDR(left, be16_to_cpu(left->bb_numrecs), cur);
  1267. lpp = XFS_ALLOC_PTR_ADDR(left, be16_to_cpu(left->bb_numrecs), cur);
  1268. rkp = XFS_ALLOC_KEY_ADDR(right, 1, cur);
  1269. rpp = XFS_ALLOC_PTR_ADDR(right, 1, cur);
  1270. #ifdef DEBUG
  1271. for (i = be16_to_cpu(right->bb_numrecs) - 1; i >= 0; i--) {
  1272. if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(rpp[i]), level)))
  1273. return error;
  1274. }
  1275. #endif
  1276. memmove(rkp + 1, rkp, be16_to_cpu(right->bb_numrecs) * sizeof(*rkp));
  1277. memmove(rpp + 1, rpp, be16_to_cpu(right->bb_numrecs) * sizeof(*rpp));
  1278. #ifdef DEBUG
  1279. if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(*lpp), level)))
  1280. return error;
  1281. #endif
  1282. *rkp = *lkp;
  1283. *rpp = *lpp;
  1284. xfs_alloc_log_keys(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1);
  1285. xfs_alloc_log_ptrs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1);
  1286. xfs_btree_check_key(cur->bc_btnum, rkp, rkp + 1);
  1287. } else {
  1288. xfs_alloc_rec_t *lrp; /* record pointer for left block */
  1289. xfs_alloc_rec_t *rrp; /* record pointer for right block */
  1290. lrp = XFS_ALLOC_REC_ADDR(left, be16_to_cpu(left->bb_numrecs), cur);
  1291. rrp = XFS_ALLOC_REC_ADDR(right, 1, cur);
  1292. memmove(rrp + 1, rrp, be16_to_cpu(right->bb_numrecs) * sizeof(*rrp));
  1293. *rrp = *lrp;
  1294. xfs_alloc_log_recs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs) + 1);
  1295. key.ar_startblock = rrp->ar_startblock;
  1296. key.ar_blockcount = rrp->ar_blockcount;
  1297. rkp = &key;
  1298. xfs_btree_check_rec(cur->bc_btnum, rrp, rrp + 1);
  1299. }
  1300. /*
  1301. * Decrement and log left's numrecs, bump and log right's numrecs.
  1302. */
  1303. be16_add_cpu(&left->bb_numrecs, -1);
  1304. xfs_alloc_log_block(cur->bc_tp, lbp, XFS_BB_NUMRECS);
  1305. be16_add_cpu(&right->bb_numrecs, 1);
  1306. xfs_alloc_log_block(cur->bc_tp, rbp, XFS_BB_NUMRECS);
  1307. /*
  1308. * Using a temporary cursor, update the parent key values of the
  1309. * block on the right.
  1310. */
  1311. if ((error = xfs_btree_dup_cursor(cur, &tcur)))
  1312. return error;
  1313. i = xfs_btree_lastrec(tcur, level);
  1314. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  1315. if ((error = xfs_btree_increment(tcur, level, &i)) ||
  1316. (error = xfs_btree_updkey(tcur, (union xfs_btree_key *)rkp, level + 1)))
  1317. goto error0;
  1318. xfs_btree_del_cursor(tcur, XFS_BTREE_NOERROR);
  1319. *stat = 1;
  1320. return 0;
  1321. error0:
  1322. xfs_btree_del_cursor(tcur, XFS_BTREE_ERROR);
  1323. return error;
  1324. }
  1325. /*
  1326. * Split cur/level block in half.
  1327. * Return new block number and its first record (to be inserted into parent).
  1328. */
  1329. STATIC int /* error */
  1330. xfs_alloc_split(
  1331. xfs_btree_cur_t *cur, /* btree cursor */
  1332. int level, /* level to split */
  1333. xfs_agblock_t *bnop, /* output: block number allocated */
  1334. xfs_alloc_key_t *keyp, /* output: first key of new block */
  1335. xfs_btree_cur_t **curp, /* output: new cursor */
  1336. int *stat) /* success/failure */
  1337. {
  1338. int error; /* error return value */
  1339. int i; /* loop index/record number */
  1340. xfs_agblock_t lbno; /* left (current) block number */
  1341. xfs_buf_t *lbp; /* buffer for left block */
  1342. xfs_alloc_block_t *left; /* left (current) btree block */
  1343. xfs_agblock_t rbno; /* right (new) block number */
  1344. xfs_buf_t *rbp; /* buffer for right block */
  1345. xfs_alloc_block_t *right; /* right (new) btree block */
  1346. /*
  1347. * Allocate the new block from the freelist.
  1348. * If we can't do it, we're toast. Give up.
  1349. */
  1350. error = xfs_alloc_get_freelist(cur->bc_tp,
  1351. cur->bc_private.a.agbp, &rbno, 1);
  1352. if (error)
  1353. return error;
  1354. if (rbno == NULLAGBLOCK) {
  1355. *stat = 0;
  1356. return 0;
  1357. }
  1358. xfs_trans_agbtree_delta(cur->bc_tp, 1);
  1359. rbp = xfs_btree_get_bufs(cur->bc_mp, cur->bc_tp, cur->bc_private.a.agno,
  1360. rbno, 0);
  1361. /*
  1362. * Set up the new block as "right".
  1363. */
  1364. right = XFS_BUF_TO_ALLOC_BLOCK(rbp);
  1365. /*
  1366. * "Left" is the current (according to the cursor) block.
  1367. */
  1368. lbp = cur->bc_bufs[level];
  1369. left = XFS_BUF_TO_ALLOC_BLOCK(lbp);
  1370. #ifdef DEBUG
  1371. if ((error = xfs_btree_check_sblock(cur, left, level, lbp)))
  1372. return error;
  1373. #endif
  1374. /*
  1375. * Fill in the btree header for the new block.
  1376. */
  1377. right->bb_magic = cpu_to_be32(xfs_magics[cur->bc_btnum]);
  1378. right->bb_level = left->bb_level;
  1379. right->bb_numrecs = cpu_to_be16(be16_to_cpu(left->bb_numrecs) / 2);
  1380. /*
  1381. * Make sure that if there's an odd number of entries now, that
  1382. * each new block will have the same number of entries.
  1383. */
  1384. if ((be16_to_cpu(left->bb_numrecs) & 1) &&
  1385. cur->bc_ptrs[level] <= be16_to_cpu(right->bb_numrecs) + 1)
  1386. be16_add_cpu(&right->bb_numrecs, 1);
  1387. i = be16_to_cpu(left->bb_numrecs) - be16_to_cpu(right->bb_numrecs) + 1;
  1388. /*
  1389. * For non-leaf blocks, copy keys and addresses over to the new block.
  1390. */
  1391. if (level > 0) {
  1392. xfs_alloc_key_t *lkp; /* left btree key pointer */
  1393. xfs_alloc_ptr_t *lpp; /* left btree address pointer */
  1394. xfs_alloc_key_t *rkp; /* right btree key pointer */
  1395. xfs_alloc_ptr_t *rpp; /* right btree address pointer */
  1396. lkp = XFS_ALLOC_KEY_ADDR(left, i, cur);
  1397. lpp = XFS_ALLOC_PTR_ADDR(left, i, cur);
  1398. rkp = XFS_ALLOC_KEY_ADDR(right, 1, cur);
  1399. rpp = XFS_ALLOC_PTR_ADDR(right, 1, cur);
  1400. #ifdef DEBUG
  1401. for (i = 0; i < be16_to_cpu(right->bb_numrecs); i++) {
  1402. if ((error = xfs_btree_check_sptr(cur, be32_to_cpu(lpp[i]), level)))
  1403. return error;
  1404. }
  1405. #endif
  1406. memcpy(rkp, lkp, be16_to_cpu(right->bb_numrecs) * sizeof(*rkp));
  1407. memcpy(rpp, lpp, be16_to_cpu(right->bb_numrecs) * sizeof(*rpp));
  1408. xfs_alloc_log_keys(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
  1409. xfs_alloc_log_ptrs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
  1410. *keyp = *rkp;
  1411. }
  1412. /*
  1413. * For leaf blocks, copy records over to the new block.
  1414. */
  1415. else {
  1416. xfs_alloc_rec_t *lrp; /* left btree record pointer */
  1417. xfs_alloc_rec_t *rrp; /* right btree record pointer */
  1418. lrp = XFS_ALLOC_REC_ADDR(left, i, cur);
  1419. rrp = XFS_ALLOC_REC_ADDR(right, 1, cur);
  1420. memcpy(rrp, lrp, be16_to_cpu(right->bb_numrecs) * sizeof(*rrp));
  1421. xfs_alloc_log_recs(cur, rbp, 1, be16_to_cpu(right->bb_numrecs));
  1422. keyp->ar_startblock = rrp->ar_startblock;
  1423. keyp->ar_blockcount = rrp->ar_blockcount;
  1424. }
  1425. /*
  1426. * Find the left block number by looking in the buffer.
  1427. * Adjust numrecs, sibling pointers.
  1428. */
  1429. lbno = XFS_DADDR_TO_AGBNO(cur->bc_mp, XFS_BUF_ADDR(lbp));
  1430. be16_add_cpu(&left->bb_numrecs, -(be16_to_cpu(right->bb_numrecs)));
  1431. right->bb_rightsib = left->bb_rightsib;
  1432. left->bb_rightsib = cpu_to_be32(rbno);
  1433. right->bb_leftsib = cpu_to_be32(lbno);
  1434. xfs_alloc_log_block(cur->bc_tp, rbp, XFS_BB_ALL_BITS);
  1435. xfs_alloc_log_block(cur->bc_tp, lbp, XFS_BB_NUMRECS | XFS_BB_RIGHTSIB);
  1436. /*
  1437. * If there's a block to the new block's right, make that block
  1438. * point back to right instead of to left.
  1439. */
  1440. if (be32_to_cpu(right->bb_rightsib) != NULLAGBLOCK) {
  1441. xfs_alloc_block_t *rrblock; /* rr btree block */
  1442. xfs_buf_t *rrbp; /* buffer for rrblock */
  1443. if ((error = xfs_btree_read_bufs(cur->bc_mp, cur->bc_tp,
  1444. cur->bc_private.a.agno, be32_to_cpu(right->bb_rightsib), 0,
  1445. &rrbp, XFS_ALLOC_BTREE_REF)))
  1446. return error;
  1447. rrblock = XFS_BUF_TO_ALLOC_BLOCK(rrbp);
  1448. if ((error = xfs_btree_check_sblock(cur, rrblock, level, rrbp)))
  1449. return error;
  1450. rrblock->bb_leftsib = cpu_to_be32(rbno);
  1451. xfs_alloc_log_block(cur->bc_tp, rrbp, XFS_BB_LEFTSIB);
  1452. }
  1453. /*
  1454. * If the cursor is really in the right block, move it there.
  1455. * If it's just pointing past the last entry in left, then we'll
  1456. * insert there, so don't change anything in that case.
  1457. */
  1458. if (cur->bc_ptrs[level] > be16_to_cpu(left->bb_numrecs) + 1) {
  1459. xfs_btree_setbuf(cur, level, rbp);
  1460. cur->bc_ptrs[level] -= be16_to_cpu(left->bb_numrecs);
  1461. }
  1462. /*
  1463. * If there are more levels, we'll need another cursor which refers to
  1464. * the right block, no matter where this cursor was.
  1465. */
  1466. if (level + 1 < cur->bc_nlevels) {
  1467. if ((error = xfs_btree_dup_cursor(cur, curp)))
  1468. return error;
  1469. (*curp)->bc_ptrs[level + 1]++;
  1470. }
  1471. *bnop = rbno;
  1472. *stat = 1;
  1473. return 0;
  1474. }
  1475. /*
  1476. * Externally visible routines.
  1477. */
  1478. /*
  1479. * Delete the record pointed to by cur.
  1480. * The cursor refers to the place where the record was (could be inserted)
  1481. * when the operation returns.
  1482. */
  1483. int /* error */
  1484. xfs_alloc_delete(
  1485. xfs_btree_cur_t *cur, /* btree cursor */
  1486. int *stat) /* success/failure */
  1487. {
  1488. int error; /* error return value */
  1489. int i; /* result code */
  1490. int level; /* btree level */
  1491. /*
  1492. * Go up the tree, starting at leaf level.
  1493. * If 2 is returned then a join was done; go to the next level.
  1494. * Otherwise we are done.
  1495. */
  1496. for (level = 0, i = 2; i == 2; level++) {
  1497. if ((error = xfs_alloc_delrec(cur, level, &i)))
  1498. return error;
  1499. }
  1500. if (i == 0) {
  1501. for (level = 1; level < cur->bc_nlevels; level++) {
  1502. if (cur->bc_ptrs[level] == 0) {
  1503. if ((error = xfs_btree_decrement(cur, level, &i)))
  1504. return error;
  1505. break;
  1506. }
  1507. }
  1508. }
  1509. *stat = i;
  1510. return 0;
  1511. }
  1512. /*
  1513. * Get the data from the pointed-to record.
  1514. */
  1515. int /* error */
  1516. xfs_alloc_get_rec(
  1517. xfs_btree_cur_t *cur, /* btree cursor */
  1518. xfs_agblock_t *bno, /* output: starting block of extent */
  1519. xfs_extlen_t *len, /* output: length of extent */
  1520. int *stat) /* output: success/failure */
  1521. {
  1522. xfs_alloc_block_t *block; /* btree block */
  1523. #ifdef DEBUG
  1524. int error; /* error return value */
  1525. #endif
  1526. int ptr; /* record number */
  1527. ptr = cur->bc_ptrs[0];
  1528. block = XFS_BUF_TO_ALLOC_BLOCK(cur->bc_bufs[0]);
  1529. #ifdef DEBUG
  1530. if ((error = xfs_btree_check_sblock(cur, block, 0, cur->bc_bufs[0])))
  1531. return error;
  1532. #endif
  1533. /*
  1534. * Off the right end or left end, return failure.
  1535. */
  1536. if (ptr > be16_to_cpu(block->bb_numrecs) || ptr <= 0) {
  1537. *stat = 0;
  1538. return 0;
  1539. }
  1540. /*
  1541. * Point to the record and extract its data.
  1542. */
  1543. {
  1544. xfs_alloc_rec_t *rec; /* record data */
  1545. rec = XFS_ALLOC_REC_ADDR(block, ptr, cur);
  1546. *bno = be32_to_cpu(rec->ar_startblock);
  1547. *len = be32_to_cpu(rec->ar_blockcount);
  1548. }
  1549. *stat = 1;
  1550. return 0;
  1551. }
  1552. /*
  1553. * Insert the current record at the point referenced by cur.
  1554. * The cursor may be inconsistent on return if splits have been done.
  1555. */
  1556. int /* error */
  1557. xfs_alloc_insert(
  1558. xfs_btree_cur_t *cur, /* btree cursor */
  1559. int *stat) /* success/failure */
  1560. {
  1561. int error; /* error return value */
  1562. int i; /* result value, 0 for failure */
  1563. int level; /* current level number in btree */
  1564. xfs_agblock_t nbno; /* new block number (split result) */
  1565. xfs_btree_cur_t *ncur; /* new cursor (split result) */
  1566. xfs_alloc_rec_t nrec; /* record being inserted this level */
  1567. xfs_btree_cur_t *pcur; /* previous level's cursor */
  1568. level = 0;
  1569. nbno = NULLAGBLOCK;
  1570. nrec.ar_startblock = cpu_to_be32(cur->bc_rec.a.ar_startblock);
  1571. nrec.ar_blockcount = cpu_to_be32(cur->bc_rec.a.ar_blockcount);
  1572. ncur = NULL;
  1573. pcur = cur;
  1574. /*
  1575. * Loop going up the tree, starting at the leaf level.
  1576. * Stop when we don't get a split block, that must mean that
  1577. * the insert is finished with this level.
  1578. */
  1579. do {
  1580. /*
  1581. * Insert nrec/nbno into this level of the tree.
  1582. * Note if we fail, nbno will be null.
  1583. */
  1584. if ((error = xfs_alloc_insrec(pcur, level++, &nbno, &nrec, &ncur,
  1585. &i))) {
  1586. if (pcur != cur)
  1587. xfs_btree_del_cursor(pcur, XFS_BTREE_ERROR);
  1588. return error;
  1589. }
  1590. /*
  1591. * See if the cursor we just used is trash.
  1592. * Can't trash the caller's cursor, but otherwise we should
  1593. * if ncur is a new cursor or we're about to be done.
  1594. */
  1595. if (pcur != cur && (ncur || nbno == NULLAGBLOCK)) {
  1596. cur->bc_nlevels = pcur->bc_nlevels;
  1597. xfs_btree_del_cursor(pcur, XFS_BTREE_NOERROR);
  1598. }
  1599. /*
  1600. * If we got a new cursor, switch to it.
  1601. */
  1602. if (ncur) {
  1603. pcur = ncur;
  1604. ncur = NULL;
  1605. }
  1606. } while (nbno != NULLAGBLOCK);
  1607. *stat = i;
  1608. return 0;
  1609. }
  1610. /*
  1611. * Update the record referred to by cur, to the value given by [bno, len].
  1612. * This either works (return 0) or gets an EFSCORRUPTED error.
  1613. */
  1614. int /* error */
  1615. xfs_alloc_update(
  1616. xfs_btree_cur_t *cur, /* btree cursor */
  1617. xfs_agblock_t bno, /* starting block of extent */
  1618. xfs_extlen_t len) /* length of extent */
  1619. {
  1620. xfs_alloc_block_t *block; /* btree block to update */
  1621. int error; /* error return value */
  1622. int ptr; /* current record number (updating) */
  1623. ASSERT(len > 0);
  1624. /*
  1625. * Pick up the a.g. freelist struct and the current block.
  1626. */
  1627. block = XFS_BUF_TO_ALLOC_BLOCK(cur->bc_bufs[0]);
  1628. #ifdef DEBUG
  1629. if ((error = xfs_btree_check_sblock(cur, block, 0, cur->bc_bufs[0])))
  1630. return error;
  1631. #endif
  1632. /*
  1633. * Get the address of the rec to be updated.
  1634. */
  1635. ptr = cur->bc_ptrs[0];
  1636. {
  1637. xfs_alloc_rec_t *rp; /* pointer to updated record */
  1638. rp = XFS_ALLOC_REC_ADDR(block, ptr, cur);
  1639. /*
  1640. * Fill in the new contents and log them.
  1641. */
  1642. rp->ar_startblock = cpu_to_be32(bno);
  1643. rp->ar_blockcount = cpu_to_be32(len);
  1644. xfs_alloc_log_recs(cur, cur->bc_bufs[0], ptr, ptr);
  1645. }
  1646. /*
  1647. * If it's the by-size btree and it's the last leaf block and
  1648. * it's the last record... then update the size of the longest
  1649. * extent in the a.g., which we cache in the a.g. freelist header.
  1650. */
  1651. if (cur->bc_btnum == XFS_BTNUM_CNT &&
  1652. be32_to_cpu(block->bb_rightsib) == NULLAGBLOCK &&
  1653. ptr == be16_to_cpu(block->bb_numrecs)) {
  1654. xfs_agf_t *agf; /* a.g. freespace header */
  1655. xfs_agnumber_t seqno;
  1656. agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
  1657. seqno = be32_to_cpu(agf->agf_seqno);
  1658. cur->bc_mp->m_perag[seqno].pagf_longest = len;
  1659. agf->agf_longest = cpu_to_be32(len);
  1660. xfs_alloc_log_agf(cur->bc_tp, cur->bc_private.a.agbp,
  1661. XFS_AGF_LONGEST);
  1662. }
  1663. /*
  1664. * Updating first record in leaf. Pass new key value up to our parent.
  1665. */
  1666. if (ptr == 1) {
  1667. xfs_alloc_key_t key; /* key containing [bno, len] */
  1668. key.ar_startblock = cpu_to_be32(bno);
  1669. key.ar_blockcount = cpu_to_be32(len);
  1670. if ((error = xfs_btree_updkey(cur, (union xfs_btree_key *)&key, 1)))
  1671. return error;
  1672. }
  1673. return 0;
  1674. }
  1675. STATIC struct xfs_btree_cur *
  1676. xfs_allocbt_dup_cursor(
  1677. struct xfs_btree_cur *cur)
  1678. {
  1679. return xfs_allocbt_init_cursor(cur->bc_mp, cur->bc_tp,
  1680. cur->bc_private.a.agbp, cur->bc_private.a.agno,
  1681. cur->bc_btnum);
  1682. }
  1683. STATIC int
  1684. xfs_allocbt_get_maxrecs(
  1685. struct xfs_btree_cur *cur,
  1686. int level)
  1687. {
  1688. return cur->bc_mp->m_alloc_mxr[level != 0];
  1689. }
  1690. STATIC void
  1691. xfs_allocbt_init_key_from_rec(
  1692. union xfs_btree_key *key,
  1693. union xfs_btree_rec *rec)
  1694. {
  1695. ASSERT(rec->alloc.ar_startblock != 0);
  1696. key->alloc.ar_startblock = rec->alloc.ar_startblock;
  1697. key->alloc.ar_blockcount = rec->alloc.ar_blockcount;
  1698. }
  1699. STATIC void
  1700. xfs_allocbt_init_ptr_from_cur(
  1701. struct xfs_btree_cur *cur,
  1702. union xfs_btree_ptr *ptr)
  1703. {
  1704. struct xfs_agf *agf = XFS_BUF_TO_AGF(cur->bc_private.a.agbp);
  1705. ASSERT(cur->bc_private.a.agno == be32_to_cpu(agf->agf_seqno));
  1706. ASSERT(agf->agf_roots[cur->bc_btnum] != 0);
  1707. ptr->s = agf->agf_roots[cur->bc_btnum];
  1708. }
  1709. STATIC __int64_t
  1710. xfs_allocbt_key_diff(
  1711. struct xfs_btree_cur *cur,
  1712. union xfs_btree_key *key)
  1713. {
  1714. xfs_alloc_rec_incore_t *rec = &cur->bc_rec.a;
  1715. xfs_alloc_key_t *kp = &key->alloc;
  1716. __int64_t diff;
  1717. if (cur->bc_btnum == XFS_BTNUM_BNO) {
  1718. return (__int64_t)be32_to_cpu(kp->ar_startblock) -
  1719. rec->ar_startblock;
  1720. }
  1721. diff = (__int64_t)be32_to_cpu(kp->ar_blockcount) - rec->ar_blockcount;
  1722. if (diff)
  1723. return diff;
  1724. return (__int64_t)be32_to_cpu(kp->ar_startblock) - rec->ar_startblock;
  1725. }
  1726. #ifdef XFS_BTREE_TRACE
  1727. ktrace_t *xfs_allocbt_trace_buf;
  1728. STATIC void
  1729. xfs_allocbt_trace_enter(
  1730. struct xfs_btree_cur *cur,
  1731. const char *func,
  1732. char *s,
  1733. int type,
  1734. int line,
  1735. __psunsigned_t a0,
  1736. __psunsigned_t a1,
  1737. __psunsigned_t a2,
  1738. __psunsigned_t a3,
  1739. __psunsigned_t a4,
  1740. __psunsigned_t a5,
  1741. __psunsigned_t a6,
  1742. __psunsigned_t a7,
  1743. __psunsigned_t a8,
  1744. __psunsigned_t a9,
  1745. __psunsigned_t a10)
  1746. {
  1747. ktrace_enter(xfs_allocbt_trace_buf, (void *)(__psint_t)type,
  1748. (void *)func, (void *)s, NULL, (void *)cur,
  1749. (void *)a0, (void *)a1, (void *)a2, (void *)a3,
  1750. (void *)a4, (void *)a5, (void *)a6, (void *)a7,
  1751. (void *)a8, (void *)a9, (void *)a10);
  1752. }
  1753. STATIC void
  1754. xfs_allocbt_trace_cursor(
  1755. struct xfs_btree_cur *cur,
  1756. __uint32_t *s0,
  1757. __uint64_t *l0,
  1758. __uint64_t *l1)
  1759. {
  1760. *s0 = cur->bc_private.a.agno;
  1761. *l0 = cur->bc_rec.a.ar_startblock;
  1762. *l1 = cur->bc_rec.a.ar_blockcount;
  1763. }
  1764. STATIC void
  1765. xfs_allocbt_trace_key(
  1766. struct xfs_btree_cur *cur,
  1767. union xfs_btree_key *key,
  1768. __uint64_t *l0,
  1769. __uint64_t *l1)
  1770. {
  1771. *l0 = be32_to_cpu(key->alloc.ar_startblock);
  1772. *l1 = be32_to_cpu(key->alloc.ar_blockcount);
  1773. }
  1774. STATIC void
  1775. xfs_allocbt_trace_record(
  1776. struct xfs_btree_cur *cur,
  1777. union xfs_btree_rec *rec,
  1778. __uint64_t *l0,
  1779. __uint64_t *l1,
  1780. __uint64_t *l2)
  1781. {
  1782. *l0 = be32_to_cpu(rec->alloc.ar_startblock);
  1783. *l1 = be32_to_cpu(rec->alloc.ar_blockcount);
  1784. *l2 = 0;
  1785. }
  1786. #endif /* XFS_BTREE_TRACE */
  1787. static const struct xfs_btree_ops xfs_allocbt_ops = {
  1788. .rec_len = sizeof(xfs_alloc_rec_t),
  1789. .key_len = sizeof(xfs_alloc_key_t),
  1790. .dup_cursor = xfs_allocbt_dup_cursor,
  1791. .get_maxrecs = xfs_allocbt_get_maxrecs,
  1792. .init_key_from_rec = xfs_allocbt_init_key_from_rec,
  1793. .init_ptr_from_cur = xfs_allocbt_init_ptr_from_cur,
  1794. .key_diff = xfs_allocbt_key_diff,
  1795. #ifdef XFS_BTREE_TRACE
  1796. .trace_enter = xfs_allocbt_trace_enter,
  1797. .trace_cursor = xfs_allocbt_trace_cursor,
  1798. .trace_key = xfs_allocbt_trace_key,
  1799. .trace_record = xfs_allocbt_trace_record,
  1800. #endif
  1801. };
  1802. /*
  1803. * Allocate a new allocation btree cursor.
  1804. */
  1805. struct xfs_btree_cur * /* new alloc btree cursor */
  1806. xfs_allocbt_init_cursor(
  1807. struct xfs_mount *mp, /* file system mount point */
  1808. struct xfs_trans *tp, /* transaction pointer */
  1809. struct xfs_buf *agbp, /* buffer for agf structure */
  1810. xfs_agnumber_t agno, /* allocation group number */
  1811. xfs_btnum_t btnum) /* btree identifier */
  1812. {
  1813. struct xfs_agf *agf = XFS_BUF_TO_AGF(agbp);
  1814. struct xfs_btree_cur *cur;
  1815. ASSERT(btnum == XFS_BTNUM_BNO || btnum == XFS_BTNUM_CNT);
  1816. cur = kmem_zone_zalloc(xfs_btree_cur_zone, KM_SLEEP);
  1817. cur->bc_tp = tp;
  1818. cur->bc_mp = mp;
  1819. cur->bc_nlevels = be32_to_cpu(agf->agf_levels[btnum]);
  1820. cur->bc_btnum = btnum;
  1821. cur->bc_blocklog = mp->m_sb.sb_blocklog;
  1822. cur->bc_ops = &xfs_allocbt_ops;
  1823. cur->bc_private.a.agbp = agbp;
  1824. cur->bc_private.a.agno = agno;
  1825. return cur;
  1826. }