xfs_da_btree.c 71 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768176917701771177217731774177517761777177817791780178117821783178417851786178717881789179017911792179317941795179617971798179918001801180218031804180518061807180818091810181118121813181418151816181718181819182018211822182318241825182618271828182918301831183218331834183518361837183818391840184118421843184418451846184718481849185018511852185318541855185618571858185918601861186218631864186518661867186818691870187118721873187418751876187718781879188018811882188318841885188618871888188918901891189218931894189518961897189818991900190119021903190419051906190719081909191019111912191319141915191619171918191919201921192219231924192519261927192819291930193119321933193419351936193719381939194019411942194319441945194619471948194919501951195219531954195519561957195819591960196119621963196419651966196719681969197019711972197319741975197619771978197919801981198219831984198519861987198819891990199119921993199419951996199719981999200020012002200320042005200620072008200920102011201220132014201520162017201820192020202120222023202420252026202720282029203020312032203320342035203620372038203920402041204220432044204520462047204820492050205120522053205420552056205720582059206020612062206320642065206620672068206920702071207220732074207520762077207820792080208120822083208420852086208720882089209020912092209320942095209620972098209921002101210221032104210521062107210821092110211121122113211421152116211721182119212021212122212321242125212621272128212921302131213221332134213521362137213821392140214121422143214421452146214721482149215021512152215321542155215621572158215921602161216221632164216521662167216821692170217121722173217421752176217721782179218021812182218321842185218621872188218921902191219221932194219521962197219821992200220122022203220422052206220722082209221022112212221322142215221622172218221922202221222222232224222522262227222822292230223122322233223422352236223722382239224022412242224322442245224622472248224922502251225222532254225522562257225822592260226122622263226422652266226722682269227022712272227322742275227622772278227922802281228222832284228522862287228822892290229122922293229422952296229722982299230023012302230323042305230623072308230923102311231223132314231523162317231823192320232123222323232423252326232723282329233023312332233323342335233623372338233923402341234223432344234523462347234823492350235123522353235423552356235723582359236023612362236323642365236623672368236923702371237223732374237523762377237823792380238123822383238423852386238723882389239023912392239323942395239623972398239924002401240224032404240524062407240824092410241124122413241424152416241724182419242024212422242324242425242624272428242924302431243224332434243524362437243824392440244124422443244424452446244724482449245024512452245324542455245624572458245924602461246224632464246524662467246824692470247124722473247424752476247724782479248024812482248324842485248624872488248924902491249224932494249524962497249824992500250125022503250425052506250725082509251025112512251325142515251625172518251925202521252225232524252525262527252825292530253125322533253425352536253725382539254025412542254325442545254625472548254925502551255225532554255525562557255825592560256125622563256425652566256725682569257025712572257325742575257625772578257925802581258225832584258525862587258825892590259125922593259425952596259725982599260026012602260326042605260626072608260926102611261226132614261526162617261826192620262126222623262426252626262726282629263026312632263326342635263626372638263926402641264226432644264526462647264826492650265126522653265426552656265726582659266026612662266326642665266626672668266926702671267226732674267526762677267826792680268126822683268426852686268726882689269026912692269326942695269626972698
  1. // SPDX-License-Identifier: GPL-2.0
  2. /*
  3. * Copyright (c) 2000-2005 Silicon Graphics, Inc.
  4. * Copyright (c) 2013 Red Hat, Inc.
  5. * All Rights Reserved.
  6. */
  7. #include "xfs.h"
  8. #include "xfs_fs.h"
  9. #include "xfs_shared.h"
  10. #include "xfs_format.h"
  11. #include "xfs_log_format.h"
  12. #include "xfs_trans_resv.h"
  13. #include "xfs_bit.h"
  14. #include "xfs_mount.h"
  15. #include "xfs_inode.h"
  16. #include "xfs_dir2.h"
  17. #include "xfs_dir2_priv.h"
  18. #include "xfs_trans.h"
  19. #include "xfs_bmap.h"
  20. #include "xfs_attr_leaf.h"
  21. #include "xfs_error.h"
  22. #include "xfs_trace.h"
  23. #include "xfs_buf_item.h"
  24. #include "xfs_log.h"
  25. #include "xfs_errortag.h"
  26. /*
  27. * xfs_da_btree.c
  28. *
  29. * Routines to implement directories as Btrees of hashed names.
  30. */
  31. /*========================================================================
  32. * Function prototypes for the kernel.
  33. *========================================================================*/
  34. /*
  35. * Routines used for growing the Btree.
  36. */
  37. STATIC int xfs_da3_root_split(xfs_da_state_t *state,
  38. xfs_da_state_blk_t *existing_root,
  39. xfs_da_state_blk_t *new_child);
  40. STATIC int xfs_da3_node_split(xfs_da_state_t *state,
  41. xfs_da_state_blk_t *existing_blk,
  42. xfs_da_state_blk_t *split_blk,
  43. xfs_da_state_blk_t *blk_to_add,
  44. int treelevel,
  45. int *result);
  46. STATIC void xfs_da3_node_rebalance(xfs_da_state_t *state,
  47. xfs_da_state_blk_t *node_blk_1,
  48. xfs_da_state_blk_t *node_blk_2);
  49. STATIC void xfs_da3_node_add(xfs_da_state_t *state,
  50. xfs_da_state_blk_t *old_node_blk,
  51. xfs_da_state_blk_t *new_node_blk);
  52. /*
  53. * Routines used for shrinking the Btree.
  54. */
  55. STATIC int xfs_da3_root_join(xfs_da_state_t *state,
  56. xfs_da_state_blk_t *root_blk);
  57. STATIC int xfs_da3_node_toosmall(xfs_da_state_t *state, int *retval);
  58. STATIC void xfs_da3_node_remove(xfs_da_state_t *state,
  59. xfs_da_state_blk_t *drop_blk);
  60. STATIC void xfs_da3_node_unbalance(xfs_da_state_t *state,
  61. xfs_da_state_blk_t *src_node_blk,
  62. xfs_da_state_blk_t *dst_node_blk);
  63. /*
  64. * Utility routines.
  65. */
  66. STATIC int xfs_da3_blk_unlink(xfs_da_state_t *state,
  67. xfs_da_state_blk_t *drop_blk,
  68. xfs_da_state_blk_t *save_blk);
  69. struct kmem_cache *xfs_da_state_cache; /* anchor for dir/attr state */
  70. /*
  71. * Allocate a dir-state structure.
  72. * We don't put them on the stack since they're large.
  73. */
  74. struct xfs_da_state *
  75. xfs_da_state_alloc(
  76. struct xfs_da_args *args)
  77. {
  78. struct xfs_da_state *state;
  79. state = kmem_cache_zalloc(xfs_da_state_cache, GFP_NOFS | __GFP_NOFAIL);
  80. state->args = args;
  81. state->mp = args->dp->i_mount;
  82. return state;
  83. }
  84. /*
  85. * Kill the altpath contents of a da-state structure.
  86. */
  87. STATIC void
  88. xfs_da_state_kill_altpath(xfs_da_state_t *state)
  89. {
  90. int i;
  91. for (i = 0; i < state->altpath.active; i++)
  92. state->altpath.blk[i].bp = NULL;
  93. state->altpath.active = 0;
  94. }
  95. /*
  96. * Free a da-state structure.
  97. */
  98. void
  99. xfs_da_state_free(xfs_da_state_t *state)
  100. {
  101. xfs_da_state_kill_altpath(state);
  102. #ifdef DEBUG
  103. memset((char *)state, 0, sizeof(*state));
  104. #endif /* DEBUG */
  105. kmem_cache_free(xfs_da_state_cache, state);
  106. }
  107. void
  108. xfs_da_state_reset(
  109. struct xfs_da_state *state,
  110. struct xfs_da_args *args)
  111. {
  112. xfs_da_state_kill_altpath(state);
  113. memset(state, 0, sizeof(struct xfs_da_state));
  114. state->args = args;
  115. state->mp = state->args->dp->i_mount;
  116. }
  117. static inline int xfs_dabuf_nfsb(struct xfs_mount *mp, int whichfork)
  118. {
  119. if (whichfork == XFS_DATA_FORK)
  120. return mp->m_dir_geo->fsbcount;
  121. return mp->m_attr_geo->fsbcount;
  122. }
  123. void
  124. xfs_da3_node_hdr_from_disk(
  125. struct xfs_mount *mp,
  126. struct xfs_da3_icnode_hdr *to,
  127. struct xfs_da_intnode *from)
  128. {
  129. if (xfs_has_crc(mp)) {
  130. struct xfs_da3_intnode *from3 = (struct xfs_da3_intnode *)from;
  131. to->forw = be32_to_cpu(from3->hdr.info.hdr.forw);
  132. to->back = be32_to_cpu(from3->hdr.info.hdr.back);
  133. to->magic = be16_to_cpu(from3->hdr.info.hdr.magic);
  134. to->count = be16_to_cpu(from3->hdr.__count);
  135. to->level = be16_to_cpu(from3->hdr.__level);
  136. to->btree = from3->__btree;
  137. ASSERT(to->magic == XFS_DA3_NODE_MAGIC);
  138. } else {
  139. to->forw = be32_to_cpu(from->hdr.info.forw);
  140. to->back = be32_to_cpu(from->hdr.info.back);
  141. to->magic = be16_to_cpu(from->hdr.info.magic);
  142. to->count = be16_to_cpu(from->hdr.__count);
  143. to->level = be16_to_cpu(from->hdr.__level);
  144. to->btree = from->__btree;
  145. ASSERT(to->magic == XFS_DA_NODE_MAGIC);
  146. }
  147. }
  148. void
  149. xfs_da3_node_hdr_to_disk(
  150. struct xfs_mount *mp,
  151. struct xfs_da_intnode *to,
  152. struct xfs_da3_icnode_hdr *from)
  153. {
  154. if (xfs_has_crc(mp)) {
  155. struct xfs_da3_intnode *to3 = (struct xfs_da3_intnode *)to;
  156. ASSERT(from->magic == XFS_DA3_NODE_MAGIC);
  157. to3->hdr.info.hdr.forw = cpu_to_be32(from->forw);
  158. to3->hdr.info.hdr.back = cpu_to_be32(from->back);
  159. to3->hdr.info.hdr.magic = cpu_to_be16(from->magic);
  160. to3->hdr.__count = cpu_to_be16(from->count);
  161. to3->hdr.__level = cpu_to_be16(from->level);
  162. } else {
  163. ASSERT(from->magic == XFS_DA_NODE_MAGIC);
  164. to->hdr.info.forw = cpu_to_be32(from->forw);
  165. to->hdr.info.back = cpu_to_be32(from->back);
  166. to->hdr.info.magic = cpu_to_be16(from->magic);
  167. to->hdr.__count = cpu_to_be16(from->count);
  168. to->hdr.__level = cpu_to_be16(from->level);
  169. }
  170. }
  171. /*
  172. * Verify an xfs_da3_blkinfo structure. Note that the da3 fields are only
  173. * accessible on v5 filesystems. This header format is common across da node,
  174. * attr leaf and dir leaf blocks.
  175. */
  176. xfs_failaddr_t
  177. xfs_da3_blkinfo_verify(
  178. struct xfs_buf *bp,
  179. struct xfs_da3_blkinfo *hdr3)
  180. {
  181. struct xfs_mount *mp = bp->b_mount;
  182. struct xfs_da_blkinfo *hdr = &hdr3->hdr;
  183. if (!xfs_verify_magic16(bp, hdr->magic))
  184. return __this_address;
  185. if (xfs_has_crc(mp)) {
  186. if (!uuid_equal(&hdr3->uuid, &mp->m_sb.sb_meta_uuid))
  187. return __this_address;
  188. if (be64_to_cpu(hdr3->blkno) != xfs_buf_daddr(bp))
  189. return __this_address;
  190. if (!xfs_log_check_lsn(mp, be64_to_cpu(hdr3->lsn)))
  191. return __this_address;
  192. }
  193. return NULL;
  194. }
  195. static xfs_failaddr_t
  196. xfs_da3_node_verify(
  197. struct xfs_buf *bp)
  198. {
  199. struct xfs_mount *mp = bp->b_mount;
  200. struct xfs_da_intnode *hdr = bp->b_addr;
  201. struct xfs_da3_icnode_hdr ichdr;
  202. xfs_failaddr_t fa;
  203. xfs_da3_node_hdr_from_disk(mp, &ichdr, hdr);
  204. fa = xfs_da3_blkinfo_verify(bp, bp->b_addr);
  205. if (fa)
  206. return fa;
  207. if (ichdr.level == 0)
  208. return __this_address;
  209. if (ichdr.level > XFS_DA_NODE_MAXDEPTH)
  210. return __this_address;
  211. if (ichdr.count == 0)
  212. return __this_address;
  213. /*
  214. * we don't know if the node is for and attribute or directory tree,
  215. * so only fail if the count is outside both bounds
  216. */
  217. if (ichdr.count > mp->m_dir_geo->node_ents &&
  218. ichdr.count > mp->m_attr_geo->node_ents)
  219. return __this_address;
  220. /* XXX: hash order check? */
  221. return NULL;
  222. }
  223. static void
  224. xfs_da3_node_write_verify(
  225. struct xfs_buf *bp)
  226. {
  227. struct xfs_mount *mp = bp->b_mount;
  228. struct xfs_buf_log_item *bip = bp->b_log_item;
  229. struct xfs_da3_node_hdr *hdr3 = bp->b_addr;
  230. xfs_failaddr_t fa;
  231. fa = xfs_da3_node_verify(bp);
  232. if (fa) {
  233. xfs_verifier_error(bp, -EFSCORRUPTED, fa);
  234. return;
  235. }
  236. if (!xfs_has_crc(mp))
  237. return;
  238. if (bip)
  239. hdr3->info.lsn = cpu_to_be64(bip->bli_item.li_lsn);
  240. xfs_buf_update_cksum(bp, XFS_DA3_NODE_CRC_OFF);
  241. }
  242. /*
  243. * leaf/node format detection on trees is sketchy, so a node read can be done on
  244. * leaf level blocks when detection identifies the tree as a node format tree
  245. * incorrectly. In this case, we need to swap the verifier to match the correct
  246. * format of the block being read.
  247. */
  248. static void
  249. xfs_da3_node_read_verify(
  250. struct xfs_buf *bp)
  251. {
  252. struct xfs_da_blkinfo *info = bp->b_addr;
  253. xfs_failaddr_t fa;
  254. switch (be16_to_cpu(info->magic)) {
  255. case XFS_DA3_NODE_MAGIC:
  256. if (!xfs_buf_verify_cksum(bp, XFS_DA3_NODE_CRC_OFF)) {
  257. xfs_verifier_error(bp, -EFSBADCRC,
  258. __this_address);
  259. break;
  260. }
  261. fallthrough;
  262. case XFS_DA_NODE_MAGIC:
  263. fa = xfs_da3_node_verify(bp);
  264. if (fa)
  265. xfs_verifier_error(bp, -EFSCORRUPTED, fa);
  266. return;
  267. case XFS_ATTR_LEAF_MAGIC:
  268. case XFS_ATTR3_LEAF_MAGIC:
  269. bp->b_ops = &xfs_attr3_leaf_buf_ops;
  270. bp->b_ops->verify_read(bp);
  271. return;
  272. case XFS_DIR2_LEAFN_MAGIC:
  273. case XFS_DIR3_LEAFN_MAGIC:
  274. bp->b_ops = &xfs_dir3_leafn_buf_ops;
  275. bp->b_ops->verify_read(bp);
  276. return;
  277. default:
  278. xfs_verifier_error(bp, -EFSCORRUPTED, __this_address);
  279. break;
  280. }
  281. }
  282. /* Verify the structure of a da3 block. */
  283. static xfs_failaddr_t
  284. xfs_da3_node_verify_struct(
  285. struct xfs_buf *bp)
  286. {
  287. struct xfs_da_blkinfo *info = bp->b_addr;
  288. switch (be16_to_cpu(info->magic)) {
  289. case XFS_DA3_NODE_MAGIC:
  290. case XFS_DA_NODE_MAGIC:
  291. return xfs_da3_node_verify(bp);
  292. case XFS_ATTR_LEAF_MAGIC:
  293. case XFS_ATTR3_LEAF_MAGIC:
  294. bp->b_ops = &xfs_attr3_leaf_buf_ops;
  295. return bp->b_ops->verify_struct(bp);
  296. case XFS_DIR2_LEAFN_MAGIC:
  297. case XFS_DIR3_LEAFN_MAGIC:
  298. bp->b_ops = &xfs_dir3_leafn_buf_ops;
  299. return bp->b_ops->verify_struct(bp);
  300. default:
  301. return __this_address;
  302. }
  303. }
  304. const struct xfs_buf_ops xfs_da3_node_buf_ops = {
  305. .name = "xfs_da3_node",
  306. .magic16 = { cpu_to_be16(XFS_DA_NODE_MAGIC),
  307. cpu_to_be16(XFS_DA3_NODE_MAGIC) },
  308. .verify_read = xfs_da3_node_read_verify,
  309. .verify_write = xfs_da3_node_write_verify,
  310. .verify_struct = xfs_da3_node_verify_struct,
  311. };
  312. static int
  313. xfs_da3_node_set_type(
  314. struct xfs_trans *tp,
  315. struct xfs_buf *bp)
  316. {
  317. struct xfs_da_blkinfo *info = bp->b_addr;
  318. switch (be16_to_cpu(info->magic)) {
  319. case XFS_DA_NODE_MAGIC:
  320. case XFS_DA3_NODE_MAGIC:
  321. xfs_trans_buf_set_type(tp, bp, XFS_BLFT_DA_NODE_BUF);
  322. return 0;
  323. case XFS_ATTR_LEAF_MAGIC:
  324. case XFS_ATTR3_LEAF_MAGIC:
  325. xfs_trans_buf_set_type(tp, bp, XFS_BLFT_ATTR_LEAF_BUF);
  326. return 0;
  327. case XFS_DIR2_LEAFN_MAGIC:
  328. case XFS_DIR3_LEAFN_MAGIC:
  329. xfs_trans_buf_set_type(tp, bp, XFS_BLFT_DIR_LEAFN_BUF);
  330. return 0;
  331. default:
  332. XFS_CORRUPTION_ERROR(__func__, XFS_ERRLEVEL_LOW, tp->t_mountp,
  333. info, sizeof(*info));
  334. xfs_trans_brelse(tp, bp);
  335. return -EFSCORRUPTED;
  336. }
  337. }
  338. int
  339. xfs_da3_node_read(
  340. struct xfs_trans *tp,
  341. struct xfs_inode *dp,
  342. xfs_dablk_t bno,
  343. struct xfs_buf **bpp,
  344. int whichfork)
  345. {
  346. int error;
  347. error = xfs_da_read_buf(tp, dp, bno, 0, bpp, whichfork,
  348. &xfs_da3_node_buf_ops);
  349. if (error || !*bpp || !tp)
  350. return error;
  351. return xfs_da3_node_set_type(tp, *bpp);
  352. }
  353. int
  354. xfs_da3_node_read_mapped(
  355. struct xfs_trans *tp,
  356. struct xfs_inode *dp,
  357. xfs_daddr_t mappedbno,
  358. struct xfs_buf **bpp,
  359. int whichfork)
  360. {
  361. struct xfs_mount *mp = dp->i_mount;
  362. int error;
  363. error = xfs_trans_read_buf(mp, tp, mp->m_ddev_targp, mappedbno,
  364. XFS_FSB_TO_BB(mp, xfs_dabuf_nfsb(mp, whichfork)), 0,
  365. bpp, &xfs_da3_node_buf_ops);
  366. if (error || !*bpp)
  367. return error;
  368. if (whichfork == XFS_ATTR_FORK)
  369. xfs_buf_set_ref(*bpp, XFS_ATTR_BTREE_REF);
  370. else
  371. xfs_buf_set_ref(*bpp, XFS_DIR_BTREE_REF);
  372. if (!tp)
  373. return 0;
  374. return xfs_da3_node_set_type(tp, *bpp);
  375. }
  376. /*========================================================================
  377. * Routines used for growing the Btree.
  378. *========================================================================*/
  379. /*
  380. * Create the initial contents of an intermediate node.
  381. */
  382. int
  383. xfs_da3_node_create(
  384. struct xfs_da_args *args,
  385. xfs_dablk_t blkno,
  386. int level,
  387. struct xfs_buf **bpp,
  388. int whichfork)
  389. {
  390. struct xfs_da_intnode *node;
  391. struct xfs_trans *tp = args->trans;
  392. struct xfs_mount *mp = tp->t_mountp;
  393. struct xfs_da3_icnode_hdr ichdr = {0};
  394. struct xfs_buf *bp;
  395. int error;
  396. struct xfs_inode *dp = args->dp;
  397. trace_xfs_da_node_create(args);
  398. ASSERT(level <= XFS_DA_NODE_MAXDEPTH);
  399. error = xfs_da_get_buf(tp, dp, blkno, &bp, whichfork);
  400. if (error)
  401. return error;
  402. bp->b_ops = &xfs_da3_node_buf_ops;
  403. xfs_trans_buf_set_type(tp, bp, XFS_BLFT_DA_NODE_BUF);
  404. node = bp->b_addr;
  405. if (xfs_has_crc(mp)) {
  406. struct xfs_da3_node_hdr *hdr3 = bp->b_addr;
  407. memset(hdr3, 0, sizeof(struct xfs_da3_node_hdr));
  408. ichdr.magic = XFS_DA3_NODE_MAGIC;
  409. hdr3->info.blkno = cpu_to_be64(xfs_buf_daddr(bp));
  410. hdr3->info.owner = cpu_to_be64(args->dp->i_ino);
  411. uuid_copy(&hdr3->info.uuid, &mp->m_sb.sb_meta_uuid);
  412. } else {
  413. ichdr.magic = XFS_DA_NODE_MAGIC;
  414. }
  415. ichdr.level = level;
  416. xfs_da3_node_hdr_to_disk(dp->i_mount, node, &ichdr);
  417. xfs_trans_log_buf(tp, bp,
  418. XFS_DA_LOGRANGE(node, &node->hdr, args->geo->node_hdr_size));
  419. *bpp = bp;
  420. return 0;
  421. }
  422. /*
  423. * Split a leaf node, rebalance, then possibly split
  424. * intermediate nodes, rebalance, etc.
  425. */
  426. int /* error */
  427. xfs_da3_split(
  428. struct xfs_da_state *state)
  429. {
  430. struct xfs_da_state_blk *oldblk;
  431. struct xfs_da_state_blk *newblk;
  432. struct xfs_da_state_blk *addblk;
  433. struct xfs_da_intnode *node;
  434. int max;
  435. int action = 0;
  436. int error;
  437. int i;
  438. trace_xfs_da_split(state->args);
  439. if (XFS_TEST_ERROR(false, state->mp, XFS_ERRTAG_DA_LEAF_SPLIT))
  440. return -EIO;
  441. /*
  442. * Walk back up the tree splitting/inserting/adjusting as necessary.
  443. * If we need to insert and there isn't room, split the node, then
  444. * decide which fragment to insert the new block from below into.
  445. * Note that we may split the root this way, but we need more fixup.
  446. */
  447. max = state->path.active - 1;
  448. ASSERT((max >= 0) && (max < XFS_DA_NODE_MAXDEPTH));
  449. ASSERT(state->path.blk[max].magic == XFS_ATTR_LEAF_MAGIC ||
  450. state->path.blk[max].magic == XFS_DIR2_LEAFN_MAGIC);
  451. addblk = &state->path.blk[max]; /* initial dummy value */
  452. for (i = max; (i >= 0) && addblk; state->path.active--, i--) {
  453. oldblk = &state->path.blk[i];
  454. newblk = &state->altpath.blk[i];
  455. /*
  456. * If a leaf node then
  457. * Allocate a new leaf node, then rebalance across them.
  458. * else if an intermediate node then
  459. * We split on the last layer, must we split the node?
  460. */
  461. switch (oldblk->magic) {
  462. case XFS_ATTR_LEAF_MAGIC:
  463. error = xfs_attr3_leaf_split(state, oldblk, newblk);
  464. if ((error != 0) && (error != -ENOSPC)) {
  465. return error; /* GROT: attr is inconsistent */
  466. }
  467. if (!error) {
  468. addblk = newblk;
  469. break;
  470. }
  471. /*
  472. * Entry wouldn't fit, split the leaf again. The new
  473. * extrablk will be consumed by xfs_da3_node_split if
  474. * the node is split.
  475. */
  476. state->extravalid = 1;
  477. if (state->inleaf) {
  478. state->extraafter = 0; /* before newblk */
  479. trace_xfs_attr_leaf_split_before(state->args);
  480. error = xfs_attr3_leaf_split(state, oldblk,
  481. &state->extrablk);
  482. } else {
  483. state->extraafter = 1; /* after newblk */
  484. trace_xfs_attr_leaf_split_after(state->args);
  485. error = xfs_attr3_leaf_split(state, newblk,
  486. &state->extrablk);
  487. }
  488. if (error)
  489. return error; /* GROT: attr inconsistent */
  490. addblk = newblk;
  491. break;
  492. case XFS_DIR2_LEAFN_MAGIC:
  493. error = xfs_dir2_leafn_split(state, oldblk, newblk);
  494. if (error)
  495. return error;
  496. addblk = newblk;
  497. break;
  498. case XFS_DA_NODE_MAGIC:
  499. error = xfs_da3_node_split(state, oldblk, newblk, addblk,
  500. max - i, &action);
  501. addblk->bp = NULL;
  502. if (error)
  503. return error; /* GROT: dir is inconsistent */
  504. /*
  505. * Record the newly split block for the next time thru?
  506. */
  507. if (action)
  508. addblk = newblk;
  509. else
  510. addblk = NULL;
  511. break;
  512. }
  513. /*
  514. * Update the btree to show the new hashval for this child.
  515. */
  516. xfs_da3_fixhashpath(state, &state->path);
  517. }
  518. if (!addblk)
  519. return 0;
  520. /*
  521. * xfs_da3_node_split() should have consumed any extra blocks we added
  522. * during a double leaf split in the attr fork. This is guaranteed as
  523. * we can't be here if the attr fork only has a single leaf block.
  524. */
  525. ASSERT(state->extravalid == 0 ||
  526. state->path.blk[max].magic == XFS_DIR2_LEAFN_MAGIC);
  527. /*
  528. * Split the root node.
  529. */
  530. ASSERT(state->path.active == 0);
  531. oldblk = &state->path.blk[0];
  532. error = xfs_da3_root_split(state, oldblk, addblk);
  533. if (error)
  534. goto out;
  535. /*
  536. * Update pointers to the node which used to be block 0 and just got
  537. * bumped because of the addition of a new root node. Note that the
  538. * original block 0 could be at any position in the list of blocks in
  539. * the tree.
  540. *
  541. * Note: the magic numbers and sibling pointers are in the same physical
  542. * place for both v2 and v3 headers (by design). Hence it doesn't matter
  543. * which version of the xfs_da_intnode structure we use here as the
  544. * result will be the same using either structure.
  545. */
  546. node = oldblk->bp->b_addr;
  547. if (node->hdr.info.forw) {
  548. if (be32_to_cpu(node->hdr.info.forw) != addblk->blkno) {
  549. xfs_buf_mark_corrupt(oldblk->bp);
  550. error = -EFSCORRUPTED;
  551. goto out;
  552. }
  553. node = addblk->bp->b_addr;
  554. node->hdr.info.back = cpu_to_be32(oldblk->blkno);
  555. xfs_trans_log_buf(state->args->trans, addblk->bp,
  556. XFS_DA_LOGRANGE(node, &node->hdr.info,
  557. sizeof(node->hdr.info)));
  558. }
  559. node = oldblk->bp->b_addr;
  560. if (node->hdr.info.back) {
  561. if (be32_to_cpu(node->hdr.info.back) != addblk->blkno) {
  562. xfs_buf_mark_corrupt(oldblk->bp);
  563. error = -EFSCORRUPTED;
  564. goto out;
  565. }
  566. node = addblk->bp->b_addr;
  567. node->hdr.info.forw = cpu_to_be32(oldblk->blkno);
  568. xfs_trans_log_buf(state->args->trans, addblk->bp,
  569. XFS_DA_LOGRANGE(node, &node->hdr.info,
  570. sizeof(node->hdr.info)));
  571. }
  572. out:
  573. addblk->bp = NULL;
  574. return error;
  575. }
  576. /*
  577. * Split the root. We have to create a new root and point to the two
  578. * parts (the split old root) that we just created. Copy block zero to
  579. * the EOF, extending the inode in process.
  580. */
  581. STATIC int /* error */
  582. xfs_da3_root_split(
  583. struct xfs_da_state *state,
  584. struct xfs_da_state_blk *blk1,
  585. struct xfs_da_state_blk *blk2)
  586. {
  587. struct xfs_da_intnode *node;
  588. struct xfs_da_intnode *oldroot;
  589. struct xfs_da_node_entry *btree;
  590. struct xfs_da3_icnode_hdr nodehdr;
  591. struct xfs_da_args *args;
  592. struct xfs_buf *bp;
  593. struct xfs_inode *dp;
  594. struct xfs_trans *tp;
  595. struct xfs_dir2_leaf *leaf;
  596. xfs_dablk_t blkno;
  597. int level;
  598. int error;
  599. int size;
  600. trace_xfs_da_root_split(state->args);
  601. /*
  602. * Copy the existing (incorrect) block from the root node position
  603. * to a free space somewhere.
  604. */
  605. args = state->args;
  606. error = xfs_da_grow_inode(args, &blkno);
  607. if (error)
  608. return error;
  609. dp = args->dp;
  610. tp = args->trans;
  611. error = xfs_da_get_buf(tp, dp, blkno, &bp, args->whichfork);
  612. if (error)
  613. return error;
  614. node = bp->b_addr;
  615. oldroot = blk1->bp->b_addr;
  616. if (oldroot->hdr.info.magic == cpu_to_be16(XFS_DA_NODE_MAGIC) ||
  617. oldroot->hdr.info.magic == cpu_to_be16(XFS_DA3_NODE_MAGIC)) {
  618. struct xfs_da3_icnode_hdr icnodehdr;
  619. xfs_da3_node_hdr_from_disk(dp->i_mount, &icnodehdr, oldroot);
  620. btree = icnodehdr.btree;
  621. size = (int)((char *)&btree[icnodehdr.count] - (char *)oldroot);
  622. level = icnodehdr.level;
  623. /*
  624. * we are about to copy oldroot to bp, so set up the type
  625. * of bp while we know exactly what it will be.
  626. */
  627. xfs_trans_buf_set_type(tp, bp, XFS_BLFT_DA_NODE_BUF);
  628. } else {
  629. struct xfs_dir3_icleaf_hdr leafhdr;
  630. leaf = (xfs_dir2_leaf_t *)oldroot;
  631. xfs_dir2_leaf_hdr_from_disk(dp->i_mount, &leafhdr, leaf);
  632. ASSERT(leafhdr.magic == XFS_DIR2_LEAFN_MAGIC ||
  633. leafhdr.magic == XFS_DIR3_LEAFN_MAGIC);
  634. size = (int)((char *)&leafhdr.ents[leafhdr.count] -
  635. (char *)leaf);
  636. level = 0;
  637. /*
  638. * we are about to copy oldroot to bp, so set up the type
  639. * of bp while we know exactly what it will be.
  640. */
  641. xfs_trans_buf_set_type(tp, bp, XFS_BLFT_DIR_LEAFN_BUF);
  642. }
  643. /*
  644. * we can copy most of the information in the node from one block to
  645. * another, but for CRC enabled headers we have to make sure that the
  646. * block specific identifiers are kept intact. We update the buffer
  647. * directly for this.
  648. */
  649. memcpy(node, oldroot, size);
  650. if (oldroot->hdr.info.magic == cpu_to_be16(XFS_DA3_NODE_MAGIC) ||
  651. oldroot->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC)) {
  652. struct xfs_da3_intnode *node3 = (struct xfs_da3_intnode *)node;
  653. node3->hdr.info.blkno = cpu_to_be64(xfs_buf_daddr(bp));
  654. }
  655. xfs_trans_log_buf(tp, bp, 0, size - 1);
  656. bp->b_ops = blk1->bp->b_ops;
  657. xfs_trans_buf_copy_type(bp, blk1->bp);
  658. blk1->bp = bp;
  659. blk1->blkno = blkno;
  660. /*
  661. * Set up the new root node.
  662. */
  663. error = xfs_da3_node_create(args,
  664. (args->whichfork == XFS_DATA_FORK) ? args->geo->leafblk : 0,
  665. level + 1, &bp, args->whichfork);
  666. if (error)
  667. return error;
  668. node = bp->b_addr;
  669. xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr, node);
  670. btree = nodehdr.btree;
  671. btree[0].hashval = cpu_to_be32(blk1->hashval);
  672. btree[0].before = cpu_to_be32(blk1->blkno);
  673. btree[1].hashval = cpu_to_be32(blk2->hashval);
  674. btree[1].before = cpu_to_be32(blk2->blkno);
  675. nodehdr.count = 2;
  676. xfs_da3_node_hdr_to_disk(dp->i_mount, node, &nodehdr);
  677. #ifdef DEBUG
  678. if (oldroot->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) ||
  679. oldroot->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC)) {
  680. ASSERT(blk1->blkno >= args->geo->leafblk &&
  681. blk1->blkno < args->geo->freeblk);
  682. ASSERT(blk2->blkno >= args->geo->leafblk &&
  683. blk2->blkno < args->geo->freeblk);
  684. }
  685. #endif
  686. /* Header is already logged by xfs_da_node_create */
  687. xfs_trans_log_buf(tp, bp,
  688. XFS_DA_LOGRANGE(node, btree, sizeof(xfs_da_node_entry_t) * 2));
  689. return 0;
  690. }
  691. /*
  692. * Split the node, rebalance, then add the new entry.
  693. */
  694. STATIC int /* error */
  695. xfs_da3_node_split(
  696. struct xfs_da_state *state,
  697. struct xfs_da_state_blk *oldblk,
  698. struct xfs_da_state_blk *newblk,
  699. struct xfs_da_state_blk *addblk,
  700. int treelevel,
  701. int *result)
  702. {
  703. struct xfs_da_intnode *node;
  704. struct xfs_da3_icnode_hdr nodehdr;
  705. xfs_dablk_t blkno;
  706. int newcount;
  707. int error;
  708. int useextra;
  709. struct xfs_inode *dp = state->args->dp;
  710. trace_xfs_da_node_split(state->args);
  711. node = oldblk->bp->b_addr;
  712. xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr, node);
  713. /*
  714. * With V2 dirs the extra block is data or freespace.
  715. */
  716. useextra = state->extravalid && state->args->whichfork == XFS_ATTR_FORK;
  717. newcount = 1 + useextra;
  718. /*
  719. * Do we have to split the node?
  720. */
  721. if (nodehdr.count + newcount > state->args->geo->node_ents) {
  722. /*
  723. * Allocate a new node, add to the doubly linked chain of
  724. * nodes, then move some of our excess entries into it.
  725. */
  726. error = xfs_da_grow_inode(state->args, &blkno);
  727. if (error)
  728. return error; /* GROT: dir is inconsistent */
  729. error = xfs_da3_node_create(state->args, blkno, treelevel,
  730. &newblk->bp, state->args->whichfork);
  731. if (error)
  732. return error; /* GROT: dir is inconsistent */
  733. newblk->blkno = blkno;
  734. newblk->magic = XFS_DA_NODE_MAGIC;
  735. xfs_da3_node_rebalance(state, oldblk, newblk);
  736. error = xfs_da3_blk_link(state, oldblk, newblk);
  737. if (error)
  738. return error;
  739. *result = 1;
  740. } else {
  741. *result = 0;
  742. }
  743. /*
  744. * Insert the new entry(s) into the correct block
  745. * (updating last hashval in the process).
  746. *
  747. * xfs_da3_node_add() inserts BEFORE the given index,
  748. * and as a result of using node_lookup_int() we always
  749. * point to a valid entry (not after one), but a split
  750. * operation always results in a new block whose hashvals
  751. * FOLLOW the current block.
  752. *
  753. * If we had double-split op below us, then add the extra block too.
  754. */
  755. node = oldblk->bp->b_addr;
  756. xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr, node);
  757. if (oldblk->index <= nodehdr.count) {
  758. oldblk->index++;
  759. xfs_da3_node_add(state, oldblk, addblk);
  760. if (useextra) {
  761. if (state->extraafter)
  762. oldblk->index++;
  763. xfs_da3_node_add(state, oldblk, &state->extrablk);
  764. state->extravalid = 0;
  765. }
  766. } else {
  767. newblk->index++;
  768. xfs_da3_node_add(state, newblk, addblk);
  769. if (useextra) {
  770. if (state->extraafter)
  771. newblk->index++;
  772. xfs_da3_node_add(state, newblk, &state->extrablk);
  773. state->extravalid = 0;
  774. }
  775. }
  776. return 0;
  777. }
  778. /*
  779. * Balance the btree elements between two intermediate nodes,
  780. * usually one full and one empty.
  781. *
  782. * NOTE: if blk2 is empty, then it will get the upper half of blk1.
  783. */
  784. STATIC void
  785. xfs_da3_node_rebalance(
  786. struct xfs_da_state *state,
  787. struct xfs_da_state_blk *blk1,
  788. struct xfs_da_state_blk *blk2)
  789. {
  790. struct xfs_da_intnode *node1;
  791. struct xfs_da_intnode *node2;
  792. struct xfs_da_node_entry *btree1;
  793. struct xfs_da_node_entry *btree2;
  794. struct xfs_da_node_entry *btree_s;
  795. struct xfs_da_node_entry *btree_d;
  796. struct xfs_da3_icnode_hdr nodehdr1;
  797. struct xfs_da3_icnode_hdr nodehdr2;
  798. struct xfs_trans *tp;
  799. int count;
  800. int tmp;
  801. int swap = 0;
  802. struct xfs_inode *dp = state->args->dp;
  803. trace_xfs_da_node_rebalance(state->args);
  804. node1 = blk1->bp->b_addr;
  805. node2 = blk2->bp->b_addr;
  806. xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr1, node1);
  807. xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr2, node2);
  808. btree1 = nodehdr1.btree;
  809. btree2 = nodehdr2.btree;
  810. /*
  811. * Figure out how many entries need to move, and in which direction.
  812. * Swap the nodes around if that makes it simpler.
  813. */
  814. if (nodehdr1.count > 0 && nodehdr2.count > 0 &&
  815. ((be32_to_cpu(btree2[0].hashval) < be32_to_cpu(btree1[0].hashval)) ||
  816. (be32_to_cpu(btree2[nodehdr2.count - 1].hashval) <
  817. be32_to_cpu(btree1[nodehdr1.count - 1].hashval)))) {
  818. swap(node1, node2);
  819. xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr1, node1);
  820. xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr2, node2);
  821. btree1 = nodehdr1.btree;
  822. btree2 = nodehdr2.btree;
  823. swap = 1;
  824. }
  825. count = (nodehdr1.count - nodehdr2.count) / 2;
  826. if (count == 0)
  827. return;
  828. tp = state->args->trans;
  829. /*
  830. * Two cases: high-to-low and low-to-high.
  831. */
  832. if (count > 0) {
  833. /*
  834. * Move elements in node2 up to make a hole.
  835. */
  836. tmp = nodehdr2.count;
  837. if (tmp > 0) {
  838. tmp *= (uint)sizeof(xfs_da_node_entry_t);
  839. btree_s = &btree2[0];
  840. btree_d = &btree2[count];
  841. memmove(btree_d, btree_s, tmp);
  842. }
  843. /*
  844. * Move the req'd B-tree elements from high in node1 to
  845. * low in node2.
  846. */
  847. nodehdr2.count += count;
  848. tmp = count * (uint)sizeof(xfs_da_node_entry_t);
  849. btree_s = &btree1[nodehdr1.count - count];
  850. btree_d = &btree2[0];
  851. memcpy(btree_d, btree_s, tmp);
  852. nodehdr1.count -= count;
  853. } else {
  854. /*
  855. * Move the req'd B-tree elements from low in node2 to
  856. * high in node1.
  857. */
  858. count = -count;
  859. tmp = count * (uint)sizeof(xfs_da_node_entry_t);
  860. btree_s = &btree2[0];
  861. btree_d = &btree1[nodehdr1.count];
  862. memcpy(btree_d, btree_s, tmp);
  863. nodehdr1.count += count;
  864. xfs_trans_log_buf(tp, blk1->bp,
  865. XFS_DA_LOGRANGE(node1, btree_d, tmp));
  866. /*
  867. * Move elements in node2 down to fill the hole.
  868. */
  869. tmp = nodehdr2.count - count;
  870. tmp *= (uint)sizeof(xfs_da_node_entry_t);
  871. btree_s = &btree2[count];
  872. btree_d = &btree2[0];
  873. memmove(btree_d, btree_s, tmp);
  874. nodehdr2.count -= count;
  875. }
  876. /*
  877. * Log header of node 1 and all current bits of node 2.
  878. */
  879. xfs_da3_node_hdr_to_disk(dp->i_mount, node1, &nodehdr1);
  880. xfs_trans_log_buf(tp, blk1->bp,
  881. XFS_DA_LOGRANGE(node1, &node1->hdr,
  882. state->args->geo->node_hdr_size));
  883. xfs_da3_node_hdr_to_disk(dp->i_mount, node2, &nodehdr2);
  884. xfs_trans_log_buf(tp, blk2->bp,
  885. XFS_DA_LOGRANGE(node2, &node2->hdr,
  886. state->args->geo->node_hdr_size +
  887. (sizeof(btree2[0]) * nodehdr2.count)));
  888. /*
  889. * Record the last hashval from each block for upward propagation.
  890. * (note: don't use the swapped node pointers)
  891. */
  892. if (swap) {
  893. node1 = blk1->bp->b_addr;
  894. node2 = blk2->bp->b_addr;
  895. xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr1, node1);
  896. xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr2, node2);
  897. btree1 = nodehdr1.btree;
  898. btree2 = nodehdr2.btree;
  899. }
  900. blk1->hashval = be32_to_cpu(btree1[nodehdr1.count - 1].hashval);
  901. blk2->hashval = be32_to_cpu(btree2[nodehdr2.count - 1].hashval);
  902. /*
  903. * Adjust the expected index for insertion.
  904. */
  905. if (blk1->index >= nodehdr1.count) {
  906. blk2->index = blk1->index - nodehdr1.count;
  907. blk1->index = nodehdr1.count + 1; /* make it invalid */
  908. }
  909. }
  910. /*
  911. * Add a new entry to an intermediate node.
  912. */
  913. STATIC void
  914. xfs_da3_node_add(
  915. struct xfs_da_state *state,
  916. struct xfs_da_state_blk *oldblk,
  917. struct xfs_da_state_blk *newblk)
  918. {
  919. struct xfs_da_intnode *node;
  920. struct xfs_da3_icnode_hdr nodehdr;
  921. struct xfs_da_node_entry *btree;
  922. int tmp;
  923. struct xfs_inode *dp = state->args->dp;
  924. trace_xfs_da_node_add(state->args);
  925. node = oldblk->bp->b_addr;
  926. xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr, node);
  927. btree = nodehdr.btree;
  928. ASSERT(oldblk->index >= 0 && oldblk->index <= nodehdr.count);
  929. ASSERT(newblk->blkno != 0);
  930. if (state->args->whichfork == XFS_DATA_FORK)
  931. ASSERT(newblk->blkno >= state->args->geo->leafblk &&
  932. newblk->blkno < state->args->geo->freeblk);
  933. /*
  934. * We may need to make some room before we insert the new node.
  935. */
  936. tmp = 0;
  937. if (oldblk->index < nodehdr.count) {
  938. tmp = (nodehdr.count - oldblk->index) * (uint)sizeof(*btree);
  939. memmove(&btree[oldblk->index + 1], &btree[oldblk->index], tmp);
  940. }
  941. btree[oldblk->index].hashval = cpu_to_be32(newblk->hashval);
  942. btree[oldblk->index].before = cpu_to_be32(newblk->blkno);
  943. xfs_trans_log_buf(state->args->trans, oldblk->bp,
  944. XFS_DA_LOGRANGE(node, &btree[oldblk->index],
  945. tmp + sizeof(*btree)));
  946. nodehdr.count += 1;
  947. xfs_da3_node_hdr_to_disk(dp->i_mount, node, &nodehdr);
  948. xfs_trans_log_buf(state->args->trans, oldblk->bp,
  949. XFS_DA_LOGRANGE(node, &node->hdr,
  950. state->args->geo->node_hdr_size));
  951. /*
  952. * Copy the last hash value from the oldblk to propagate upwards.
  953. */
  954. oldblk->hashval = be32_to_cpu(btree[nodehdr.count - 1].hashval);
  955. }
  956. /*========================================================================
  957. * Routines used for shrinking the Btree.
  958. *========================================================================*/
  959. /*
  960. * Deallocate an empty leaf node, remove it from its parent,
  961. * possibly deallocating that block, etc...
  962. */
  963. int
  964. xfs_da3_join(
  965. struct xfs_da_state *state)
  966. {
  967. struct xfs_da_state_blk *drop_blk;
  968. struct xfs_da_state_blk *save_blk;
  969. int action = 0;
  970. int error;
  971. trace_xfs_da_join(state->args);
  972. drop_blk = &state->path.blk[ state->path.active-1 ];
  973. save_blk = &state->altpath.blk[ state->path.active-1 ];
  974. ASSERT(state->path.blk[0].magic == XFS_DA_NODE_MAGIC);
  975. ASSERT(drop_blk->magic == XFS_ATTR_LEAF_MAGIC ||
  976. drop_blk->magic == XFS_DIR2_LEAFN_MAGIC);
  977. /*
  978. * Walk back up the tree joining/deallocating as necessary.
  979. * When we stop dropping blocks, break out.
  980. */
  981. for ( ; state->path.active >= 2; drop_blk--, save_blk--,
  982. state->path.active--) {
  983. /*
  984. * See if we can combine the block with a neighbor.
  985. * (action == 0) => no options, just leave
  986. * (action == 1) => coalesce, then unlink
  987. * (action == 2) => block empty, unlink it
  988. */
  989. switch (drop_blk->magic) {
  990. case XFS_ATTR_LEAF_MAGIC:
  991. error = xfs_attr3_leaf_toosmall(state, &action);
  992. if (error)
  993. return error;
  994. if (action == 0)
  995. return 0;
  996. xfs_attr3_leaf_unbalance(state, drop_blk, save_blk);
  997. break;
  998. case XFS_DIR2_LEAFN_MAGIC:
  999. error = xfs_dir2_leafn_toosmall(state, &action);
  1000. if (error)
  1001. return error;
  1002. if (action == 0)
  1003. return 0;
  1004. xfs_dir2_leafn_unbalance(state, drop_blk, save_blk);
  1005. break;
  1006. case XFS_DA_NODE_MAGIC:
  1007. /*
  1008. * Remove the offending node, fixup hashvals,
  1009. * check for a toosmall neighbor.
  1010. */
  1011. xfs_da3_node_remove(state, drop_blk);
  1012. xfs_da3_fixhashpath(state, &state->path);
  1013. error = xfs_da3_node_toosmall(state, &action);
  1014. if (error)
  1015. return error;
  1016. if (action == 0)
  1017. return 0;
  1018. xfs_da3_node_unbalance(state, drop_blk, save_blk);
  1019. break;
  1020. }
  1021. xfs_da3_fixhashpath(state, &state->altpath);
  1022. error = xfs_da3_blk_unlink(state, drop_blk, save_blk);
  1023. xfs_da_state_kill_altpath(state);
  1024. if (error)
  1025. return error;
  1026. error = xfs_da_shrink_inode(state->args, drop_blk->blkno,
  1027. drop_blk->bp);
  1028. drop_blk->bp = NULL;
  1029. if (error)
  1030. return error;
  1031. }
  1032. /*
  1033. * We joined all the way to the top. If it turns out that
  1034. * we only have one entry in the root, make the child block
  1035. * the new root.
  1036. */
  1037. xfs_da3_node_remove(state, drop_blk);
  1038. xfs_da3_fixhashpath(state, &state->path);
  1039. error = xfs_da3_root_join(state, &state->path.blk[0]);
  1040. return error;
  1041. }
  1042. #ifdef DEBUG
  1043. static void
  1044. xfs_da_blkinfo_onlychild_validate(struct xfs_da_blkinfo *blkinfo, __u16 level)
  1045. {
  1046. __be16 magic = blkinfo->magic;
  1047. if (level == 1) {
  1048. ASSERT(magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) ||
  1049. magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC) ||
  1050. magic == cpu_to_be16(XFS_ATTR_LEAF_MAGIC) ||
  1051. magic == cpu_to_be16(XFS_ATTR3_LEAF_MAGIC));
  1052. } else {
  1053. ASSERT(magic == cpu_to_be16(XFS_DA_NODE_MAGIC) ||
  1054. magic == cpu_to_be16(XFS_DA3_NODE_MAGIC));
  1055. }
  1056. ASSERT(!blkinfo->forw);
  1057. ASSERT(!blkinfo->back);
  1058. }
  1059. #else /* !DEBUG */
  1060. #define xfs_da_blkinfo_onlychild_validate(blkinfo, level)
  1061. #endif /* !DEBUG */
  1062. /*
  1063. * We have only one entry in the root. Copy the only remaining child of
  1064. * the old root to block 0 as the new root node.
  1065. */
  1066. STATIC int
  1067. xfs_da3_root_join(
  1068. struct xfs_da_state *state,
  1069. struct xfs_da_state_blk *root_blk)
  1070. {
  1071. struct xfs_da_intnode *oldroot;
  1072. struct xfs_da_args *args;
  1073. xfs_dablk_t child;
  1074. struct xfs_buf *bp;
  1075. struct xfs_da3_icnode_hdr oldroothdr;
  1076. int error;
  1077. struct xfs_inode *dp = state->args->dp;
  1078. trace_xfs_da_root_join(state->args);
  1079. ASSERT(root_blk->magic == XFS_DA_NODE_MAGIC);
  1080. args = state->args;
  1081. oldroot = root_blk->bp->b_addr;
  1082. xfs_da3_node_hdr_from_disk(dp->i_mount, &oldroothdr, oldroot);
  1083. ASSERT(oldroothdr.forw == 0);
  1084. ASSERT(oldroothdr.back == 0);
  1085. /*
  1086. * If the root has more than one child, then don't do anything.
  1087. */
  1088. if (oldroothdr.count > 1)
  1089. return 0;
  1090. /*
  1091. * Read in the (only) child block, then copy those bytes into
  1092. * the root block's buffer and free the original child block.
  1093. */
  1094. child = be32_to_cpu(oldroothdr.btree[0].before);
  1095. ASSERT(child != 0);
  1096. error = xfs_da3_node_read(args->trans, dp, child, &bp, args->whichfork);
  1097. if (error)
  1098. return error;
  1099. xfs_da_blkinfo_onlychild_validate(bp->b_addr, oldroothdr.level);
  1100. /*
  1101. * This could be copying a leaf back into the root block in the case of
  1102. * there only being a single leaf block left in the tree. Hence we have
  1103. * to update the b_ops pointer as well to match the buffer type change
  1104. * that could occur. For dir3 blocks we also need to update the block
  1105. * number in the buffer header.
  1106. */
  1107. memcpy(root_blk->bp->b_addr, bp->b_addr, args->geo->blksize);
  1108. root_blk->bp->b_ops = bp->b_ops;
  1109. xfs_trans_buf_copy_type(root_blk->bp, bp);
  1110. if (oldroothdr.magic == XFS_DA3_NODE_MAGIC) {
  1111. struct xfs_da3_blkinfo *da3 = root_blk->bp->b_addr;
  1112. da3->blkno = cpu_to_be64(xfs_buf_daddr(root_blk->bp));
  1113. }
  1114. xfs_trans_log_buf(args->trans, root_blk->bp, 0,
  1115. args->geo->blksize - 1);
  1116. error = xfs_da_shrink_inode(args, child, bp);
  1117. return error;
  1118. }
  1119. /*
  1120. * Check a node block and its neighbors to see if the block should be
  1121. * collapsed into one or the other neighbor. Always keep the block
  1122. * with the smaller block number.
  1123. * If the current block is over 50% full, don't try to join it, return 0.
  1124. * If the block is empty, fill in the state structure and return 2.
  1125. * If it can be collapsed, fill in the state structure and return 1.
  1126. * If nothing can be done, return 0.
  1127. */
  1128. STATIC int
  1129. xfs_da3_node_toosmall(
  1130. struct xfs_da_state *state,
  1131. int *action)
  1132. {
  1133. struct xfs_da_intnode *node;
  1134. struct xfs_da_state_blk *blk;
  1135. struct xfs_da_blkinfo *info;
  1136. xfs_dablk_t blkno;
  1137. struct xfs_buf *bp;
  1138. struct xfs_da3_icnode_hdr nodehdr;
  1139. int count;
  1140. int forward;
  1141. int error;
  1142. int retval;
  1143. int i;
  1144. struct xfs_inode *dp = state->args->dp;
  1145. trace_xfs_da_node_toosmall(state->args);
  1146. /*
  1147. * Check for the degenerate case of the block being over 50% full.
  1148. * If so, it's not worth even looking to see if we might be able
  1149. * to coalesce with a sibling.
  1150. */
  1151. blk = &state->path.blk[ state->path.active-1 ];
  1152. info = blk->bp->b_addr;
  1153. node = (xfs_da_intnode_t *)info;
  1154. xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr, node);
  1155. if (nodehdr.count > (state->args->geo->node_ents >> 1)) {
  1156. *action = 0; /* blk over 50%, don't try to join */
  1157. return 0; /* blk over 50%, don't try to join */
  1158. }
  1159. /*
  1160. * Check for the degenerate case of the block being empty.
  1161. * If the block is empty, we'll simply delete it, no need to
  1162. * coalesce it with a sibling block. We choose (arbitrarily)
  1163. * to merge with the forward block unless it is NULL.
  1164. */
  1165. if (nodehdr.count == 0) {
  1166. /*
  1167. * Make altpath point to the block we want to keep and
  1168. * path point to the block we want to drop (this one).
  1169. */
  1170. forward = (info->forw != 0);
  1171. memcpy(&state->altpath, &state->path, sizeof(state->path));
  1172. error = xfs_da3_path_shift(state, &state->altpath, forward,
  1173. 0, &retval);
  1174. if (error)
  1175. return error;
  1176. if (retval) {
  1177. *action = 0;
  1178. } else {
  1179. *action = 2;
  1180. }
  1181. return 0;
  1182. }
  1183. /*
  1184. * Examine each sibling block to see if we can coalesce with
  1185. * at least 25% free space to spare. We need to figure out
  1186. * whether to merge with the forward or the backward block.
  1187. * We prefer coalescing with the lower numbered sibling so as
  1188. * to shrink a directory over time.
  1189. */
  1190. count = state->args->geo->node_ents;
  1191. count -= state->args->geo->node_ents >> 2;
  1192. count -= nodehdr.count;
  1193. /* start with smaller blk num */
  1194. forward = nodehdr.forw < nodehdr.back;
  1195. for (i = 0; i < 2; forward = !forward, i++) {
  1196. struct xfs_da3_icnode_hdr thdr;
  1197. if (forward)
  1198. blkno = nodehdr.forw;
  1199. else
  1200. blkno = nodehdr.back;
  1201. if (blkno == 0)
  1202. continue;
  1203. error = xfs_da3_node_read(state->args->trans, dp, blkno, &bp,
  1204. state->args->whichfork);
  1205. if (error)
  1206. return error;
  1207. node = bp->b_addr;
  1208. xfs_da3_node_hdr_from_disk(dp->i_mount, &thdr, node);
  1209. xfs_trans_brelse(state->args->trans, bp);
  1210. if (count - thdr.count >= 0)
  1211. break; /* fits with at least 25% to spare */
  1212. }
  1213. if (i >= 2) {
  1214. *action = 0;
  1215. return 0;
  1216. }
  1217. /*
  1218. * Make altpath point to the block we want to keep (the lower
  1219. * numbered block) and path point to the block we want to drop.
  1220. */
  1221. memcpy(&state->altpath, &state->path, sizeof(state->path));
  1222. if (blkno < blk->blkno) {
  1223. error = xfs_da3_path_shift(state, &state->altpath, forward,
  1224. 0, &retval);
  1225. } else {
  1226. error = xfs_da3_path_shift(state, &state->path, forward,
  1227. 0, &retval);
  1228. }
  1229. if (error)
  1230. return error;
  1231. if (retval) {
  1232. *action = 0;
  1233. return 0;
  1234. }
  1235. *action = 1;
  1236. return 0;
  1237. }
  1238. /*
  1239. * Pick up the last hashvalue from an intermediate node.
  1240. */
  1241. STATIC uint
  1242. xfs_da3_node_lasthash(
  1243. struct xfs_inode *dp,
  1244. struct xfs_buf *bp,
  1245. int *count)
  1246. {
  1247. struct xfs_da3_icnode_hdr nodehdr;
  1248. xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr, bp->b_addr);
  1249. if (count)
  1250. *count = nodehdr.count;
  1251. if (!nodehdr.count)
  1252. return 0;
  1253. return be32_to_cpu(nodehdr.btree[nodehdr.count - 1].hashval);
  1254. }
  1255. /*
  1256. * Walk back up the tree adjusting hash values as necessary,
  1257. * when we stop making changes, return.
  1258. */
  1259. void
  1260. xfs_da3_fixhashpath(
  1261. struct xfs_da_state *state,
  1262. struct xfs_da_state_path *path)
  1263. {
  1264. struct xfs_da_state_blk *blk;
  1265. struct xfs_da_intnode *node;
  1266. struct xfs_da_node_entry *btree;
  1267. xfs_dahash_t lasthash=0;
  1268. int level;
  1269. int count;
  1270. struct xfs_inode *dp = state->args->dp;
  1271. trace_xfs_da_fixhashpath(state->args);
  1272. level = path->active-1;
  1273. blk = &path->blk[ level ];
  1274. switch (blk->magic) {
  1275. case XFS_ATTR_LEAF_MAGIC:
  1276. lasthash = xfs_attr_leaf_lasthash(blk->bp, &count);
  1277. if (count == 0)
  1278. return;
  1279. break;
  1280. case XFS_DIR2_LEAFN_MAGIC:
  1281. lasthash = xfs_dir2_leaf_lasthash(dp, blk->bp, &count);
  1282. if (count == 0)
  1283. return;
  1284. break;
  1285. case XFS_DA_NODE_MAGIC:
  1286. lasthash = xfs_da3_node_lasthash(dp, blk->bp, &count);
  1287. if (count == 0)
  1288. return;
  1289. break;
  1290. }
  1291. for (blk--, level--; level >= 0; blk--, level--) {
  1292. struct xfs_da3_icnode_hdr nodehdr;
  1293. node = blk->bp->b_addr;
  1294. xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr, node);
  1295. btree = nodehdr.btree;
  1296. if (be32_to_cpu(btree[blk->index].hashval) == lasthash)
  1297. break;
  1298. blk->hashval = lasthash;
  1299. btree[blk->index].hashval = cpu_to_be32(lasthash);
  1300. xfs_trans_log_buf(state->args->trans, blk->bp,
  1301. XFS_DA_LOGRANGE(node, &btree[blk->index],
  1302. sizeof(*btree)));
  1303. lasthash = be32_to_cpu(btree[nodehdr.count - 1].hashval);
  1304. }
  1305. }
  1306. /*
  1307. * Remove an entry from an intermediate node.
  1308. */
  1309. STATIC void
  1310. xfs_da3_node_remove(
  1311. struct xfs_da_state *state,
  1312. struct xfs_da_state_blk *drop_blk)
  1313. {
  1314. struct xfs_da_intnode *node;
  1315. struct xfs_da3_icnode_hdr nodehdr;
  1316. struct xfs_da_node_entry *btree;
  1317. int index;
  1318. int tmp;
  1319. struct xfs_inode *dp = state->args->dp;
  1320. trace_xfs_da_node_remove(state->args);
  1321. node = drop_blk->bp->b_addr;
  1322. xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr, node);
  1323. ASSERT(drop_blk->index < nodehdr.count);
  1324. ASSERT(drop_blk->index >= 0);
  1325. /*
  1326. * Copy over the offending entry, or just zero it out.
  1327. */
  1328. index = drop_blk->index;
  1329. btree = nodehdr.btree;
  1330. if (index < nodehdr.count - 1) {
  1331. tmp = nodehdr.count - index - 1;
  1332. tmp *= (uint)sizeof(xfs_da_node_entry_t);
  1333. memmove(&btree[index], &btree[index + 1], tmp);
  1334. xfs_trans_log_buf(state->args->trans, drop_blk->bp,
  1335. XFS_DA_LOGRANGE(node, &btree[index], tmp));
  1336. index = nodehdr.count - 1;
  1337. }
  1338. memset(&btree[index], 0, sizeof(xfs_da_node_entry_t));
  1339. xfs_trans_log_buf(state->args->trans, drop_blk->bp,
  1340. XFS_DA_LOGRANGE(node, &btree[index], sizeof(btree[index])));
  1341. nodehdr.count -= 1;
  1342. xfs_da3_node_hdr_to_disk(dp->i_mount, node, &nodehdr);
  1343. xfs_trans_log_buf(state->args->trans, drop_blk->bp,
  1344. XFS_DA_LOGRANGE(node, &node->hdr, state->args->geo->node_hdr_size));
  1345. /*
  1346. * Copy the last hash value from the block to propagate upwards.
  1347. */
  1348. drop_blk->hashval = be32_to_cpu(btree[index - 1].hashval);
  1349. }
  1350. /*
  1351. * Unbalance the elements between two intermediate nodes,
  1352. * move all Btree elements from one node into another.
  1353. */
  1354. STATIC void
  1355. xfs_da3_node_unbalance(
  1356. struct xfs_da_state *state,
  1357. struct xfs_da_state_blk *drop_blk,
  1358. struct xfs_da_state_blk *save_blk)
  1359. {
  1360. struct xfs_da_intnode *drop_node;
  1361. struct xfs_da_intnode *save_node;
  1362. struct xfs_da_node_entry *drop_btree;
  1363. struct xfs_da_node_entry *save_btree;
  1364. struct xfs_da3_icnode_hdr drop_hdr;
  1365. struct xfs_da3_icnode_hdr save_hdr;
  1366. struct xfs_trans *tp;
  1367. int sindex;
  1368. int tmp;
  1369. struct xfs_inode *dp = state->args->dp;
  1370. trace_xfs_da_node_unbalance(state->args);
  1371. drop_node = drop_blk->bp->b_addr;
  1372. save_node = save_blk->bp->b_addr;
  1373. xfs_da3_node_hdr_from_disk(dp->i_mount, &drop_hdr, drop_node);
  1374. xfs_da3_node_hdr_from_disk(dp->i_mount, &save_hdr, save_node);
  1375. drop_btree = drop_hdr.btree;
  1376. save_btree = save_hdr.btree;
  1377. tp = state->args->trans;
  1378. /*
  1379. * If the dying block has lower hashvals, then move all the
  1380. * elements in the remaining block up to make a hole.
  1381. */
  1382. if ((be32_to_cpu(drop_btree[0].hashval) <
  1383. be32_to_cpu(save_btree[0].hashval)) ||
  1384. (be32_to_cpu(drop_btree[drop_hdr.count - 1].hashval) <
  1385. be32_to_cpu(save_btree[save_hdr.count - 1].hashval))) {
  1386. /* XXX: check this - is memmove dst correct? */
  1387. tmp = save_hdr.count * sizeof(xfs_da_node_entry_t);
  1388. memmove(&save_btree[drop_hdr.count], &save_btree[0], tmp);
  1389. sindex = 0;
  1390. xfs_trans_log_buf(tp, save_blk->bp,
  1391. XFS_DA_LOGRANGE(save_node, &save_btree[0],
  1392. (save_hdr.count + drop_hdr.count) *
  1393. sizeof(xfs_da_node_entry_t)));
  1394. } else {
  1395. sindex = save_hdr.count;
  1396. xfs_trans_log_buf(tp, save_blk->bp,
  1397. XFS_DA_LOGRANGE(save_node, &save_btree[sindex],
  1398. drop_hdr.count * sizeof(xfs_da_node_entry_t)));
  1399. }
  1400. /*
  1401. * Move all the B-tree elements from drop_blk to save_blk.
  1402. */
  1403. tmp = drop_hdr.count * (uint)sizeof(xfs_da_node_entry_t);
  1404. memcpy(&save_btree[sindex], &drop_btree[0], tmp);
  1405. save_hdr.count += drop_hdr.count;
  1406. xfs_da3_node_hdr_to_disk(dp->i_mount, save_node, &save_hdr);
  1407. xfs_trans_log_buf(tp, save_blk->bp,
  1408. XFS_DA_LOGRANGE(save_node, &save_node->hdr,
  1409. state->args->geo->node_hdr_size));
  1410. /*
  1411. * Save the last hashval in the remaining block for upward propagation.
  1412. */
  1413. save_blk->hashval = be32_to_cpu(save_btree[save_hdr.count - 1].hashval);
  1414. }
  1415. /*========================================================================
  1416. * Routines used for finding things in the Btree.
  1417. *========================================================================*/
  1418. /*
  1419. * Walk down the Btree looking for a particular filename, filling
  1420. * in the state structure as we go.
  1421. *
  1422. * We will set the state structure to point to each of the elements
  1423. * in each of the nodes where either the hashval is or should be.
  1424. *
  1425. * We support duplicate hashval's so for each entry in the current
  1426. * node that could contain the desired hashval, descend. This is a
  1427. * pruned depth-first tree search.
  1428. */
  1429. int /* error */
  1430. xfs_da3_node_lookup_int(
  1431. struct xfs_da_state *state,
  1432. int *result)
  1433. {
  1434. struct xfs_da_state_blk *blk;
  1435. struct xfs_da_blkinfo *curr;
  1436. struct xfs_da_intnode *node;
  1437. struct xfs_da_node_entry *btree;
  1438. struct xfs_da3_icnode_hdr nodehdr;
  1439. struct xfs_da_args *args;
  1440. xfs_dablk_t blkno;
  1441. xfs_dahash_t hashval;
  1442. xfs_dahash_t btreehashval;
  1443. int probe;
  1444. int span;
  1445. int max;
  1446. int error;
  1447. int retval;
  1448. unsigned int expected_level = 0;
  1449. uint16_t magic;
  1450. struct xfs_inode *dp = state->args->dp;
  1451. args = state->args;
  1452. /*
  1453. * Descend thru the B-tree searching each level for the right
  1454. * node to use, until the right hashval is found.
  1455. */
  1456. blkno = args->geo->leafblk;
  1457. for (blk = &state->path.blk[0], state->path.active = 1;
  1458. state->path.active <= XFS_DA_NODE_MAXDEPTH;
  1459. blk++, state->path.active++) {
  1460. /*
  1461. * Read the next node down in the tree.
  1462. */
  1463. blk->blkno = blkno;
  1464. error = xfs_da3_node_read(args->trans, args->dp, blkno,
  1465. &blk->bp, args->whichfork);
  1466. if (error) {
  1467. blk->blkno = 0;
  1468. state->path.active--;
  1469. return error;
  1470. }
  1471. curr = blk->bp->b_addr;
  1472. magic = be16_to_cpu(curr->magic);
  1473. if (magic == XFS_ATTR_LEAF_MAGIC ||
  1474. magic == XFS_ATTR3_LEAF_MAGIC) {
  1475. blk->magic = XFS_ATTR_LEAF_MAGIC;
  1476. blk->hashval = xfs_attr_leaf_lasthash(blk->bp, NULL);
  1477. break;
  1478. }
  1479. if (magic == XFS_DIR2_LEAFN_MAGIC ||
  1480. magic == XFS_DIR3_LEAFN_MAGIC) {
  1481. blk->magic = XFS_DIR2_LEAFN_MAGIC;
  1482. blk->hashval = xfs_dir2_leaf_lasthash(args->dp,
  1483. blk->bp, NULL);
  1484. break;
  1485. }
  1486. if (magic != XFS_DA_NODE_MAGIC && magic != XFS_DA3_NODE_MAGIC) {
  1487. xfs_buf_mark_corrupt(blk->bp);
  1488. return -EFSCORRUPTED;
  1489. }
  1490. blk->magic = XFS_DA_NODE_MAGIC;
  1491. /*
  1492. * Search an intermediate node for a match.
  1493. */
  1494. node = blk->bp->b_addr;
  1495. xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr, node);
  1496. btree = nodehdr.btree;
  1497. /* Tree taller than we can handle; bail out! */
  1498. if (nodehdr.level >= XFS_DA_NODE_MAXDEPTH) {
  1499. xfs_buf_mark_corrupt(blk->bp);
  1500. return -EFSCORRUPTED;
  1501. }
  1502. /* Check the level from the root. */
  1503. if (blkno == args->geo->leafblk)
  1504. expected_level = nodehdr.level - 1;
  1505. else if (expected_level != nodehdr.level) {
  1506. xfs_buf_mark_corrupt(blk->bp);
  1507. return -EFSCORRUPTED;
  1508. } else
  1509. expected_level--;
  1510. max = nodehdr.count;
  1511. blk->hashval = be32_to_cpu(btree[max - 1].hashval);
  1512. /*
  1513. * Binary search. (note: small blocks will skip loop)
  1514. */
  1515. probe = span = max / 2;
  1516. hashval = args->hashval;
  1517. while (span > 4) {
  1518. span /= 2;
  1519. btreehashval = be32_to_cpu(btree[probe].hashval);
  1520. if (btreehashval < hashval)
  1521. probe += span;
  1522. else if (btreehashval > hashval)
  1523. probe -= span;
  1524. else
  1525. break;
  1526. }
  1527. ASSERT((probe >= 0) && (probe < max));
  1528. ASSERT((span <= 4) ||
  1529. (be32_to_cpu(btree[probe].hashval) == hashval));
  1530. /*
  1531. * Since we may have duplicate hashval's, find the first
  1532. * matching hashval in the node.
  1533. */
  1534. while (probe > 0 &&
  1535. be32_to_cpu(btree[probe].hashval) >= hashval) {
  1536. probe--;
  1537. }
  1538. while (probe < max &&
  1539. be32_to_cpu(btree[probe].hashval) < hashval) {
  1540. probe++;
  1541. }
  1542. /*
  1543. * Pick the right block to descend on.
  1544. */
  1545. if (probe == max) {
  1546. blk->index = max - 1;
  1547. blkno = be32_to_cpu(btree[max - 1].before);
  1548. } else {
  1549. blk->index = probe;
  1550. blkno = be32_to_cpu(btree[probe].before);
  1551. }
  1552. /* We can't point back to the root. */
  1553. if (XFS_IS_CORRUPT(dp->i_mount, blkno == args->geo->leafblk))
  1554. return -EFSCORRUPTED;
  1555. }
  1556. if (XFS_IS_CORRUPT(dp->i_mount, expected_level != 0))
  1557. return -EFSCORRUPTED;
  1558. /*
  1559. * A leaf block that ends in the hashval that we are interested in
  1560. * (final hashval == search hashval) means that the next block may
  1561. * contain more entries with the same hashval, shift upward to the
  1562. * next leaf and keep searching.
  1563. */
  1564. for (;;) {
  1565. if (blk->magic == XFS_DIR2_LEAFN_MAGIC) {
  1566. retval = xfs_dir2_leafn_lookup_int(blk->bp, args,
  1567. &blk->index, state);
  1568. } else if (blk->magic == XFS_ATTR_LEAF_MAGIC) {
  1569. retval = xfs_attr3_leaf_lookup_int(blk->bp, args);
  1570. blk->index = args->index;
  1571. args->blkno = blk->blkno;
  1572. } else {
  1573. ASSERT(0);
  1574. return -EFSCORRUPTED;
  1575. }
  1576. if (((retval == -ENOENT) || (retval == -ENOATTR)) &&
  1577. (blk->hashval == args->hashval)) {
  1578. error = xfs_da3_path_shift(state, &state->path, 1, 1,
  1579. &retval);
  1580. if (error)
  1581. return error;
  1582. if (retval == 0) {
  1583. continue;
  1584. } else if (blk->magic == XFS_ATTR_LEAF_MAGIC) {
  1585. /* path_shift() gives ENOENT */
  1586. retval = -ENOATTR;
  1587. }
  1588. }
  1589. break;
  1590. }
  1591. *result = retval;
  1592. return 0;
  1593. }
  1594. /*========================================================================
  1595. * Utility routines.
  1596. *========================================================================*/
  1597. /*
  1598. * Compare two intermediate nodes for "order".
  1599. */
  1600. STATIC int
  1601. xfs_da3_node_order(
  1602. struct xfs_inode *dp,
  1603. struct xfs_buf *node1_bp,
  1604. struct xfs_buf *node2_bp)
  1605. {
  1606. struct xfs_da_intnode *node1;
  1607. struct xfs_da_intnode *node2;
  1608. struct xfs_da_node_entry *btree1;
  1609. struct xfs_da_node_entry *btree2;
  1610. struct xfs_da3_icnode_hdr node1hdr;
  1611. struct xfs_da3_icnode_hdr node2hdr;
  1612. node1 = node1_bp->b_addr;
  1613. node2 = node2_bp->b_addr;
  1614. xfs_da3_node_hdr_from_disk(dp->i_mount, &node1hdr, node1);
  1615. xfs_da3_node_hdr_from_disk(dp->i_mount, &node2hdr, node2);
  1616. btree1 = node1hdr.btree;
  1617. btree2 = node2hdr.btree;
  1618. if (node1hdr.count > 0 && node2hdr.count > 0 &&
  1619. ((be32_to_cpu(btree2[0].hashval) < be32_to_cpu(btree1[0].hashval)) ||
  1620. (be32_to_cpu(btree2[node2hdr.count - 1].hashval) <
  1621. be32_to_cpu(btree1[node1hdr.count - 1].hashval)))) {
  1622. return 1;
  1623. }
  1624. return 0;
  1625. }
  1626. /*
  1627. * Link a new block into a doubly linked list of blocks (of whatever type).
  1628. */
  1629. int /* error */
  1630. xfs_da3_blk_link(
  1631. struct xfs_da_state *state,
  1632. struct xfs_da_state_blk *old_blk,
  1633. struct xfs_da_state_blk *new_blk)
  1634. {
  1635. struct xfs_da_blkinfo *old_info;
  1636. struct xfs_da_blkinfo *new_info;
  1637. struct xfs_da_blkinfo *tmp_info;
  1638. struct xfs_da_args *args;
  1639. struct xfs_buf *bp;
  1640. int before = 0;
  1641. int error;
  1642. struct xfs_inode *dp = state->args->dp;
  1643. /*
  1644. * Set up environment.
  1645. */
  1646. args = state->args;
  1647. ASSERT(args != NULL);
  1648. old_info = old_blk->bp->b_addr;
  1649. new_info = new_blk->bp->b_addr;
  1650. ASSERT(old_blk->magic == XFS_DA_NODE_MAGIC ||
  1651. old_blk->magic == XFS_DIR2_LEAFN_MAGIC ||
  1652. old_blk->magic == XFS_ATTR_LEAF_MAGIC);
  1653. switch (old_blk->magic) {
  1654. case XFS_ATTR_LEAF_MAGIC:
  1655. before = xfs_attr_leaf_order(old_blk->bp, new_blk->bp);
  1656. break;
  1657. case XFS_DIR2_LEAFN_MAGIC:
  1658. before = xfs_dir2_leafn_order(dp, old_blk->bp, new_blk->bp);
  1659. break;
  1660. case XFS_DA_NODE_MAGIC:
  1661. before = xfs_da3_node_order(dp, old_blk->bp, new_blk->bp);
  1662. break;
  1663. }
  1664. /*
  1665. * Link blocks in appropriate order.
  1666. */
  1667. if (before) {
  1668. /*
  1669. * Link new block in before existing block.
  1670. */
  1671. trace_xfs_da_link_before(args);
  1672. new_info->forw = cpu_to_be32(old_blk->blkno);
  1673. new_info->back = old_info->back;
  1674. if (old_info->back) {
  1675. error = xfs_da3_node_read(args->trans, dp,
  1676. be32_to_cpu(old_info->back),
  1677. &bp, args->whichfork);
  1678. if (error)
  1679. return error;
  1680. ASSERT(bp != NULL);
  1681. tmp_info = bp->b_addr;
  1682. ASSERT(tmp_info->magic == old_info->magic);
  1683. ASSERT(be32_to_cpu(tmp_info->forw) == old_blk->blkno);
  1684. tmp_info->forw = cpu_to_be32(new_blk->blkno);
  1685. xfs_trans_log_buf(args->trans, bp, 0, sizeof(*tmp_info)-1);
  1686. }
  1687. old_info->back = cpu_to_be32(new_blk->blkno);
  1688. } else {
  1689. /*
  1690. * Link new block in after existing block.
  1691. */
  1692. trace_xfs_da_link_after(args);
  1693. new_info->forw = old_info->forw;
  1694. new_info->back = cpu_to_be32(old_blk->blkno);
  1695. if (old_info->forw) {
  1696. error = xfs_da3_node_read(args->trans, dp,
  1697. be32_to_cpu(old_info->forw),
  1698. &bp, args->whichfork);
  1699. if (error)
  1700. return error;
  1701. ASSERT(bp != NULL);
  1702. tmp_info = bp->b_addr;
  1703. ASSERT(tmp_info->magic == old_info->magic);
  1704. ASSERT(be32_to_cpu(tmp_info->back) == old_blk->blkno);
  1705. tmp_info->back = cpu_to_be32(new_blk->blkno);
  1706. xfs_trans_log_buf(args->trans, bp, 0, sizeof(*tmp_info)-1);
  1707. }
  1708. old_info->forw = cpu_to_be32(new_blk->blkno);
  1709. }
  1710. xfs_trans_log_buf(args->trans, old_blk->bp, 0, sizeof(*tmp_info) - 1);
  1711. xfs_trans_log_buf(args->trans, new_blk->bp, 0, sizeof(*tmp_info) - 1);
  1712. return 0;
  1713. }
  1714. /*
  1715. * Unlink a block from a doubly linked list of blocks.
  1716. */
  1717. STATIC int /* error */
  1718. xfs_da3_blk_unlink(
  1719. struct xfs_da_state *state,
  1720. struct xfs_da_state_blk *drop_blk,
  1721. struct xfs_da_state_blk *save_blk)
  1722. {
  1723. struct xfs_da_blkinfo *drop_info;
  1724. struct xfs_da_blkinfo *save_info;
  1725. struct xfs_da_blkinfo *tmp_info;
  1726. struct xfs_da_args *args;
  1727. struct xfs_buf *bp;
  1728. int error;
  1729. /*
  1730. * Set up environment.
  1731. */
  1732. args = state->args;
  1733. ASSERT(args != NULL);
  1734. save_info = save_blk->bp->b_addr;
  1735. drop_info = drop_blk->bp->b_addr;
  1736. ASSERT(save_blk->magic == XFS_DA_NODE_MAGIC ||
  1737. save_blk->magic == XFS_DIR2_LEAFN_MAGIC ||
  1738. save_blk->magic == XFS_ATTR_LEAF_MAGIC);
  1739. ASSERT(save_blk->magic == drop_blk->magic);
  1740. ASSERT((be32_to_cpu(save_info->forw) == drop_blk->blkno) ||
  1741. (be32_to_cpu(save_info->back) == drop_blk->blkno));
  1742. ASSERT((be32_to_cpu(drop_info->forw) == save_blk->blkno) ||
  1743. (be32_to_cpu(drop_info->back) == save_blk->blkno));
  1744. /*
  1745. * Unlink the leaf block from the doubly linked chain of leaves.
  1746. */
  1747. if (be32_to_cpu(save_info->back) == drop_blk->blkno) {
  1748. trace_xfs_da_unlink_back(args);
  1749. save_info->back = drop_info->back;
  1750. if (drop_info->back) {
  1751. error = xfs_da3_node_read(args->trans, args->dp,
  1752. be32_to_cpu(drop_info->back),
  1753. &bp, args->whichfork);
  1754. if (error)
  1755. return error;
  1756. ASSERT(bp != NULL);
  1757. tmp_info = bp->b_addr;
  1758. ASSERT(tmp_info->magic == save_info->magic);
  1759. ASSERT(be32_to_cpu(tmp_info->forw) == drop_blk->blkno);
  1760. tmp_info->forw = cpu_to_be32(save_blk->blkno);
  1761. xfs_trans_log_buf(args->trans, bp, 0,
  1762. sizeof(*tmp_info) - 1);
  1763. }
  1764. } else {
  1765. trace_xfs_da_unlink_forward(args);
  1766. save_info->forw = drop_info->forw;
  1767. if (drop_info->forw) {
  1768. error = xfs_da3_node_read(args->trans, args->dp,
  1769. be32_to_cpu(drop_info->forw),
  1770. &bp, args->whichfork);
  1771. if (error)
  1772. return error;
  1773. ASSERT(bp != NULL);
  1774. tmp_info = bp->b_addr;
  1775. ASSERT(tmp_info->magic == save_info->magic);
  1776. ASSERT(be32_to_cpu(tmp_info->back) == drop_blk->blkno);
  1777. tmp_info->back = cpu_to_be32(save_blk->blkno);
  1778. xfs_trans_log_buf(args->trans, bp, 0,
  1779. sizeof(*tmp_info) - 1);
  1780. }
  1781. }
  1782. xfs_trans_log_buf(args->trans, save_blk->bp, 0, sizeof(*save_info) - 1);
  1783. return 0;
  1784. }
  1785. /*
  1786. * Move a path "forward" or "!forward" one block at the current level.
  1787. *
  1788. * This routine will adjust a "path" to point to the next block
  1789. * "forward" (higher hashvalues) or "!forward" (lower hashvals) in the
  1790. * Btree, including updating pointers to the intermediate nodes between
  1791. * the new bottom and the root.
  1792. */
  1793. int /* error */
  1794. xfs_da3_path_shift(
  1795. struct xfs_da_state *state,
  1796. struct xfs_da_state_path *path,
  1797. int forward,
  1798. int release,
  1799. int *result)
  1800. {
  1801. struct xfs_da_state_blk *blk;
  1802. struct xfs_da_blkinfo *info;
  1803. struct xfs_da_args *args;
  1804. struct xfs_da_node_entry *btree;
  1805. struct xfs_da3_icnode_hdr nodehdr;
  1806. struct xfs_buf *bp;
  1807. xfs_dablk_t blkno = 0;
  1808. int level;
  1809. int error;
  1810. struct xfs_inode *dp = state->args->dp;
  1811. trace_xfs_da_path_shift(state->args);
  1812. /*
  1813. * Roll up the Btree looking for the first block where our
  1814. * current index is not at the edge of the block. Note that
  1815. * we skip the bottom layer because we want the sibling block.
  1816. */
  1817. args = state->args;
  1818. ASSERT(args != NULL);
  1819. ASSERT(path != NULL);
  1820. ASSERT((path->active > 0) && (path->active < XFS_DA_NODE_MAXDEPTH));
  1821. level = (path->active-1) - 1; /* skip bottom layer in path */
  1822. for (; level >= 0; level--) {
  1823. blk = &path->blk[level];
  1824. xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr,
  1825. blk->bp->b_addr);
  1826. if (forward && (blk->index < nodehdr.count - 1)) {
  1827. blk->index++;
  1828. blkno = be32_to_cpu(nodehdr.btree[blk->index].before);
  1829. break;
  1830. } else if (!forward && (blk->index > 0)) {
  1831. blk->index--;
  1832. blkno = be32_to_cpu(nodehdr.btree[blk->index].before);
  1833. break;
  1834. }
  1835. }
  1836. if (level < 0) {
  1837. *result = -ENOENT; /* we're out of our tree */
  1838. ASSERT(args->op_flags & XFS_DA_OP_OKNOENT);
  1839. return 0;
  1840. }
  1841. /*
  1842. * Roll down the edge of the subtree until we reach the
  1843. * same depth we were at originally.
  1844. */
  1845. for (blk++, level++; level < path->active; blk++, level++) {
  1846. /*
  1847. * Read the next child block into a local buffer.
  1848. */
  1849. error = xfs_da3_node_read(args->trans, dp, blkno, &bp,
  1850. args->whichfork);
  1851. if (error)
  1852. return error;
  1853. /*
  1854. * Release the old block (if it's dirty, the trans doesn't
  1855. * actually let go) and swap the local buffer into the path
  1856. * structure. This ensures failure of the above read doesn't set
  1857. * a NULL buffer in an active slot in the path.
  1858. */
  1859. if (release)
  1860. xfs_trans_brelse(args->trans, blk->bp);
  1861. blk->blkno = blkno;
  1862. blk->bp = bp;
  1863. info = blk->bp->b_addr;
  1864. ASSERT(info->magic == cpu_to_be16(XFS_DA_NODE_MAGIC) ||
  1865. info->magic == cpu_to_be16(XFS_DA3_NODE_MAGIC) ||
  1866. info->magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) ||
  1867. info->magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC) ||
  1868. info->magic == cpu_to_be16(XFS_ATTR_LEAF_MAGIC) ||
  1869. info->magic == cpu_to_be16(XFS_ATTR3_LEAF_MAGIC));
  1870. /*
  1871. * Note: we flatten the magic number to a single type so we
  1872. * don't have to compare against crc/non-crc types elsewhere.
  1873. */
  1874. switch (be16_to_cpu(info->magic)) {
  1875. case XFS_DA_NODE_MAGIC:
  1876. case XFS_DA3_NODE_MAGIC:
  1877. blk->magic = XFS_DA_NODE_MAGIC;
  1878. xfs_da3_node_hdr_from_disk(dp->i_mount, &nodehdr,
  1879. bp->b_addr);
  1880. btree = nodehdr.btree;
  1881. blk->hashval = be32_to_cpu(btree[nodehdr.count - 1].hashval);
  1882. if (forward)
  1883. blk->index = 0;
  1884. else
  1885. blk->index = nodehdr.count - 1;
  1886. blkno = be32_to_cpu(btree[blk->index].before);
  1887. break;
  1888. case XFS_ATTR_LEAF_MAGIC:
  1889. case XFS_ATTR3_LEAF_MAGIC:
  1890. blk->magic = XFS_ATTR_LEAF_MAGIC;
  1891. ASSERT(level == path->active-1);
  1892. blk->index = 0;
  1893. blk->hashval = xfs_attr_leaf_lasthash(blk->bp, NULL);
  1894. break;
  1895. case XFS_DIR2_LEAFN_MAGIC:
  1896. case XFS_DIR3_LEAFN_MAGIC:
  1897. blk->magic = XFS_DIR2_LEAFN_MAGIC;
  1898. ASSERT(level == path->active-1);
  1899. blk->index = 0;
  1900. blk->hashval = xfs_dir2_leaf_lasthash(args->dp,
  1901. blk->bp, NULL);
  1902. break;
  1903. default:
  1904. ASSERT(0);
  1905. break;
  1906. }
  1907. }
  1908. *result = 0;
  1909. return 0;
  1910. }
  1911. /*========================================================================
  1912. * Utility routines.
  1913. *========================================================================*/
  1914. /*
  1915. * Implement a simple hash on a character string.
  1916. * Rotate the hash value by 7 bits, then XOR each character in.
  1917. * This is implemented with some source-level loop unrolling.
  1918. */
  1919. xfs_dahash_t
  1920. xfs_da_hashname(const uint8_t *name, int namelen)
  1921. {
  1922. xfs_dahash_t hash;
  1923. /*
  1924. * Do four characters at a time as long as we can.
  1925. */
  1926. for (hash = 0; namelen >= 4; namelen -= 4, name += 4)
  1927. hash = (name[0] << 21) ^ (name[1] << 14) ^ (name[2] << 7) ^
  1928. (name[3] << 0) ^ rol32(hash, 7 * 4);
  1929. /*
  1930. * Now do the rest of the characters.
  1931. */
  1932. switch (namelen) {
  1933. case 3:
  1934. return (name[0] << 14) ^ (name[1] << 7) ^ (name[2] << 0) ^
  1935. rol32(hash, 7 * 3);
  1936. case 2:
  1937. return (name[0] << 7) ^ (name[1] << 0) ^ rol32(hash, 7 * 2);
  1938. case 1:
  1939. return (name[0] << 0) ^ rol32(hash, 7 * 1);
  1940. default: /* case 0: */
  1941. return hash;
  1942. }
  1943. }
  1944. enum xfs_dacmp
  1945. xfs_da_compname(
  1946. struct xfs_da_args *args,
  1947. const unsigned char *name,
  1948. int len)
  1949. {
  1950. return (args->namelen == len && memcmp(args->name, name, len) == 0) ?
  1951. XFS_CMP_EXACT : XFS_CMP_DIFFERENT;
  1952. }
  1953. int
  1954. xfs_da_grow_inode_int(
  1955. struct xfs_da_args *args,
  1956. xfs_fileoff_t *bno,
  1957. int count)
  1958. {
  1959. struct xfs_trans *tp = args->trans;
  1960. struct xfs_inode *dp = args->dp;
  1961. int w = args->whichfork;
  1962. xfs_rfsblock_t nblks = dp->i_nblocks;
  1963. struct xfs_bmbt_irec map, *mapp;
  1964. int nmap, error, got, i, mapi;
  1965. /*
  1966. * Find a spot in the file space to put the new block.
  1967. */
  1968. error = xfs_bmap_first_unused(tp, dp, count, bno, w);
  1969. if (error)
  1970. return error;
  1971. /*
  1972. * Try mapping it in one filesystem block.
  1973. */
  1974. nmap = 1;
  1975. error = xfs_bmapi_write(tp, dp, *bno, count,
  1976. xfs_bmapi_aflag(w)|XFS_BMAPI_METADATA|XFS_BMAPI_CONTIG,
  1977. args->total, &map, &nmap);
  1978. if (error)
  1979. return error;
  1980. ASSERT(nmap <= 1);
  1981. if (nmap == 1) {
  1982. mapp = &map;
  1983. mapi = 1;
  1984. } else if (nmap == 0 && count > 1) {
  1985. xfs_fileoff_t b;
  1986. int c;
  1987. /*
  1988. * If we didn't get it and the block might work if fragmented,
  1989. * try without the CONTIG flag. Loop until we get it all.
  1990. */
  1991. mapp = kmem_alloc(sizeof(*mapp) * count, 0);
  1992. for (b = *bno, mapi = 0; b < *bno + count; ) {
  1993. c = (int)(*bno + count - b);
  1994. nmap = min(XFS_BMAP_MAX_NMAP, c);
  1995. error = xfs_bmapi_write(tp, dp, b, c,
  1996. xfs_bmapi_aflag(w)|XFS_BMAPI_METADATA,
  1997. args->total, &mapp[mapi], &nmap);
  1998. if (error)
  1999. goto out_free_map;
  2000. if (nmap < 1)
  2001. break;
  2002. mapi += nmap;
  2003. b = mapp[mapi - 1].br_startoff +
  2004. mapp[mapi - 1].br_blockcount;
  2005. }
  2006. } else {
  2007. mapi = 0;
  2008. mapp = NULL;
  2009. }
  2010. /*
  2011. * Count the blocks we got, make sure it matches the total.
  2012. */
  2013. for (i = 0, got = 0; i < mapi; i++)
  2014. got += mapp[i].br_blockcount;
  2015. if (got != count || mapp[0].br_startoff != *bno ||
  2016. mapp[mapi - 1].br_startoff + mapp[mapi - 1].br_blockcount !=
  2017. *bno + count) {
  2018. error = -ENOSPC;
  2019. goto out_free_map;
  2020. }
  2021. /* account for newly allocated blocks in reserved blocks total */
  2022. args->total -= dp->i_nblocks - nblks;
  2023. out_free_map:
  2024. if (mapp != &map)
  2025. kmem_free(mapp);
  2026. return error;
  2027. }
  2028. /*
  2029. * Add a block to the btree ahead of the file.
  2030. * Return the new block number to the caller.
  2031. */
  2032. int
  2033. xfs_da_grow_inode(
  2034. struct xfs_da_args *args,
  2035. xfs_dablk_t *new_blkno)
  2036. {
  2037. xfs_fileoff_t bno;
  2038. int error;
  2039. trace_xfs_da_grow_inode(args);
  2040. bno = args->geo->leafblk;
  2041. error = xfs_da_grow_inode_int(args, &bno, args->geo->fsbcount);
  2042. if (!error)
  2043. *new_blkno = (xfs_dablk_t)bno;
  2044. return error;
  2045. }
  2046. /*
  2047. * Ick. We need to always be able to remove a btree block, even
  2048. * if there's no space reservation because the filesystem is full.
  2049. * This is called if xfs_bunmapi on a btree block fails due to ENOSPC.
  2050. * It swaps the target block with the last block in the file. The
  2051. * last block in the file can always be removed since it can't cause
  2052. * a bmap btree split to do that.
  2053. */
  2054. STATIC int
  2055. xfs_da3_swap_lastblock(
  2056. struct xfs_da_args *args,
  2057. xfs_dablk_t *dead_blknop,
  2058. struct xfs_buf **dead_bufp)
  2059. {
  2060. struct xfs_da_blkinfo *dead_info;
  2061. struct xfs_da_blkinfo *sib_info;
  2062. struct xfs_da_intnode *par_node;
  2063. struct xfs_da_intnode *dead_node;
  2064. struct xfs_dir2_leaf *dead_leaf2;
  2065. struct xfs_da_node_entry *btree;
  2066. struct xfs_da3_icnode_hdr par_hdr;
  2067. struct xfs_inode *dp;
  2068. struct xfs_trans *tp;
  2069. struct xfs_mount *mp;
  2070. struct xfs_buf *dead_buf;
  2071. struct xfs_buf *last_buf;
  2072. struct xfs_buf *sib_buf;
  2073. struct xfs_buf *par_buf;
  2074. xfs_dahash_t dead_hash;
  2075. xfs_fileoff_t lastoff;
  2076. xfs_dablk_t dead_blkno;
  2077. xfs_dablk_t last_blkno;
  2078. xfs_dablk_t sib_blkno;
  2079. xfs_dablk_t par_blkno;
  2080. int error;
  2081. int w;
  2082. int entno;
  2083. int level;
  2084. int dead_level;
  2085. trace_xfs_da_swap_lastblock(args);
  2086. dead_buf = *dead_bufp;
  2087. dead_blkno = *dead_blknop;
  2088. tp = args->trans;
  2089. dp = args->dp;
  2090. w = args->whichfork;
  2091. ASSERT(w == XFS_DATA_FORK);
  2092. mp = dp->i_mount;
  2093. lastoff = args->geo->freeblk;
  2094. error = xfs_bmap_last_before(tp, dp, &lastoff, w);
  2095. if (error)
  2096. return error;
  2097. if (XFS_IS_CORRUPT(mp, lastoff == 0))
  2098. return -EFSCORRUPTED;
  2099. /*
  2100. * Read the last block in the btree space.
  2101. */
  2102. last_blkno = (xfs_dablk_t)lastoff - args->geo->fsbcount;
  2103. error = xfs_da3_node_read(tp, dp, last_blkno, &last_buf, w);
  2104. if (error)
  2105. return error;
  2106. /*
  2107. * Copy the last block into the dead buffer and log it.
  2108. */
  2109. memcpy(dead_buf->b_addr, last_buf->b_addr, args->geo->blksize);
  2110. xfs_trans_log_buf(tp, dead_buf, 0, args->geo->blksize - 1);
  2111. dead_info = dead_buf->b_addr;
  2112. /*
  2113. * Get values from the moved block.
  2114. */
  2115. if (dead_info->magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) ||
  2116. dead_info->magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC)) {
  2117. struct xfs_dir3_icleaf_hdr leafhdr;
  2118. struct xfs_dir2_leaf_entry *ents;
  2119. dead_leaf2 = (xfs_dir2_leaf_t *)dead_info;
  2120. xfs_dir2_leaf_hdr_from_disk(dp->i_mount, &leafhdr,
  2121. dead_leaf2);
  2122. ents = leafhdr.ents;
  2123. dead_level = 0;
  2124. dead_hash = be32_to_cpu(ents[leafhdr.count - 1].hashval);
  2125. } else {
  2126. struct xfs_da3_icnode_hdr deadhdr;
  2127. dead_node = (xfs_da_intnode_t *)dead_info;
  2128. xfs_da3_node_hdr_from_disk(dp->i_mount, &deadhdr, dead_node);
  2129. btree = deadhdr.btree;
  2130. dead_level = deadhdr.level;
  2131. dead_hash = be32_to_cpu(btree[deadhdr.count - 1].hashval);
  2132. }
  2133. sib_buf = par_buf = NULL;
  2134. /*
  2135. * If the moved block has a left sibling, fix up the pointers.
  2136. */
  2137. if ((sib_blkno = be32_to_cpu(dead_info->back))) {
  2138. error = xfs_da3_node_read(tp, dp, sib_blkno, &sib_buf, w);
  2139. if (error)
  2140. goto done;
  2141. sib_info = sib_buf->b_addr;
  2142. if (XFS_IS_CORRUPT(mp,
  2143. be32_to_cpu(sib_info->forw) != last_blkno ||
  2144. sib_info->magic != dead_info->magic)) {
  2145. error = -EFSCORRUPTED;
  2146. goto done;
  2147. }
  2148. sib_info->forw = cpu_to_be32(dead_blkno);
  2149. xfs_trans_log_buf(tp, sib_buf,
  2150. XFS_DA_LOGRANGE(sib_info, &sib_info->forw,
  2151. sizeof(sib_info->forw)));
  2152. sib_buf = NULL;
  2153. }
  2154. /*
  2155. * If the moved block has a right sibling, fix up the pointers.
  2156. */
  2157. if ((sib_blkno = be32_to_cpu(dead_info->forw))) {
  2158. error = xfs_da3_node_read(tp, dp, sib_blkno, &sib_buf, w);
  2159. if (error)
  2160. goto done;
  2161. sib_info = sib_buf->b_addr;
  2162. if (XFS_IS_CORRUPT(mp,
  2163. be32_to_cpu(sib_info->back) != last_blkno ||
  2164. sib_info->magic != dead_info->magic)) {
  2165. error = -EFSCORRUPTED;
  2166. goto done;
  2167. }
  2168. sib_info->back = cpu_to_be32(dead_blkno);
  2169. xfs_trans_log_buf(tp, sib_buf,
  2170. XFS_DA_LOGRANGE(sib_info, &sib_info->back,
  2171. sizeof(sib_info->back)));
  2172. sib_buf = NULL;
  2173. }
  2174. par_blkno = args->geo->leafblk;
  2175. level = -1;
  2176. /*
  2177. * Walk down the tree looking for the parent of the moved block.
  2178. */
  2179. for (;;) {
  2180. error = xfs_da3_node_read(tp, dp, par_blkno, &par_buf, w);
  2181. if (error)
  2182. goto done;
  2183. par_node = par_buf->b_addr;
  2184. xfs_da3_node_hdr_from_disk(dp->i_mount, &par_hdr, par_node);
  2185. if (XFS_IS_CORRUPT(mp,
  2186. level >= 0 && level != par_hdr.level + 1)) {
  2187. error = -EFSCORRUPTED;
  2188. goto done;
  2189. }
  2190. level = par_hdr.level;
  2191. btree = par_hdr.btree;
  2192. for (entno = 0;
  2193. entno < par_hdr.count &&
  2194. be32_to_cpu(btree[entno].hashval) < dead_hash;
  2195. entno++)
  2196. continue;
  2197. if (XFS_IS_CORRUPT(mp, entno == par_hdr.count)) {
  2198. error = -EFSCORRUPTED;
  2199. goto done;
  2200. }
  2201. par_blkno = be32_to_cpu(btree[entno].before);
  2202. if (level == dead_level + 1)
  2203. break;
  2204. xfs_trans_brelse(tp, par_buf);
  2205. par_buf = NULL;
  2206. }
  2207. /*
  2208. * We're in the right parent block.
  2209. * Look for the right entry.
  2210. */
  2211. for (;;) {
  2212. for (;
  2213. entno < par_hdr.count &&
  2214. be32_to_cpu(btree[entno].before) != last_blkno;
  2215. entno++)
  2216. continue;
  2217. if (entno < par_hdr.count)
  2218. break;
  2219. par_blkno = par_hdr.forw;
  2220. xfs_trans_brelse(tp, par_buf);
  2221. par_buf = NULL;
  2222. if (XFS_IS_CORRUPT(mp, par_blkno == 0)) {
  2223. error = -EFSCORRUPTED;
  2224. goto done;
  2225. }
  2226. error = xfs_da3_node_read(tp, dp, par_blkno, &par_buf, w);
  2227. if (error)
  2228. goto done;
  2229. par_node = par_buf->b_addr;
  2230. xfs_da3_node_hdr_from_disk(dp->i_mount, &par_hdr, par_node);
  2231. if (XFS_IS_CORRUPT(mp, par_hdr.level != level)) {
  2232. error = -EFSCORRUPTED;
  2233. goto done;
  2234. }
  2235. btree = par_hdr.btree;
  2236. entno = 0;
  2237. }
  2238. /*
  2239. * Update the parent entry pointing to the moved block.
  2240. */
  2241. btree[entno].before = cpu_to_be32(dead_blkno);
  2242. xfs_trans_log_buf(tp, par_buf,
  2243. XFS_DA_LOGRANGE(par_node, &btree[entno].before,
  2244. sizeof(btree[entno].before)));
  2245. *dead_blknop = last_blkno;
  2246. *dead_bufp = last_buf;
  2247. return 0;
  2248. done:
  2249. if (par_buf)
  2250. xfs_trans_brelse(tp, par_buf);
  2251. if (sib_buf)
  2252. xfs_trans_brelse(tp, sib_buf);
  2253. xfs_trans_brelse(tp, last_buf);
  2254. return error;
  2255. }
  2256. /*
  2257. * Remove a btree block from a directory or attribute.
  2258. */
  2259. int
  2260. xfs_da_shrink_inode(
  2261. struct xfs_da_args *args,
  2262. xfs_dablk_t dead_blkno,
  2263. struct xfs_buf *dead_buf)
  2264. {
  2265. struct xfs_inode *dp;
  2266. int done, error, w, count;
  2267. struct xfs_trans *tp;
  2268. trace_xfs_da_shrink_inode(args);
  2269. dp = args->dp;
  2270. w = args->whichfork;
  2271. tp = args->trans;
  2272. count = args->geo->fsbcount;
  2273. for (;;) {
  2274. /*
  2275. * Remove extents. If we get ENOSPC for a dir we have to move
  2276. * the last block to the place we want to kill.
  2277. */
  2278. error = xfs_bunmapi(tp, dp, dead_blkno, count,
  2279. xfs_bmapi_aflag(w), 0, &done);
  2280. if (error == -ENOSPC) {
  2281. if (w != XFS_DATA_FORK)
  2282. break;
  2283. error = xfs_da3_swap_lastblock(args, &dead_blkno,
  2284. &dead_buf);
  2285. if (error)
  2286. break;
  2287. } else {
  2288. break;
  2289. }
  2290. }
  2291. xfs_trans_binval(tp, dead_buf);
  2292. return error;
  2293. }
  2294. static int
  2295. xfs_dabuf_map(
  2296. struct xfs_inode *dp,
  2297. xfs_dablk_t bno,
  2298. unsigned int flags,
  2299. int whichfork,
  2300. struct xfs_buf_map **mapp,
  2301. int *nmaps)
  2302. {
  2303. struct xfs_mount *mp = dp->i_mount;
  2304. int nfsb = xfs_dabuf_nfsb(mp, whichfork);
  2305. struct xfs_bmbt_irec irec, *irecs = &irec;
  2306. struct xfs_buf_map *map = *mapp;
  2307. xfs_fileoff_t off = bno;
  2308. int error = 0, nirecs, i;
  2309. if (nfsb > 1)
  2310. irecs = kmem_zalloc(sizeof(irec) * nfsb, KM_NOFS);
  2311. nirecs = nfsb;
  2312. error = xfs_bmapi_read(dp, bno, nfsb, irecs, &nirecs,
  2313. xfs_bmapi_aflag(whichfork));
  2314. if (error)
  2315. goto out_free_irecs;
  2316. /*
  2317. * Use the caller provided map for the single map case, else allocate a
  2318. * larger one that needs to be free by the caller.
  2319. */
  2320. if (nirecs > 1) {
  2321. map = kmem_zalloc(nirecs * sizeof(struct xfs_buf_map), KM_NOFS);
  2322. if (!map) {
  2323. error = -ENOMEM;
  2324. goto out_free_irecs;
  2325. }
  2326. *mapp = map;
  2327. }
  2328. for (i = 0; i < nirecs; i++) {
  2329. if (irecs[i].br_startblock == HOLESTARTBLOCK ||
  2330. irecs[i].br_startblock == DELAYSTARTBLOCK)
  2331. goto invalid_mapping;
  2332. if (off != irecs[i].br_startoff)
  2333. goto invalid_mapping;
  2334. map[i].bm_bn = XFS_FSB_TO_DADDR(mp, irecs[i].br_startblock);
  2335. map[i].bm_len = XFS_FSB_TO_BB(mp, irecs[i].br_blockcount);
  2336. off += irecs[i].br_blockcount;
  2337. }
  2338. if (off != bno + nfsb)
  2339. goto invalid_mapping;
  2340. *nmaps = nirecs;
  2341. out_free_irecs:
  2342. if (irecs != &irec)
  2343. kmem_free(irecs);
  2344. return error;
  2345. invalid_mapping:
  2346. /* Caller ok with no mapping. */
  2347. if (XFS_IS_CORRUPT(mp, !(flags & XFS_DABUF_MAP_HOLE_OK))) {
  2348. error = -EFSCORRUPTED;
  2349. if (xfs_error_level >= XFS_ERRLEVEL_LOW) {
  2350. xfs_alert(mp, "%s: bno %u inode %llu",
  2351. __func__, bno, dp->i_ino);
  2352. for (i = 0; i < nirecs; i++) {
  2353. xfs_alert(mp,
  2354. "[%02d] br_startoff %lld br_startblock %lld br_blockcount %lld br_state %d",
  2355. i, irecs[i].br_startoff,
  2356. irecs[i].br_startblock,
  2357. irecs[i].br_blockcount,
  2358. irecs[i].br_state);
  2359. }
  2360. }
  2361. } else {
  2362. *nmaps = 0;
  2363. }
  2364. goto out_free_irecs;
  2365. }
  2366. /*
  2367. * Get a buffer for the dir/attr block.
  2368. */
  2369. int
  2370. xfs_da_get_buf(
  2371. struct xfs_trans *tp,
  2372. struct xfs_inode *dp,
  2373. xfs_dablk_t bno,
  2374. struct xfs_buf **bpp,
  2375. int whichfork)
  2376. {
  2377. struct xfs_mount *mp = dp->i_mount;
  2378. struct xfs_buf *bp;
  2379. struct xfs_buf_map map, *mapp = &map;
  2380. int nmap = 1;
  2381. int error;
  2382. *bpp = NULL;
  2383. error = xfs_dabuf_map(dp, bno, 0, whichfork, &mapp, &nmap);
  2384. if (error || nmap == 0)
  2385. goto out_free;
  2386. error = xfs_trans_get_buf_map(tp, mp->m_ddev_targp, mapp, nmap, 0, &bp);
  2387. if (error)
  2388. goto out_free;
  2389. *bpp = bp;
  2390. out_free:
  2391. if (mapp != &map)
  2392. kmem_free(mapp);
  2393. return error;
  2394. }
  2395. /*
  2396. * Get a buffer for the dir/attr block, fill in the contents.
  2397. */
  2398. int
  2399. xfs_da_read_buf(
  2400. struct xfs_trans *tp,
  2401. struct xfs_inode *dp,
  2402. xfs_dablk_t bno,
  2403. unsigned int flags,
  2404. struct xfs_buf **bpp,
  2405. int whichfork,
  2406. const struct xfs_buf_ops *ops)
  2407. {
  2408. struct xfs_mount *mp = dp->i_mount;
  2409. struct xfs_buf *bp;
  2410. struct xfs_buf_map map, *mapp = &map;
  2411. int nmap = 1;
  2412. int error;
  2413. *bpp = NULL;
  2414. error = xfs_dabuf_map(dp, bno, flags, whichfork, &mapp, &nmap);
  2415. if (error || !nmap)
  2416. goto out_free;
  2417. error = xfs_trans_read_buf_map(mp, tp, mp->m_ddev_targp, mapp, nmap, 0,
  2418. &bp, ops);
  2419. if (error)
  2420. goto out_free;
  2421. if (whichfork == XFS_ATTR_FORK)
  2422. xfs_buf_set_ref(bp, XFS_ATTR_BTREE_REF);
  2423. else
  2424. xfs_buf_set_ref(bp, XFS_DIR_BTREE_REF);
  2425. *bpp = bp;
  2426. out_free:
  2427. if (mapp != &map)
  2428. kmem_free(mapp);
  2429. return error;
  2430. }
  2431. /*
  2432. * Readahead the dir/attr block.
  2433. */
  2434. int
  2435. xfs_da_reada_buf(
  2436. struct xfs_inode *dp,
  2437. xfs_dablk_t bno,
  2438. unsigned int flags,
  2439. int whichfork,
  2440. const struct xfs_buf_ops *ops)
  2441. {
  2442. struct xfs_buf_map map;
  2443. struct xfs_buf_map *mapp;
  2444. int nmap;
  2445. int error;
  2446. mapp = &map;
  2447. nmap = 1;
  2448. error = xfs_dabuf_map(dp, bno, flags, whichfork, &mapp, &nmap);
  2449. if (error || !nmap)
  2450. goto out_free;
  2451. xfs_buf_readahead_map(dp->i_mount->m_ddev_targp, mapp, nmap, ops);
  2452. out_free:
  2453. if (mapp != &map)
  2454. kmem_free(mapp);
  2455. return error;
  2456. }