xfs_dir2_node.c 57 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768176917701771177217731774177517761777177817791780178117821783178417851786178717881789179017911792179317941795179617971798179918001801180218031804180518061807180818091810181118121813181418151816181718181819182018211822182318241825182618271828182918301831183218331834183518361837183818391840184118421843184418451846184718481849185018511852185318541855185618571858185918601861186218631864186518661867186818691870187118721873187418751876187718781879188018811882188318841885188618871888188918901891189218931894189518961897189818991900190119021903190419051906190719081909191019111912191319141915191619171918191919201921192219231924192519261927192819291930193119321933193419351936193719381939194019411942194319441945194619471948194919501951195219531954195519561957195819591960196119621963196419651966196719681969197019711972197319741975197619771978197919801981198219831984198519861987198819891990199119921993199419951996199719981999
  1. /*
  2. * Copyright (c) 2000-2005 Silicon Graphics, Inc.
  3. * All Rights Reserved.
  4. *
  5. * This program is free software; you can redistribute it and/or
  6. * modify it under the terms of the GNU General Public License as
  7. * published by the Free Software Foundation.
  8. *
  9. * This program is distributed in the hope that it would be useful,
  10. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  12. * GNU General Public License for more details.
  13. *
  14. * You should have received a copy of the GNU General Public License
  15. * along with this program; if not, write the Free Software Foundation,
  16. * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
  17. */
  18. #include "xfs.h"
  19. #include "xfs_fs.h"
  20. #include "xfs_types.h"
  21. #include "xfs_log.h"
  22. #include "xfs_inum.h"
  23. #include "xfs_trans.h"
  24. #include "xfs_sb.h"
  25. #include "xfs_dir2.h"
  26. #include "xfs_dmapi.h"
  27. #include "xfs_mount.h"
  28. #include "xfs_da_btree.h"
  29. #include "xfs_bmap_btree.h"
  30. #include "xfs_dir2_sf.h"
  31. #include "xfs_attr_sf.h"
  32. #include "xfs_dinode.h"
  33. #include "xfs_inode.h"
  34. #include "xfs_bmap.h"
  35. #include "xfs_dir2_data.h"
  36. #include "xfs_dir2_leaf.h"
  37. #include "xfs_dir2_block.h"
  38. #include "xfs_dir2_node.h"
  39. #include "xfs_dir2_trace.h"
  40. #include "xfs_error.h"
  41. /*
  42. * Function declarations.
  43. */
  44. static void xfs_dir2_free_log_header(xfs_trans_t *tp, xfs_dabuf_t *bp);
  45. static int xfs_dir2_leafn_add(xfs_dabuf_t *bp, xfs_da_args_t *args, int index);
  46. #ifdef DEBUG
  47. static void xfs_dir2_leafn_check(xfs_inode_t *dp, xfs_dabuf_t *bp);
  48. #else
  49. #define xfs_dir2_leafn_check(dp, bp)
  50. #endif
  51. static void xfs_dir2_leafn_moveents(xfs_da_args_t *args, xfs_dabuf_t *bp_s,
  52. int start_s, xfs_dabuf_t *bp_d, int start_d,
  53. int count);
  54. static void xfs_dir2_leafn_rebalance(xfs_da_state_t *state,
  55. xfs_da_state_blk_t *blk1,
  56. xfs_da_state_blk_t *blk2);
  57. static int xfs_dir2_leafn_remove(xfs_da_args_t *args, xfs_dabuf_t *bp,
  58. int index, xfs_da_state_blk_t *dblk,
  59. int *rval);
  60. static int xfs_dir2_node_addname_int(xfs_da_args_t *args,
  61. xfs_da_state_blk_t *fblk);
  62. /*
  63. * Log entries from a freespace block.
  64. */
  65. void
  66. xfs_dir2_free_log_bests(
  67. xfs_trans_t *tp, /* transaction pointer */
  68. xfs_dabuf_t *bp, /* freespace buffer */
  69. int first, /* first entry to log */
  70. int last) /* last entry to log */
  71. {
  72. xfs_dir2_free_t *free; /* freespace structure */
  73. free = bp->data;
  74. ASSERT(be32_to_cpu(free->hdr.magic) == XFS_DIR2_FREE_MAGIC);
  75. xfs_da_log_buf(tp, bp,
  76. (uint)((char *)&free->bests[first] - (char *)free),
  77. (uint)((char *)&free->bests[last] - (char *)free +
  78. sizeof(free->bests[0]) - 1));
  79. }
  80. /*
  81. * Log header from a freespace block.
  82. */
  83. static void
  84. xfs_dir2_free_log_header(
  85. xfs_trans_t *tp, /* transaction pointer */
  86. xfs_dabuf_t *bp) /* freespace buffer */
  87. {
  88. xfs_dir2_free_t *free; /* freespace structure */
  89. free = bp->data;
  90. ASSERT(be32_to_cpu(free->hdr.magic) == XFS_DIR2_FREE_MAGIC);
  91. xfs_da_log_buf(tp, bp, (uint)((char *)&free->hdr - (char *)free),
  92. (uint)(sizeof(xfs_dir2_free_hdr_t) - 1));
  93. }
  94. /*
  95. * Convert a leaf-format directory to a node-format directory.
  96. * We need to change the magic number of the leaf block, and copy
  97. * the freespace table out of the leaf block into its own block.
  98. */
  99. int /* error */
  100. xfs_dir2_leaf_to_node(
  101. xfs_da_args_t *args, /* operation arguments */
  102. xfs_dabuf_t *lbp) /* leaf buffer */
  103. {
  104. xfs_inode_t *dp; /* incore directory inode */
  105. int error; /* error return value */
  106. xfs_dabuf_t *fbp; /* freespace buffer */
  107. xfs_dir2_db_t fdb; /* freespace block number */
  108. xfs_dir2_free_t *free; /* freespace structure */
  109. __be16 *from; /* pointer to freespace entry */
  110. int i; /* leaf freespace index */
  111. xfs_dir2_leaf_t *leaf; /* leaf structure */
  112. xfs_dir2_leaf_tail_t *ltp; /* leaf tail structure */
  113. xfs_mount_t *mp; /* filesystem mount point */
  114. int n; /* count of live freespc ents */
  115. xfs_dir2_data_off_t off; /* freespace entry value */
  116. __be16 *to; /* pointer to freespace entry */
  117. xfs_trans_t *tp; /* transaction pointer */
  118. xfs_dir2_trace_args_b("leaf_to_node", args, lbp);
  119. dp = args->dp;
  120. mp = dp->i_mount;
  121. tp = args->trans;
  122. /*
  123. * Add a freespace block to the directory.
  124. */
  125. if ((error = xfs_dir2_grow_inode(args, XFS_DIR2_FREE_SPACE, &fdb))) {
  126. return error;
  127. }
  128. ASSERT(fdb == XFS_DIR2_FREE_FIRSTDB(mp));
  129. /*
  130. * Get the buffer for the new freespace block.
  131. */
  132. if ((error = xfs_da_get_buf(tp, dp, XFS_DIR2_DB_TO_DA(mp, fdb), -1, &fbp,
  133. XFS_DATA_FORK))) {
  134. return error;
  135. }
  136. ASSERT(fbp != NULL);
  137. free = fbp->data;
  138. leaf = lbp->data;
  139. ltp = XFS_DIR2_LEAF_TAIL_P(mp, leaf);
  140. /*
  141. * Initialize the freespace block header.
  142. */
  143. free->hdr.magic = cpu_to_be32(XFS_DIR2_FREE_MAGIC);
  144. free->hdr.firstdb = 0;
  145. ASSERT(be32_to_cpu(ltp->bestcount) <= (uint)dp->i_d.di_size / mp->m_dirblksize);
  146. free->hdr.nvalid = ltp->bestcount;
  147. /*
  148. * Copy freespace entries from the leaf block to the new block.
  149. * Count active entries.
  150. */
  151. for (i = n = 0, from = XFS_DIR2_LEAF_BESTS_P(ltp), to = free->bests;
  152. i < be32_to_cpu(ltp->bestcount); i++, from++, to++) {
  153. if ((off = be16_to_cpu(*from)) != NULLDATAOFF)
  154. n++;
  155. *to = cpu_to_be16(off);
  156. }
  157. free->hdr.nused = cpu_to_be32(n);
  158. leaf->hdr.info.magic = cpu_to_be16(XFS_DIR2_LEAFN_MAGIC);
  159. /*
  160. * Log everything.
  161. */
  162. xfs_dir2_leaf_log_header(tp, lbp);
  163. xfs_dir2_free_log_header(tp, fbp);
  164. xfs_dir2_free_log_bests(tp, fbp, 0, be32_to_cpu(free->hdr.nvalid) - 1);
  165. xfs_da_buf_done(fbp);
  166. xfs_dir2_leafn_check(dp, lbp);
  167. return 0;
  168. }
  169. /*
  170. * Add a leaf entry to a leaf block in a node-form directory.
  171. * The other work necessary is done from the caller.
  172. */
  173. static int /* error */
  174. xfs_dir2_leafn_add(
  175. xfs_dabuf_t *bp, /* leaf buffer */
  176. xfs_da_args_t *args, /* operation arguments */
  177. int index) /* insertion pt for new entry */
  178. {
  179. int compact; /* compacting stale leaves */
  180. xfs_inode_t *dp; /* incore directory inode */
  181. int highstale; /* next stale entry */
  182. xfs_dir2_leaf_t *leaf; /* leaf structure */
  183. xfs_dir2_leaf_entry_t *lep; /* leaf entry */
  184. int lfloghigh; /* high leaf entry logging */
  185. int lfloglow; /* low leaf entry logging */
  186. int lowstale; /* previous stale entry */
  187. xfs_mount_t *mp; /* filesystem mount point */
  188. xfs_trans_t *tp; /* transaction pointer */
  189. xfs_dir2_trace_args_sb("leafn_add", args, index, bp);
  190. dp = args->dp;
  191. mp = dp->i_mount;
  192. tp = args->trans;
  193. leaf = bp->data;
  194. /*
  195. * Quick check just to make sure we are not going to index
  196. * into other peoples memory
  197. */
  198. if (index < 0)
  199. return XFS_ERROR(EFSCORRUPTED);
  200. /*
  201. * If there are already the maximum number of leaf entries in
  202. * the block, if there are no stale entries it won't fit.
  203. * Caller will do a split. If there are stale entries we'll do
  204. * a compact.
  205. */
  206. if (be16_to_cpu(leaf->hdr.count) == XFS_DIR2_MAX_LEAF_ENTS(mp)) {
  207. if (!leaf->hdr.stale)
  208. return XFS_ERROR(ENOSPC);
  209. compact = be16_to_cpu(leaf->hdr.stale) > 1;
  210. } else
  211. compact = 0;
  212. ASSERT(index == 0 || be32_to_cpu(leaf->ents[index - 1].hashval) <= args->hashval);
  213. ASSERT(index == be16_to_cpu(leaf->hdr.count) ||
  214. be32_to_cpu(leaf->ents[index].hashval) >= args->hashval);
  215. if (args->justcheck)
  216. return 0;
  217. /*
  218. * Compact out all but one stale leaf entry. Leaves behind
  219. * the entry closest to index.
  220. */
  221. if (compact) {
  222. xfs_dir2_leaf_compact_x1(bp, &index, &lowstale, &highstale,
  223. &lfloglow, &lfloghigh);
  224. }
  225. /*
  226. * Set impossible logging indices for this case.
  227. */
  228. else if (leaf->hdr.stale) {
  229. lfloglow = be16_to_cpu(leaf->hdr.count);
  230. lfloghigh = -1;
  231. }
  232. /*
  233. * No stale entries, just insert a space for the new entry.
  234. */
  235. if (!leaf->hdr.stale) {
  236. lep = &leaf->ents[index];
  237. if (index < be16_to_cpu(leaf->hdr.count))
  238. memmove(lep + 1, lep,
  239. (be16_to_cpu(leaf->hdr.count) - index) * sizeof(*lep));
  240. lfloglow = index;
  241. lfloghigh = be16_to_cpu(leaf->hdr.count);
  242. be16_add(&leaf->hdr.count, 1);
  243. }
  244. /*
  245. * There are stale entries. We'll use one for the new entry.
  246. */
  247. else {
  248. /*
  249. * If we didn't do a compact then we need to figure out
  250. * which stale entry will be used.
  251. */
  252. if (compact == 0) {
  253. /*
  254. * Find first stale entry before our insertion point.
  255. */
  256. for (lowstale = index - 1;
  257. lowstale >= 0 &&
  258. be32_to_cpu(leaf->ents[lowstale].address) !=
  259. XFS_DIR2_NULL_DATAPTR;
  260. lowstale--)
  261. continue;
  262. /*
  263. * Find next stale entry after insertion point.
  264. * Stop looking if the answer would be worse than
  265. * lowstale already found.
  266. */
  267. for (highstale = index;
  268. highstale < be16_to_cpu(leaf->hdr.count) &&
  269. be32_to_cpu(leaf->ents[highstale].address) !=
  270. XFS_DIR2_NULL_DATAPTR &&
  271. (lowstale < 0 ||
  272. index - lowstale - 1 >= highstale - index);
  273. highstale++)
  274. continue;
  275. }
  276. /*
  277. * Using the low stale entry.
  278. * Shift entries up toward the stale slot.
  279. */
  280. if (lowstale >= 0 &&
  281. (highstale == be16_to_cpu(leaf->hdr.count) ||
  282. index - lowstale - 1 < highstale - index)) {
  283. ASSERT(be32_to_cpu(leaf->ents[lowstale].address) ==
  284. XFS_DIR2_NULL_DATAPTR);
  285. ASSERT(index - lowstale - 1 >= 0);
  286. if (index - lowstale - 1 > 0)
  287. memmove(&leaf->ents[lowstale],
  288. &leaf->ents[lowstale + 1],
  289. (index - lowstale - 1) * sizeof(*lep));
  290. lep = &leaf->ents[index - 1];
  291. lfloglow = MIN(lowstale, lfloglow);
  292. lfloghigh = MAX(index - 1, lfloghigh);
  293. }
  294. /*
  295. * Using the high stale entry.
  296. * Shift entries down toward the stale slot.
  297. */
  298. else {
  299. ASSERT(be32_to_cpu(leaf->ents[highstale].address) ==
  300. XFS_DIR2_NULL_DATAPTR);
  301. ASSERT(highstale - index >= 0);
  302. if (highstale - index > 0)
  303. memmove(&leaf->ents[index + 1],
  304. &leaf->ents[index],
  305. (highstale - index) * sizeof(*lep));
  306. lep = &leaf->ents[index];
  307. lfloglow = MIN(index, lfloglow);
  308. lfloghigh = MAX(highstale, lfloghigh);
  309. }
  310. be16_add(&leaf->hdr.stale, -1);
  311. }
  312. /*
  313. * Insert the new entry, log everything.
  314. */
  315. lep->hashval = cpu_to_be32(args->hashval);
  316. lep->address = cpu_to_be32(XFS_DIR2_DB_OFF_TO_DATAPTR(mp,
  317. args->blkno, args->index));
  318. xfs_dir2_leaf_log_header(tp, bp);
  319. xfs_dir2_leaf_log_ents(tp, bp, lfloglow, lfloghigh);
  320. xfs_dir2_leafn_check(dp, bp);
  321. return 0;
  322. }
  323. #ifdef DEBUG
  324. /*
  325. * Check internal consistency of a leafn block.
  326. */
  327. void
  328. xfs_dir2_leafn_check(
  329. xfs_inode_t *dp, /* incore directory inode */
  330. xfs_dabuf_t *bp) /* leaf buffer */
  331. {
  332. int i; /* leaf index */
  333. xfs_dir2_leaf_t *leaf; /* leaf structure */
  334. xfs_mount_t *mp; /* filesystem mount point */
  335. int stale; /* count of stale leaves */
  336. leaf = bp->data;
  337. mp = dp->i_mount;
  338. ASSERT(be16_to_cpu(leaf->hdr.info.magic) == XFS_DIR2_LEAFN_MAGIC);
  339. ASSERT(be16_to_cpu(leaf->hdr.count) <= XFS_DIR2_MAX_LEAF_ENTS(mp));
  340. for (i = stale = 0; i < be16_to_cpu(leaf->hdr.count); i++) {
  341. if (i + 1 < be16_to_cpu(leaf->hdr.count)) {
  342. ASSERT(be32_to_cpu(leaf->ents[i].hashval) <=
  343. be32_to_cpu(leaf->ents[i + 1].hashval));
  344. }
  345. if (be32_to_cpu(leaf->ents[i].address) == XFS_DIR2_NULL_DATAPTR)
  346. stale++;
  347. }
  348. ASSERT(be16_to_cpu(leaf->hdr.stale) == stale);
  349. }
  350. #endif /* DEBUG */
  351. /*
  352. * Return the last hash value in the leaf.
  353. * Stale entries are ok.
  354. */
  355. xfs_dahash_t /* hash value */
  356. xfs_dir2_leafn_lasthash(
  357. xfs_dabuf_t *bp, /* leaf buffer */
  358. int *count) /* count of entries in leaf */
  359. {
  360. xfs_dir2_leaf_t *leaf; /* leaf structure */
  361. leaf = bp->data;
  362. ASSERT(be16_to_cpu(leaf->hdr.info.magic) == XFS_DIR2_LEAFN_MAGIC);
  363. if (count)
  364. *count = be16_to_cpu(leaf->hdr.count);
  365. if (!leaf->hdr.count)
  366. return 0;
  367. return be32_to_cpu(leaf->ents[be16_to_cpu(leaf->hdr.count) - 1].hashval);
  368. }
  369. /*
  370. * Look up a leaf entry in a node-format leaf block.
  371. * If this is an addname then the extrablk in state is a freespace block,
  372. * otherwise it's a data block.
  373. */
  374. int
  375. xfs_dir2_leafn_lookup_int(
  376. xfs_dabuf_t *bp, /* leaf buffer */
  377. xfs_da_args_t *args, /* operation arguments */
  378. int *indexp, /* out: leaf entry index */
  379. xfs_da_state_t *state) /* state to fill in */
  380. {
  381. xfs_dabuf_t *curbp; /* current data/free buffer */
  382. xfs_dir2_db_t curdb; /* current data block number */
  383. xfs_dir2_db_t curfdb; /* current free block number */
  384. xfs_dir2_data_entry_t *dep; /* data block entry */
  385. xfs_inode_t *dp; /* incore directory inode */
  386. int error; /* error return value */
  387. int fi; /* free entry index */
  388. xfs_dir2_free_t *free=NULL; /* free block structure */
  389. int index; /* leaf entry index */
  390. xfs_dir2_leaf_t *leaf; /* leaf structure */
  391. int length=0; /* length of new data entry */
  392. xfs_dir2_leaf_entry_t *lep; /* leaf entry */
  393. xfs_mount_t *mp; /* filesystem mount point */
  394. xfs_dir2_db_t newdb; /* new data block number */
  395. xfs_dir2_db_t newfdb; /* new free block number */
  396. xfs_trans_t *tp; /* transaction pointer */
  397. dp = args->dp;
  398. tp = args->trans;
  399. mp = dp->i_mount;
  400. leaf = bp->data;
  401. ASSERT(be16_to_cpu(leaf->hdr.info.magic) == XFS_DIR2_LEAFN_MAGIC);
  402. #ifdef __KERNEL__
  403. ASSERT(be16_to_cpu(leaf->hdr.count) > 0);
  404. #endif
  405. xfs_dir2_leafn_check(dp, bp);
  406. /*
  407. * Look up the hash value in the leaf entries.
  408. */
  409. index = xfs_dir2_leaf_search_hash(args, bp);
  410. /*
  411. * Do we have a buffer coming in?
  412. */
  413. if (state->extravalid)
  414. curbp = state->extrablk.bp;
  415. else
  416. curbp = NULL;
  417. /*
  418. * For addname, it's a free block buffer, get the block number.
  419. */
  420. if (args->addname) {
  421. curfdb = curbp ? state->extrablk.blkno : -1;
  422. curdb = -1;
  423. length = XFS_DIR2_DATA_ENTSIZE(args->namelen);
  424. if ((free = (curbp ? curbp->data : NULL)))
  425. ASSERT(be32_to_cpu(free->hdr.magic) == XFS_DIR2_FREE_MAGIC);
  426. }
  427. /*
  428. * For others, it's a data block buffer, get the block number.
  429. */
  430. else {
  431. curfdb = -1;
  432. curdb = curbp ? state->extrablk.blkno : -1;
  433. }
  434. /*
  435. * Loop over leaf entries with the right hash value.
  436. */
  437. for (lep = &leaf->ents[index];
  438. index < be16_to_cpu(leaf->hdr.count) && be32_to_cpu(lep->hashval) == args->hashval;
  439. lep++, index++) {
  440. /*
  441. * Skip stale leaf entries.
  442. */
  443. if (be32_to_cpu(lep->address) == XFS_DIR2_NULL_DATAPTR)
  444. continue;
  445. /*
  446. * Pull the data block number from the entry.
  447. */
  448. newdb = XFS_DIR2_DATAPTR_TO_DB(mp, be32_to_cpu(lep->address));
  449. /*
  450. * For addname, we're looking for a place to put the new entry.
  451. * We want to use a data block with an entry of equal
  452. * hash value to ours if there is one with room.
  453. */
  454. if (args->addname) {
  455. /*
  456. * If this block isn't the data block we already have
  457. * in hand, take a look at it.
  458. */
  459. if (newdb != curdb) {
  460. curdb = newdb;
  461. /*
  462. * Convert the data block to the free block
  463. * holding its freespace information.
  464. */
  465. newfdb = XFS_DIR2_DB_TO_FDB(mp, newdb);
  466. /*
  467. * If it's not the one we have in hand,
  468. * read it in.
  469. */
  470. if (newfdb != curfdb) {
  471. /*
  472. * If we had one before, drop it.
  473. */
  474. if (curbp)
  475. xfs_da_brelse(tp, curbp);
  476. /*
  477. * Read the free block.
  478. */
  479. if ((error = xfs_da_read_buf(tp, dp,
  480. XFS_DIR2_DB_TO_DA(mp,
  481. newfdb),
  482. -1, &curbp,
  483. XFS_DATA_FORK))) {
  484. return error;
  485. }
  486. free = curbp->data;
  487. ASSERT(be32_to_cpu(free->hdr.magic) ==
  488. XFS_DIR2_FREE_MAGIC);
  489. ASSERT((be32_to_cpu(free->hdr.firstdb) %
  490. XFS_DIR2_MAX_FREE_BESTS(mp)) ==
  491. 0);
  492. ASSERT(be32_to_cpu(free->hdr.firstdb) <= curdb);
  493. ASSERT(curdb <
  494. be32_to_cpu(free->hdr.firstdb) +
  495. be32_to_cpu(free->hdr.nvalid));
  496. }
  497. /*
  498. * Get the index for our entry.
  499. */
  500. fi = XFS_DIR2_DB_TO_FDINDEX(mp, curdb);
  501. /*
  502. * If it has room, return it.
  503. */
  504. if (unlikely(be16_to_cpu(free->bests[fi]) == NULLDATAOFF)) {
  505. XFS_ERROR_REPORT("xfs_dir2_leafn_lookup_int",
  506. XFS_ERRLEVEL_LOW, mp);
  507. if (curfdb != newfdb)
  508. xfs_da_brelse(tp, curbp);
  509. return XFS_ERROR(EFSCORRUPTED);
  510. }
  511. curfdb = newfdb;
  512. if (be16_to_cpu(free->bests[fi]) >= length) {
  513. *indexp = index;
  514. state->extravalid = 1;
  515. state->extrablk.bp = curbp;
  516. state->extrablk.blkno = curfdb;
  517. state->extrablk.index = fi;
  518. state->extrablk.magic =
  519. XFS_DIR2_FREE_MAGIC;
  520. ASSERT(args->oknoent);
  521. return XFS_ERROR(ENOENT);
  522. }
  523. }
  524. }
  525. /*
  526. * Not adding a new entry, so we really want to find
  527. * the name given to us.
  528. */
  529. else {
  530. /*
  531. * If it's a different data block, go get it.
  532. */
  533. if (newdb != curdb) {
  534. /*
  535. * If we had a block before, drop it.
  536. */
  537. if (curbp)
  538. xfs_da_brelse(tp, curbp);
  539. /*
  540. * Read the data block.
  541. */
  542. if ((error =
  543. xfs_da_read_buf(tp, dp,
  544. XFS_DIR2_DB_TO_DA(mp, newdb), -1,
  545. &curbp, XFS_DATA_FORK))) {
  546. return error;
  547. }
  548. xfs_dir2_data_check(dp, curbp);
  549. curdb = newdb;
  550. }
  551. /*
  552. * Point to the data entry.
  553. */
  554. dep = (xfs_dir2_data_entry_t *)
  555. ((char *)curbp->data +
  556. XFS_DIR2_DATAPTR_TO_OFF(mp, be32_to_cpu(lep->address)));
  557. /*
  558. * Compare the entry, return it if it matches.
  559. */
  560. if (dep->namelen == args->namelen &&
  561. dep->name[0] == args->name[0] &&
  562. memcmp(dep->name, args->name, args->namelen) == 0) {
  563. args->inumber = be64_to_cpu(dep->inumber);
  564. *indexp = index;
  565. state->extravalid = 1;
  566. state->extrablk.bp = curbp;
  567. state->extrablk.blkno = curdb;
  568. state->extrablk.index =
  569. (int)((char *)dep -
  570. (char *)curbp->data);
  571. state->extrablk.magic = XFS_DIR2_DATA_MAGIC;
  572. return XFS_ERROR(EEXIST);
  573. }
  574. }
  575. }
  576. /*
  577. * Didn't find a match.
  578. * If we are holding a buffer, give it back in case our caller
  579. * finds it useful.
  580. */
  581. if ((state->extravalid = (curbp != NULL))) {
  582. state->extrablk.bp = curbp;
  583. state->extrablk.index = -1;
  584. /*
  585. * For addname, giving back a free block.
  586. */
  587. if (args->addname) {
  588. state->extrablk.blkno = curfdb;
  589. state->extrablk.magic = XFS_DIR2_FREE_MAGIC;
  590. }
  591. /*
  592. * For other callers, giving back a data block.
  593. */
  594. else {
  595. state->extrablk.blkno = curdb;
  596. state->extrablk.magic = XFS_DIR2_DATA_MAGIC;
  597. }
  598. }
  599. /*
  600. * Return the final index, that will be the insertion point.
  601. */
  602. *indexp = index;
  603. ASSERT(index == be16_to_cpu(leaf->hdr.count) || args->oknoent);
  604. return XFS_ERROR(ENOENT);
  605. }
  606. /*
  607. * Move count leaf entries from source to destination leaf.
  608. * Log entries and headers. Stale entries are preserved.
  609. */
  610. static void
  611. xfs_dir2_leafn_moveents(
  612. xfs_da_args_t *args, /* operation arguments */
  613. xfs_dabuf_t *bp_s, /* source leaf buffer */
  614. int start_s, /* source leaf index */
  615. xfs_dabuf_t *bp_d, /* destination leaf buffer */
  616. int start_d, /* destination leaf index */
  617. int count) /* count of leaves to copy */
  618. {
  619. xfs_dir2_leaf_t *leaf_d; /* destination leaf structure */
  620. xfs_dir2_leaf_t *leaf_s; /* source leaf structure */
  621. int stale; /* count stale leaves copied */
  622. xfs_trans_t *tp; /* transaction pointer */
  623. xfs_dir2_trace_args_bibii("leafn_moveents", args, bp_s, start_s, bp_d,
  624. start_d, count);
  625. /*
  626. * Silently return if nothing to do.
  627. */
  628. if (count == 0) {
  629. return;
  630. }
  631. tp = args->trans;
  632. leaf_s = bp_s->data;
  633. leaf_d = bp_d->data;
  634. /*
  635. * If the destination index is not the end of the current
  636. * destination leaf entries, open up a hole in the destination
  637. * to hold the new entries.
  638. */
  639. if (start_d < be16_to_cpu(leaf_d->hdr.count)) {
  640. memmove(&leaf_d->ents[start_d + count], &leaf_d->ents[start_d],
  641. (be16_to_cpu(leaf_d->hdr.count) - start_d) *
  642. sizeof(xfs_dir2_leaf_entry_t));
  643. xfs_dir2_leaf_log_ents(tp, bp_d, start_d + count,
  644. count + be16_to_cpu(leaf_d->hdr.count) - 1);
  645. }
  646. /*
  647. * If the source has stale leaves, count the ones in the copy range
  648. * so we can update the header correctly.
  649. */
  650. if (leaf_s->hdr.stale) {
  651. int i; /* temp leaf index */
  652. for (i = start_s, stale = 0; i < start_s + count; i++) {
  653. if (be32_to_cpu(leaf_s->ents[i].address) == XFS_DIR2_NULL_DATAPTR)
  654. stale++;
  655. }
  656. } else
  657. stale = 0;
  658. /*
  659. * Copy the leaf entries from source to destination.
  660. */
  661. memcpy(&leaf_d->ents[start_d], &leaf_s->ents[start_s],
  662. count * sizeof(xfs_dir2_leaf_entry_t));
  663. xfs_dir2_leaf_log_ents(tp, bp_d, start_d, start_d + count - 1);
  664. /*
  665. * If there are source entries after the ones we copied,
  666. * delete the ones we copied by sliding the next ones down.
  667. */
  668. if (start_s + count < be16_to_cpu(leaf_s->hdr.count)) {
  669. memmove(&leaf_s->ents[start_s], &leaf_s->ents[start_s + count],
  670. count * sizeof(xfs_dir2_leaf_entry_t));
  671. xfs_dir2_leaf_log_ents(tp, bp_s, start_s, start_s + count - 1);
  672. }
  673. /*
  674. * Update the headers and log them.
  675. */
  676. be16_add(&leaf_s->hdr.count, -(count));
  677. be16_add(&leaf_s->hdr.stale, -(stale));
  678. be16_add(&leaf_d->hdr.count, count);
  679. be16_add(&leaf_d->hdr.stale, stale);
  680. xfs_dir2_leaf_log_header(tp, bp_s);
  681. xfs_dir2_leaf_log_header(tp, bp_d);
  682. xfs_dir2_leafn_check(args->dp, bp_s);
  683. xfs_dir2_leafn_check(args->dp, bp_d);
  684. }
  685. /*
  686. * Determine the sort order of two leaf blocks.
  687. * Returns 1 if both are valid and leaf2 should be before leaf1, else 0.
  688. */
  689. int /* sort order */
  690. xfs_dir2_leafn_order(
  691. xfs_dabuf_t *leaf1_bp, /* leaf1 buffer */
  692. xfs_dabuf_t *leaf2_bp) /* leaf2 buffer */
  693. {
  694. xfs_dir2_leaf_t *leaf1; /* leaf1 structure */
  695. xfs_dir2_leaf_t *leaf2; /* leaf2 structure */
  696. leaf1 = leaf1_bp->data;
  697. leaf2 = leaf2_bp->data;
  698. ASSERT(be16_to_cpu(leaf1->hdr.info.magic) == XFS_DIR2_LEAFN_MAGIC);
  699. ASSERT(be16_to_cpu(leaf2->hdr.info.magic) == XFS_DIR2_LEAFN_MAGIC);
  700. if (be16_to_cpu(leaf1->hdr.count) > 0 &&
  701. be16_to_cpu(leaf2->hdr.count) > 0 &&
  702. (be32_to_cpu(leaf2->ents[0].hashval) < be32_to_cpu(leaf1->ents[0].hashval) ||
  703. be32_to_cpu(leaf2->ents[be16_to_cpu(leaf2->hdr.count) - 1].hashval) <
  704. be32_to_cpu(leaf1->ents[be16_to_cpu(leaf1->hdr.count) - 1].hashval)))
  705. return 1;
  706. return 0;
  707. }
  708. /*
  709. * Rebalance leaf entries between two leaf blocks.
  710. * This is actually only called when the second block is new,
  711. * though the code deals with the general case.
  712. * A new entry will be inserted in one of the blocks, and that
  713. * entry is taken into account when balancing.
  714. */
  715. static void
  716. xfs_dir2_leafn_rebalance(
  717. xfs_da_state_t *state, /* btree cursor */
  718. xfs_da_state_blk_t *blk1, /* first btree block */
  719. xfs_da_state_blk_t *blk2) /* second btree block */
  720. {
  721. xfs_da_args_t *args; /* operation arguments */
  722. int count; /* count (& direction) leaves */
  723. int isleft; /* new goes in left leaf */
  724. xfs_dir2_leaf_t *leaf1; /* first leaf structure */
  725. xfs_dir2_leaf_t *leaf2; /* second leaf structure */
  726. int mid; /* midpoint leaf index */
  727. #ifdef DEBUG
  728. int oldstale; /* old count of stale leaves */
  729. #endif
  730. int oldsum; /* old total leaf count */
  731. int swap; /* swapped leaf blocks */
  732. args = state->args;
  733. /*
  734. * If the block order is wrong, swap the arguments.
  735. */
  736. if ((swap = xfs_dir2_leafn_order(blk1->bp, blk2->bp))) {
  737. xfs_da_state_blk_t *tmp; /* temp for block swap */
  738. tmp = blk1;
  739. blk1 = blk2;
  740. blk2 = tmp;
  741. }
  742. leaf1 = blk1->bp->data;
  743. leaf2 = blk2->bp->data;
  744. oldsum = be16_to_cpu(leaf1->hdr.count) + be16_to_cpu(leaf2->hdr.count);
  745. #ifdef DEBUG
  746. oldstale = be16_to_cpu(leaf1->hdr.stale) + be16_to_cpu(leaf2->hdr.stale);
  747. #endif
  748. mid = oldsum >> 1;
  749. /*
  750. * If the old leaf count was odd then the new one will be even,
  751. * so we need to divide the new count evenly.
  752. */
  753. if (oldsum & 1) {
  754. xfs_dahash_t midhash; /* middle entry hash value */
  755. if (mid >= be16_to_cpu(leaf1->hdr.count))
  756. midhash = be32_to_cpu(leaf2->ents[mid - be16_to_cpu(leaf1->hdr.count)].hashval);
  757. else
  758. midhash = be32_to_cpu(leaf1->ents[mid].hashval);
  759. isleft = args->hashval <= midhash;
  760. }
  761. /*
  762. * If the old count is even then the new count is odd, so there's
  763. * no preferred side for the new entry.
  764. * Pick the left one.
  765. */
  766. else
  767. isleft = 1;
  768. /*
  769. * Calculate moved entry count. Positive means left-to-right,
  770. * negative means right-to-left. Then move the entries.
  771. */
  772. count = be16_to_cpu(leaf1->hdr.count) - mid + (isleft == 0);
  773. if (count > 0)
  774. xfs_dir2_leafn_moveents(args, blk1->bp,
  775. be16_to_cpu(leaf1->hdr.count) - count, blk2->bp, 0, count);
  776. else if (count < 0)
  777. xfs_dir2_leafn_moveents(args, blk2->bp, 0, blk1->bp,
  778. be16_to_cpu(leaf1->hdr.count), count);
  779. ASSERT(be16_to_cpu(leaf1->hdr.count) + be16_to_cpu(leaf2->hdr.count) == oldsum);
  780. ASSERT(be16_to_cpu(leaf1->hdr.stale) + be16_to_cpu(leaf2->hdr.stale) == oldstale);
  781. /*
  782. * Mark whether we're inserting into the old or new leaf.
  783. */
  784. if (be16_to_cpu(leaf1->hdr.count) < be16_to_cpu(leaf2->hdr.count))
  785. state->inleaf = swap;
  786. else if (be16_to_cpu(leaf1->hdr.count) > be16_to_cpu(leaf2->hdr.count))
  787. state->inleaf = !swap;
  788. else
  789. state->inleaf =
  790. swap ^ (blk1->index <= be16_to_cpu(leaf1->hdr.count));
  791. /*
  792. * Adjust the expected index for insertion.
  793. */
  794. if (!state->inleaf)
  795. blk2->index = blk1->index - be16_to_cpu(leaf1->hdr.count);
  796. /*
  797. * Finally sanity check just to make sure we are not returning a negative index
  798. */
  799. if(blk2->index < 0) {
  800. state->inleaf = 1;
  801. blk2->index = 0;
  802. cmn_err(CE_ALERT,
  803. "xfs_dir2_leafn_rebalance: picked the wrong leaf? reverting original leaf: "
  804. "blk1->index %d\n",
  805. blk1->index);
  806. }
  807. }
  808. /*
  809. * Remove an entry from a node directory.
  810. * This removes the leaf entry and the data entry,
  811. * and updates the free block if necessary.
  812. */
  813. static int /* error */
  814. xfs_dir2_leafn_remove(
  815. xfs_da_args_t *args, /* operation arguments */
  816. xfs_dabuf_t *bp, /* leaf buffer */
  817. int index, /* leaf entry index */
  818. xfs_da_state_blk_t *dblk, /* data block */
  819. int *rval) /* resulting block needs join */
  820. {
  821. xfs_dir2_data_t *data; /* data block structure */
  822. xfs_dir2_db_t db; /* data block number */
  823. xfs_dabuf_t *dbp; /* data block buffer */
  824. xfs_dir2_data_entry_t *dep; /* data block entry */
  825. xfs_inode_t *dp; /* incore directory inode */
  826. xfs_dir2_leaf_t *leaf; /* leaf structure */
  827. xfs_dir2_leaf_entry_t *lep; /* leaf entry */
  828. int longest; /* longest data free entry */
  829. int off; /* data block entry offset */
  830. xfs_mount_t *mp; /* filesystem mount point */
  831. int needlog; /* need to log data header */
  832. int needscan; /* need to rescan data frees */
  833. xfs_trans_t *tp; /* transaction pointer */
  834. xfs_dir2_trace_args_sb("leafn_remove", args, index, bp);
  835. dp = args->dp;
  836. tp = args->trans;
  837. mp = dp->i_mount;
  838. leaf = bp->data;
  839. ASSERT(be16_to_cpu(leaf->hdr.info.magic) == XFS_DIR2_LEAFN_MAGIC);
  840. /*
  841. * Point to the entry we're removing.
  842. */
  843. lep = &leaf->ents[index];
  844. /*
  845. * Extract the data block and offset from the entry.
  846. */
  847. db = XFS_DIR2_DATAPTR_TO_DB(mp, be32_to_cpu(lep->address));
  848. ASSERT(dblk->blkno == db);
  849. off = XFS_DIR2_DATAPTR_TO_OFF(mp, be32_to_cpu(lep->address));
  850. ASSERT(dblk->index == off);
  851. /*
  852. * Kill the leaf entry by marking it stale.
  853. * Log the leaf block changes.
  854. */
  855. be16_add(&leaf->hdr.stale, 1);
  856. xfs_dir2_leaf_log_header(tp, bp);
  857. lep->address = cpu_to_be32(XFS_DIR2_NULL_DATAPTR);
  858. xfs_dir2_leaf_log_ents(tp, bp, index, index);
  859. /*
  860. * Make the data entry free. Keep track of the longest freespace
  861. * in the data block in case it changes.
  862. */
  863. dbp = dblk->bp;
  864. data = dbp->data;
  865. dep = (xfs_dir2_data_entry_t *)((char *)data + off);
  866. longest = be16_to_cpu(data->hdr.bestfree[0].length);
  867. needlog = needscan = 0;
  868. xfs_dir2_data_make_free(tp, dbp, off,
  869. XFS_DIR2_DATA_ENTSIZE(dep->namelen), &needlog, &needscan);
  870. /*
  871. * Rescan the data block freespaces for bestfree.
  872. * Log the data block header if needed.
  873. */
  874. if (needscan)
  875. xfs_dir2_data_freescan(mp, data, &needlog, NULL);
  876. if (needlog)
  877. xfs_dir2_data_log_header(tp, dbp);
  878. xfs_dir2_data_check(dp, dbp);
  879. /*
  880. * If the longest data block freespace changes, need to update
  881. * the corresponding freeblock entry.
  882. */
  883. if (longest < be16_to_cpu(data->hdr.bestfree[0].length)) {
  884. int error; /* error return value */
  885. xfs_dabuf_t *fbp; /* freeblock buffer */
  886. xfs_dir2_db_t fdb; /* freeblock block number */
  887. int findex; /* index in freeblock entries */
  888. xfs_dir2_free_t *free; /* freeblock structure */
  889. int logfree; /* need to log free entry */
  890. /*
  891. * Convert the data block number to a free block,
  892. * read in the free block.
  893. */
  894. fdb = XFS_DIR2_DB_TO_FDB(mp, db);
  895. if ((error = xfs_da_read_buf(tp, dp, XFS_DIR2_DB_TO_DA(mp, fdb),
  896. -1, &fbp, XFS_DATA_FORK))) {
  897. return error;
  898. }
  899. free = fbp->data;
  900. ASSERT(be32_to_cpu(free->hdr.magic) == XFS_DIR2_FREE_MAGIC);
  901. ASSERT(be32_to_cpu(free->hdr.firstdb) ==
  902. XFS_DIR2_MAX_FREE_BESTS(mp) *
  903. (fdb - XFS_DIR2_FREE_FIRSTDB(mp)));
  904. /*
  905. * Calculate which entry we need to fix.
  906. */
  907. findex = XFS_DIR2_DB_TO_FDINDEX(mp, db);
  908. longest = be16_to_cpu(data->hdr.bestfree[0].length);
  909. /*
  910. * If the data block is now empty we can get rid of it
  911. * (usually).
  912. */
  913. if (longest == mp->m_dirblksize - (uint)sizeof(data->hdr)) {
  914. /*
  915. * Try to punch out the data block.
  916. */
  917. error = xfs_dir2_shrink_inode(args, db, dbp);
  918. if (error == 0) {
  919. dblk->bp = NULL;
  920. data = NULL;
  921. }
  922. /*
  923. * We can get ENOSPC if there's no space reservation.
  924. * In this case just drop the buffer and some one else
  925. * will eventually get rid of the empty block.
  926. */
  927. else if (error == ENOSPC && args->total == 0)
  928. xfs_da_buf_done(dbp);
  929. else
  930. return error;
  931. }
  932. /*
  933. * If we got rid of the data block, we can eliminate that entry
  934. * in the free block.
  935. */
  936. if (data == NULL) {
  937. /*
  938. * One less used entry in the free table.
  939. */
  940. be32_add(&free->hdr.nused, -1);
  941. xfs_dir2_free_log_header(tp, fbp);
  942. /*
  943. * If this was the last entry in the table, we can
  944. * trim the table size back. There might be other
  945. * entries at the end referring to non-existent
  946. * data blocks, get those too.
  947. */
  948. if (findex == be32_to_cpu(free->hdr.nvalid) - 1) {
  949. int i; /* free entry index */
  950. for (i = findex - 1;
  951. i >= 0 && be16_to_cpu(free->bests[i]) == NULLDATAOFF;
  952. i--)
  953. continue;
  954. free->hdr.nvalid = cpu_to_be32(i + 1);
  955. logfree = 0;
  956. }
  957. /*
  958. * Not the last entry, just punch it out.
  959. */
  960. else {
  961. free->bests[findex] = cpu_to_be16(NULLDATAOFF);
  962. logfree = 1;
  963. }
  964. /*
  965. * If there are no useful entries left in the block,
  966. * get rid of the block if we can.
  967. */
  968. if (!free->hdr.nused) {
  969. error = xfs_dir2_shrink_inode(args, fdb, fbp);
  970. if (error == 0) {
  971. fbp = NULL;
  972. logfree = 0;
  973. } else if (error != ENOSPC || args->total != 0)
  974. return error;
  975. /*
  976. * It's possible to get ENOSPC if there is no
  977. * space reservation. In this case some one
  978. * else will eventually get rid of this block.
  979. */
  980. }
  981. }
  982. /*
  983. * Data block is not empty, just set the free entry to
  984. * the new value.
  985. */
  986. else {
  987. free->bests[findex] = cpu_to_be16(longest);
  988. logfree = 1;
  989. }
  990. /*
  991. * Log the free entry that changed, unless we got rid of it.
  992. */
  993. if (logfree)
  994. xfs_dir2_free_log_bests(tp, fbp, findex, findex);
  995. /*
  996. * Drop the buffer if we still have it.
  997. */
  998. if (fbp)
  999. xfs_da_buf_done(fbp);
  1000. }
  1001. xfs_dir2_leafn_check(dp, bp);
  1002. /*
  1003. * Return indication of whether this leaf block is emtpy enough
  1004. * to justify trying to join it with a neighbor.
  1005. */
  1006. *rval =
  1007. ((uint)sizeof(leaf->hdr) +
  1008. (uint)sizeof(leaf->ents[0]) *
  1009. (be16_to_cpu(leaf->hdr.count) - be16_to_cpu(leaf->hdr.stale))) <
  1010. mp->m_dir_magicpct;
  1011. return 0;
  1012. }
  1013. /*
  1014. * Split the leaf entries in the old block into old and new blocks.
  1015. */
  1016. int /* error */
  1017. xfs_dir2_leafn_split(
  1018. xfs_da_state_t *state, /* btree cursor */
  1019. xfs_da_state_blk_t *oldblk, /* original block */
  1020. xfs_da_state_blk_t *newblk) /* newly created block */
  1021. {
  1022. xfs_da_args_t *args; /* operation arguments */
  1023. xfs_dablk_t blkno; /* new leaf block number */
  1024. int error; /* error return value */
  1025. xfs_mount_t *mp; /* filesystem mount point */
  1026. /*
  1027. * Allocate space for a new leaf node.
  1028. */
  1029. args = state->args;
  1030. mp = args->dp->i_mount;
  1031. ASSERT(args != NULL);
  1032. ASSERT(oldblk->magic == XFS_DIR2_LEAFN_MAGIC);
  1033. error = xfs_da_grow_inode(args, &blkno);
  1034. if (error) {
  1035. return error;
  1036. }
  1037. /*
  1038. * Initialize the new leaf block.
  1039. */
  1040. error = xfs_dir2_leaf_init(args, XFS_DIR2_DA_TO_DB(mp, blkno),
  1041. &newblk->bp, XFS_DIR2_LEAFN_MAGIC);
  1042. if (error) {
  1043. return error;
  1044. }
  1045. newblk->blkno = blkno;
  1046. newblk->magic = XFS_DIR2_LEAFN_MAGIC;
  1047. /*
  1048. * Rebalance the entries across the two leaves, link the new
  1049. * block into the leaves.
  1050. */
  1051. xfs_dir2_leafn_rebalance(state, oldblk, newblk);
  1052. error = xfs_da_blk_link(state, oldblk, newblk);
  1053. if (error) {
  1054. return error;
  1055. }
  1056. /*
  1057. * Insert the new entry in the correct block.
  1058. */
  1059. if (state->inleaf)
  1060. error = xfs_dir2_leafn_add(oldblk->bp, args, oldblk->index);
  1061. else
  1062. error = xfs_dir2_leafn_add(newblk->bp, args, newblk->index);
  1063. /*
  1064. * Update last hashval in each block since we added the name.
  1065. */
  1066. oldblk->hashval = xfs_dir2_leafn_lasthash(oldblk->bp, NULL);
  1067. newblk->hashval = xfs_dir2_leafn_lasthash(newblk->bp, NULL);
  1068. xfs_dir2_leafn_check(args->dp, oldblk->bp);
  1069. xfs_dir2_leafn_check(args->dp, newblk->bp);
  1070. return error;
  1071. }
  1072. /*
  1073. * Check a leaf block and its neighbors to see if the block should be
  1074. * collapsed into one or the other neighbor. Always keep the block
  1075. * with the smaller block number.
  1076. * If the current block is over 50% full, don't try to join it, return 0.
  1077. * If the block is empty, fill in the state structure and return 2.
  1078. * If it can be collapsed, fill in the state structure and return 1.
  1079. * If nothing can be done, return 0.
  1080. */
  1081. int /* error */
  1082. xfs_dir2_leafn_toosmall(
  1083. xfs_da_state_t *state, /* btree cursor */
  1084. int *action) /* resulting action to take */
  1085. {
  1086. xfs_da_state_blk_t *blk; /* leaf block */
  1087. xfs_dablk_t blkno; /* leaf block number */
  1088. xfs_dabuf_t *bp; /* leaf buffer */
  1089. int bytes; /* bytes in use */
  1090. int count; /* leaf live entry count */
  1091. int error; /* error return value */
  1092. int forward; /* sibling block direction */
  1093. int i; /* sibling counter */
  1094. xfs_da_blkinfo_t *info; /* leaf block header */
  1095. xfs_dir2_leaf_t *leaf; /* leaf structure */
  1096. int rval; /* result from path_shift */
  1097. /*
  1098. * Check for the degenerate case of the block being over 50% full.
  1099. * If so, it's not worth even looking to see if we might be able
  1100. * to coalesce with a sibling.
  1101. */
  1102. blk = &state->path.blk[state->path.active - 1];
  1103. info = blk->bp->data;
  1104. ASSERT(be16_to_cpu(info->magic) == XFS_DIR2_LEAFN_MAGIC);
  1105. leaf = (xfs_dir2_leaf_t *)info;
  1106. count = be16_to_cpu(leaf->hdr.count) - be16_to_cpu(leaf->hdr.stale);
  1107. bytes = (uint)sizeof(leaf->hdr) + count * (uint)sizeof(leaf->ents[0]);
  1108. if (bytes > (state->blocksize >> 1)) {
  1109. /*
  1110. * Blk over 50%, don't try to join.
  1111. */
  1112. *action = 0;
  1113. return 0;
  1114. }
  1115. /*
  1116. * Check for the degenerate case of the block being empty.
  1117. * If the block is empty, we'll simply delete it, no need to
  1118. * coalesce it with a sibling block. We choose (arbitrarily)
  1119. * to merge with the forward block unless it is NULL.
  1120. */
  1121. if (count == 0) {
  1122. /*
  1123. * Make altpath point to the block we want to keep and
  1124. * path point to the block we want to drop (this one).
  1125. */
  1126. forward = (info->forw != 0);
  1127. memcpy(&state->altpath, &state->path, sizeof(state->path));
  1128. error = xfs_da_path_shift(state, &state->altpath, forward, 0,
  1129. &rval);
  1130. if (error)
  1131. return error;
  1132. *action = rval ? 2 : 0;
  1133. return 0;
  1134. }
  1135. /*
  1136. * Examine each sibling block to see if we can coalesce with
  1137. * at least 25% free space to spare. We need to figure out
  1138. * whether to merge with the forward or the backward block.
  1139. * We prefer coalescing with the lower numbered sibling so as
  1140. * to shrink a directory over time.
  1141. */
  1142. forward = be32_to_cpu(info->forw) < be32_to_cpu(info->back);
  1143. for (i = 0, bp = NULL; i < 2; forward = !forward, i++) {
  1144. blkno = forward ? be32_to_cpu(info->forw) : be32_to_cpu(info->back);
  1145. if (blkno == 0)
  1146. continue;
  1147. /*
  1148. * Read the sibling leaf block.
  1149. */
  1150. if ((error =
  1151. xfs_da_read_buf(state->args->trans, state->args->dp, blkno,
  1152. -1, &bp, XFS_DATA_FORK))) {
  1153. return error;
  1154. }
  1155. ASSERT(bp != NULL);
  1156. /*
  1157. * Count bytes in the two blocks combined.
  1158. */
  1159. leaf = (xfs_dir2_leaf_t *)info;
  1160. count = be16_to_cpu(leaf->hdr.count) - be16_to_cpu(leaf->hdr.stale);
  1161. bytes = state->blocksize - (state->blocksize >> 2);
  1162. leaf = bp->data;
  1163. ASSERT(be16_to_cpu(leaf->hdr.info.magic) == XFS_DIR2_LEAFN_MAGIC);
  1164. count += be16_to_cpu(leaf->hdr.count) - be16_to_cpu(leaf->hdr.stale);
  1165. bytes -= count * (uint)sizeof(leaf->ents[0]);
  1166. /*
  1167. * Fits with at least 25% to spare.
  1168. */
  1169. if (bytes >= 0)
  1170. break;
  1171. xfs_da_brelse(state->args->trans, bp);
  1172. }
  1173. /*
  1174. * Didn't like either block, give up.
  1175. */
  1176. if (i >= 2) {
  1177. *action = 0;
  1178. return 0;
  1179. }
  1180. /*
  1181. * Done with the sibling leaf block here, drop the dabuf
  1182. * so path_shift can get it.
  1183. */
  1184. xfs_da_buf_done(bp);
  1185. /*
  1186. * Make altpath point to the block we want to keep (the lower
  1187. * numbered block) and path point to the block we want to drop.
  1188. */
  1189. memcpy(&state->altpath, &state->path, sizeof(state->path));
  1190. if (blkno < blk->blkno)
  1191. error = xfs_da_path_shift(state, &state->altpath, forward, 0,
  1192. &rval);
  1193. else
  1194. error = xfs_da_path_shift(state, &state->path, forward, 0,
  1195. &rval);
  1196. if (error) {
  1197. return error;
  1198. }
  1199. *action = rval ? 0 : 1;
  1200. return 0;
  1201. }
  1202. /*
  1203. * Move all the leaf entries from drop_blk to save_blk.
  1204. * This is done as part of a join operation.
  1205. */
  1206. void
  1207. xfs_dir2_leafn_unbalance(
  1208. xfs_da_state_t *state, /* cursor */
  1209. xfs_da_state_blk_t *drop_blk, /* dead block */
  1210. xfs_da_state_blk_t *save_blk) /* surviving block */
  1211. {
  1212. xfs_da_args_t *args; /* operation arguments */
  1213. xfs_dir2_leaf_t *drop_leaf; /* dead leaf structure */
  1214. xfs_dir2_leaf_t *save_leaf; /* surviving leaf structure */
  1215. args = state->args;
  1216. ASSERT(drop_blk->magic == XFS_DIR2_LEAFN_MAGIC);
  1217. ASSERT(save_blk->magic == XFS_DIR2_LEAFN_MAGIC);
  1218. drop_leaf = drop_blk->bp->data;
  1219. save_leaf = save_blk->bp->data;
  1220. ASSERT(be16_to_cpu(drop_leaf->hdr.info.magic) == XFS_DIR2_LEAFN_MAGIC);
  1221. ASSERT(be16_to_cpu(save_leaf->hdr.info.magic) == XFS_DIR2_LEAFN_MAGIC);
  1222. /*
  1223. * If there are any stale leaf entries, take this opportunity
  1224. * to purge them.
  1225. */
  1226. if (drop_leaf->hdr.stale)
  1227. xfs_dir2_leaf_compact(args, drop_blk->bp);
  1228. if (save_leaf->hdr.stale)
  1229. xfs_dir2_leaf_compact(args, save_blk->bp);
  1230. /*
  1231. * Move the entries from drop to the appropriate end of save.
  1232. */
  1233. drop_blk->hashval = be32_to_cpu(drop_leaf->ents[be16_to_cpu(drop_leaf->hdr.count) - 1].hashval);
  1234. if (xfs_dir2_leafn_order(save_blk->bp, drop_blk->bp))
  1235. xfs_dir2_leafn_moveents(args, drop_blk->bp, 0, save_blk->bp, 0,
  1236. be16_to_cpu(drop_leaf->hdr.count));
  1237. else
  1238. xfs_dir2_leafn_moveents(args, drop_blk->bp, 0, save_blk->bp,
  1239. be16_to_cpu(save_leaf->hdr.count), be16_to_cpu(drop_leaf->hdr.count));
  1240. save_blk->hashval = be32_to_cpu(save_leaf->ents[be16_to_cpu(save_leaf->hdr.count) - 1].hashval);
  1241. xfs_dir2_leafn_check(args->dp, save_blk->bp);
  1242. }
  1243. /*
  1244. * Top-level node form directory addname routine.
  1245. */
  1246. int /* error */
  1247. xfs_dir2_node_addname(
  1248. xfs_da_args_t *args) /* operation arguments */
  1249. {
  1250. xfs_da_state_blk_t *blk; /* leaf block for insert */
  1251. int error; /* error return value */
  1252. int rval; /* sub-return value */
  1253. xfs_da_state_t *state; /* btree cursor */
  1254. xfs_dir2_trace_args("node_addname", args);
  1255. /*
  1256. * Allocate and initialize the state (btree cursor).
  1257. */
  1258. state = xfs_da_state_alloc();
  1259. state->args = args;
  1260. state->mp = args->dp->i_mount;
  1261. state->blocksize = state->mp->m_dirblksize;
  1262. state->node_ents = state->mp->m_dir_node_ents;
  1263. /*
  1264. * Look up the name. We're not supposed to find it, but
  1265. * this gives us the insertion point.
  1266. */
  1267. error = xfs_da_node_lookup_int(state, &rval);
  1268. if (error)
  1269. rval = error;
  1270. if (rval != ENOENT) {
  1271. goto done;
  1272. }
  1273. /*
  1274. * Add the data entry to a data block.
  1275. * Extravalid is set to a freeblock found by lookup.
  1276. */
  1277. rval = xfs_dir2_node_addname_int(args,
  1278. state->extravalid ? &state->extrablk : NULL);
  1279. if (rval) {
  1280. goto done;
  1281. }
  1282. blk = &state->path.blk[state->path.active - 1];
  1283. ASSERT(blk->magic == XFS_DIR2_LEAFN_MAGIC);
  1284. /*
  1285. * Add the new leaf entry.
  1286. */
  1287. rval = xfs_dir2_leafn_add(blk->bp, args, blk->index);
  1288. if (rval == 0) {
  1289. /*
  1290. * It worked, fix the hash values up the btree.
  1291. */
  1292. if (!args->justcheck)
  1293. xfs_da_fixhashpath(state, &state->path);
  1294. } else {
  1295. /*
  1296. * It didn't work, we need to split the leaf block.
  1297. */
  1298. if (args->total == 0) {
  1299. ASSERT(rval == ENOSPC);
  1300. goto done;
  1301. }
  1302. /*
  1303. * Split the leaf block and insert the new entry.
  1304. */
  1305. rval = xfs_da_split(state);
  1306. }
  1307. done:
  1308. xfs_da_state_free(state);
  1309. return rval;
  1310. }
  1311. /*
  1312. * Add the data entry for a node-format directory name addition.
  1313. * The leaf entry is added in xfs_dir2_leafn_add.
  1314. * We may enter with a freespace block that the lookup found.
  1315. */
  1316. static int /* error */
  1317. xfs_dir2_node_addname_int(
  1318. xfs_da_args_t *args, /* operation arguments */
  1319. xfs_da_state_blk_t *fblk) /* optional freespace block */
  1320. {
  1321. xfs_dir2_data_t *data; /* data block structure */
  1322. xfs_dir2_db_t dbno; /* data block number */
  1323. xfs_dabuf_t *dbp; /* data block buffer */
  1324. xfs_dir2_data_entry_t *dep; /* data entry pointer */
  1325. xfs_inode_t *dp; /* incore directory inode */
  1326. xfs_dir2_data_unused_t *dup; /* data unused entry pointer */
  1327. int error; /* error return value */
  1328. xfs_dir2_db_t fbno; /* freespace block number */
  1329. xfs_dabuf_t *fbp; /* freespace buffer */
  1330. int findex; /* freespace entry index */
  1331. xfs_dir2_free_t *free=NULL; /* freespace block structure */
  1332. xfs_dir2_db_t ifbno; /* initial freespace block no */
  1333. xfs_dir2_db_t lastfbno=0; /* highest freespace block no */
  1334. int length; /* length of the new entry */
  1335. int logfree; /* need to log free entry */
  1336. xfs_mount_t *mp; /* filesystem mount point */
  1337. int needlog; /* need to log data header */
  1338. int needscan; /* need to rescan data frees */
  1339. __be16 *tagp; /* data entry tag pointer */
  1340. xfs_trans_t *tp; /* transaction pointer */
  1341. dp = args->dp;
  1342. mp = dp->i_mount;
  1343. tp = args->trans;
  1344. length = XFS_DIR2_DATA_ENTSIZE(args->namelen);
  1345. /*
  1346. * If we came in with a freespace block that means that lookup
  1347. * found an entry with our hash value. This is the freespace
  1348. * block for that data entry.
  1349. */
  1350. if (fblk) {
  1351. fbp = fblk->bp;
  1352. /*
  1353. * Remember initial freespace block number.
  1354. */
  1355. ifbno = fblk->blkno;
  1356. free = fbp->data;
  1357. ASSERT(be32_to_cpu(free->hdr.magic) == XFS_DIR2_FREE_MAGIC);
  1358. findex = fblk->index;
  1359. /*
  1360. * This means the free entry showed that the data block had
  1361. * space for our entry, so we remembered it.
  1362. * Use that data block.
  1363. */
  1364. if (findex >= 0) {
  1365. ASSERT(findex < be32_to_cpu(free->hdr.nvalid));
  1366. ASSERT(be16_to_cpu(free->bests[findex]) != NULLDATAOFF);
  1367. ASSERT(be16_to_cpu(free->bests[findex]) >= length);
  1368. dbno = be32_to_cpu(free->hdr.firstdb) + findex;
  1369. }
  1370. /*
  1371. * The data block looked at didn't have enough room.
  1372. * We'll start at the beginning of the freespace entries.
  1373. */
  1374. else {
  1375. dbno = -1;
  1376. findex = 0;
  1377. }
  1378. }
  1379. /*
  1380. * Didn't come in with a freespace block, so don't have a data block.
  1381. */
  1382. else {
  1383. ifbno = dbno = -1;
  1384. fbp = NULL;
  1385. findex = 0;
  1386. }
  1387. /*
  1388. * If we don't have a data block yet, we're going to scan the
  1389. * freespace blocks looking for one. Figure out what the
  1390. * highest freespace block number is.
  1391. */
  1392. if (dbno == -1) {
  1393. xfs_fileoff_t fo; /* freespace block number */
  1394. if ((error = xfs_bmap_last_offset(tp, dp, &fo, XFS_DATA_FORK)))
  1395. return error;
  1396. lastfbno = XFS_DIR2_DA_TO_DB(mp, (xfs_dablk_t)fo);
  1397. fbno = ifbno;
  1398. }
  1399. /*
  1400. * While we haven't identified a data block, search the freeblock
  1401. * data for a good data block. If we find a null freeblock entry,
  1402. * indicating a hole in the data blocks, remember that.
  1403. */
  1404. while (dbno == -1) {
  1405. /*
  1406. * If we don't have a freeblock in hand, get the next one.
  1407. */
  1408. if (fbp == NULL) {
  1409. /*
  1410. * Happens the first time through unless lookup gave
  1411. * us a freespace block to start with.
  1412. */
  1413. if (++fbno == 0)
  1414. fbno = XFS_DIR2_FREE_FIRSTDB(mp);
  1415. /*
  1416. * If it's ifbno we already looked at it.
  1417. */
  1418. if (fbno == ifbno)
  1419. fbno++;
  1420. /*
  1421. * If it's off the end we're done.
  1422. */
  1423. if (fbno >= lastfbno)
  1424. break;
  1425. /*
  1426. * Read the block. There can be holes in the
  1427. * freespace blocks, so this might not succeed.
  1428. * This should be really rare, so there's no reason
  1429. * to avoid it.
  1430. */
  1431. if ((error = xfs_da_read_buf(tp, dp,
  1432. XFS_DIR2_DB_TO_DA(mp, fbno), -2, &fbp,
  1433. XFS_DATA_FORK))) {
  1434. return error;
  1435. }
  1436. if (unlikely(fbp == NULL)) {
  1437. continue;
  1438. }
  1439. free = fbp->data;
  1440. ASSERT(be32_to_cpu(free->hdr.magic) == XFS_DIR2_FREE_MAGIC);
  1441. findex = 0;
  1442. }
  1443. /*
  1444. * Look at the current free entry. Is it good enough?
  1445. */
  1446. if (be16_to_cpu(free->bests[findex]) != NULLDATAOFF &&
  1447. be16_to_cpu(free->bests[findex]) >= length)
  1448. dbno = be32_to_cpu(free->hdr.firstdb) + findex;
  1449. else {
  1450. /*
  1451. * Are we done with the freeblock?
  1452. */
  1453. if (++findex == be32_to_cpu(free->hdr.nvalid)) {
  1454. /*
  1455. * Drop the block.
  1456. */
  1457. xfs_da_brelse(tp, fbp);
  1458. fbp = NULL;
  1459. if (fblk && fblk->bp)
  1460. fblk->bp = NULL;
  1461. }
  1462. }
  1463. }
  1464. /*
  1465. * If we don't have a data block, we need to allocate one and make
  1466. * the freespace entries refer to it.
  1467. */
  1468. if (unlikely(dbno == -1)) {
  1469. /*
  1470. * Not allowed to allocate, return failure.
  1471. */
  1472. if (args->justcheck || args->total == 0) {
  1473. /*
  1474. * Drop the freespace buffer unless it came from our
  1475. * caller.
  1476. */
  1477. if ((fblk == NULL || fblk->bp == NULL) && fbp != NULL)
  1478. xfs_da_buf_done(fbp);
  1479. return XFS_ERROR(ENOSPC);
  1480. }
  1481. /*
  1482. * Allocate and initialize the new data block.
  1483. */
  1484. if (unlikely((error = xfs_dir2_grow_inode(args,
  1485. XFS_DIR2_DATA_SPACE,
  1486. &dbno)) ||
  1487. (error = xfs_dir2_data_init(args, dbno, &dbp)))) {
  1488. /*
  1489. * Drop the freespace buffer unless it came from our
  1490. * caller.
  1491. */
  1492. if ((fblk == NULL || fblk->bp == NULL) && fbp != NULL)
  1493. xfs_da_buf_done(fbp);
  1494. return error;
  1495. }
  1496. /*
  1497. * If (somehow) we have a freespace block, get rid of it.
  1498. */
  1499. if (fbp)
  1500. xfs_da_brelse(tp, fbp);
  1501. if (fblk && fblk->bp)
  1502. fblk->bp = NULL;
  1503. /*
  1504. * Get the freespace block corresponding to the data block
  1505. * that was just allocated.
  1506. */
  1507. fbno = XFS_DIR2_DB_TO_FDB(mp, dbno);
  1508. if (unlikely(error = xfs_da_read_buf(tp, dp,
  1509. XFS_DIR2_DB_TO_DA(mp, fbno), -2, &fbp,
  1510. XFS_DATA_FORK))) {
  1511. xfs_da_buf_done(dbp);
  1512. return error;
  1513. }
  1514. /*
  1515. * If there wasn't a freespace block, the read will
  1516. * return a NULL fbp. Allocate and initialize a new one.
  1517. */
  1518. if( fbp == NULL ) {
  1519. if ((error = xfs_dir2_grow_inode(args, XFS_DIR2_FREE_SPACE,
  1520. &fbno))) {
  1521. return error;
  1522. }
  1523. if (unlikely(XFS_DIR2_DB_TO_FDB(mp, dbno) != fbno)) {
  1524. cmn_err(CE_ALERT,
  1525. "xfs_dir2_node_addname_int: dir ino "
  1526. "%llu needed freesp block %lld for\n"
  1527. " data block %lld, got %lld\n"
  1528. " ifbno %llu lastfbno %d\n",
  1529. (unsigned long long)dp->i_ino,
  1530. (long long)XFS_DIR2_DB_TO_FDB(mp, dbno),
  1531. (long long)dbno, (long long)fbno,
  1532. (unsigned long long)ifbno, lastfbno);
  1533. if (fblk) {
  1534. cmn_err(CE_ALERT,
  1535. " fblk 0x%p blkno %llu "
  1536. "index %d magic 0x%x\n",
  1537. fblk,
  1538. (unsigned long long)fblk->blkno,
  1539. fblk->index,
  1540. fblk->magic);
  1541. } else {
  1542. cmn_err(CE_ALERT,
  1543. " ... fblk is NULL\n");
  1544. }
  1545. XFS_ERROR_REPORT("xfs_dir2_node_addname_int",
  1546. XFS_ERRLEVEL_LOW, mp);
  1547. return XFS_ERROR(EFSCORRUPTED);
  1548. }
  1549. /*
  1550. * Get a buffer for the new block.
  1551. */
  1552. if ((error = xfs_da_get_buf(tp, dp,
  1553. XFS_DIR2_DB_TO_DA(mp, fbno),
  1554. -1, &fbp, XFS_DATA_FORK))) {
  1555. return error;
  1556. }
  1557. ASSERT(fbp != NULL);
  1558. /*
  1559. * Initialize the new block to be empty, and remember
  1560. * its first slot as our empty slot.
  1561. */
  1562. free = fbp->data;
  1563. free->hdr.magic = cpu_to_be32(XFS_DIR2_FREE_MAGIC);
  1564. free->hdr.firstdb = cpu_to_be32(
  1565. (fbno - XFS_DIR2_FREE_FIRSTDB(mp)) *
  1566. XFS_DIR2_MAX_FREE_BESTS(mp));
  1567. free->hdr.nvalid = 0;
  1568. free->hdr.nused = 0;
  1569. } else {
  1570. free = fbp->data;
  1571. ASSERT(be32_to_cpu(free->hdr.magic) == XFS_DIR2_FREE_MAGIC);
  1572. }
  1573. /*
  1574. * Set the freespace block index from the data block number.
  1575. */
  1576. findex = XFS_DIR2_DB_TO_FDINDEX(mp, dbno);
  1577. /*
  1578. * If it's after the end of the current entries in the
  1579. * freespace block, extend that table.
  1580. */
  1581. if (findex >= be32_to_cpu(free->hdr.nvalid)) {
  1582. ASSERT(findex < XFS_DIR2_MAX_FREE_BESTS(mp));
  1583. free->hdr.nvalid = cpu_to_be32(findex + 1);
  1584. /*
  1585. * Tag new entry so nused will go up.
  1586. */
  1587. free->bests[findex] = cpu_to_be16(NULLDATAOFF);
  1588. }
  1589. /*
  1590. * If this entry was for an empty data block
  1591. * (this should always be true) then update the header.
  1592. */
  1593. if (be16_to_cpu(free->bests[findex]) == NULLDATAOFF) {
  1594. be32_add(&free->hdr.nused, 1);
  1595. xfs_dir2_free_log_header(tp, fbp);
  1596. }
  1597. /*
  1598. * Update the real value in the table.
  1599. * We haven't allocated the data entry yet so this will
  1600. * change again.
  1601. */
  1602. data = dbp->data;
  1603. free->bests[findex] = data->hdr.bestfree[0].length;
  1604. logfree = 1;
  1605. }
  1606. /*
  1607. * We had a data block so we don't have to make a new one.
  1608. */
  1609. else {
  1610. /*
  1611. * If just checking, we succeeded.
  1612. */
  1613. if (args->justcheck) {
  1614. if ((fblk == NULL || fblk->bp == NULL) && fbp != NULL)
  1615. xfs_da_buf_done(fbp);
  1616. return 0;
  1617. }
  1618. /*
  1619. * Read the data block in.
  1620. */
  1621. if (unlikely(
  1622. error = xfs_da_read_buf(tp, dp, XFS_DIR2_DB_TO_DA(mp, dbno),
  1623. -1, &dbp, XFS_DATA_FORK))) {
  1624. if ((fblk == NULL || fblk->bp == NULL) && fbp != NULL)
  1625. xfs_da_buf_done(fbp);
  1626. return error;
  1627. }
  1628. data = dbp->data;
  1629. logfree = 0;
  1630. }
  1631. ASSERT(be16_to_cpu(data->hdr.bestfree[0].length) >= length);
  1632. /*
  1633. * Point to the existing unused space.
  1634. */
  1635. dup = (xfs_dir2_data_unused_t *)
  1636. ((char *)data + be16_to_cpu(data->hdr.bestfree[0].offset));
  1637. needscan = needlog = 0;
  1638. /*
  1639. * Mark the first part of the unused space, inuse for us.
  1640. */
  1641. xfs_dir2_data_use_free(tp, dbp, dup,
  1642. (xfs_dir2_data_aoff_t)((char *)dup - (char *)data), length,
  1643. &needlog, &needscan);
  1644. /*
  1645. * Fill in the new entry and log it.
  1646. */
  1647. dep = (xfs_dir2_data_entry_t *)dup;
  1648. dep->inumber = cpu_to_be64(args->inumber);
  1649. dep->namelen = args->namelen;
  1650. memcpy(dep->name, args->name, dep->namelen);
  1651. tagp = XFS_DIR2_DATA_ENTRY_TAG_P(dep);
  1652. *tagp = cpu_to_be16((char *)dep - (char *)data);
  1653. xfs_dir2_data_log_entry(tp, dbp, dep);
  1654. /*
  1655. * Rescan the block for bestfree if needed.
  1656. */
  1657. if (needscan)
  1658. xfs_dir2_data_freescan(mp, data, &needlog, NULL);
  1659. /*
  1660. * Log the data block header if needed.
  1661. */
  1662. if (needlog)
  1663. xfs_dir2_data_log_header(tp, dbp);
  1664. /*
  1665. * If the freespace entry is now wrong, update it.
  1666. */
  1667. if (be16_to_cpu(free->bests[findex]) != be16_to_cpu(data->hdr.bestfree[0].length)) {
  1668. free->bests[findex] = data->hdr.bestfree[0].length;
  1669. logfree = 1;
  1670. }
  1671. /*
  1672. * Log the freespace entry if needed.
  1673. */
  1674. if (logfree)
  1675. xfs_dir2_free_log_bests(tp, fbp, findex, findex);
  1676. /*
  1677. * If the caller didn't hand us the freespace block, drop it.
  1678. */
  1679. if ((fblk == NULL || fblk->bp == NULL) && fbp != NULL)
  1680. xfs_da_buf_done(fbp);
  1681. /*
  1682. * Return the data block and offset in args, then drop the data block.
  1683. */
  1684. args->blkno = (xfs_dablk_t)dbno;
  1685. args->index = be16_to_cpu(*tagp);
  1686. xfs_da_buf_done(dbp);
  1687. return 0;
  1688. }
  1689. /*
  1690. * Lookup an entry in a node-format directory.
  1691. * All the real work happens in xfs_da_node_lookup_int.
  1692. * The only real output is the inode number of the entry.
  1693. */
  1694. int /* error */
  1695. xfs_dir2_node_lookup(
  1696. xfs_da_args_t *args) /* operation arguments */
  1697. {
  1698. int error; /* error return value */
  1699. int i; /* btree level */
  1700. int rval; /* operation return value */
  1701. xfs_da_state_t *state; /* btree cursor */
  1702. xfs_dir2_trace_args("node_lookup", args);
  1703. /*
  1704. * Allocate and initialize the btree cursor.
  1705. */
  1706. state = xfs_da_state_alloc();
  1707. state->args = args;
  1708. state->mp = args->dp->i_mount;
  1709. state->blocksize = state->mp->m_dirblksize;
  1710. state->node_ents = state->mp->m_dir_node_ents;
  1711. /*
  1712. * Fill in the path to the entry in the cursor.
  1713. */
  1714. error = xfs_da_node_lookup_int(state, &rval);
  1715. if (error)
  1716. rval = error;
  1717. /*
  1718. * Release the btree blocks and leaf block.
  1719. */
  1720. for (i = 0; i < state->path.active; i++) {
  1721. xfs_da_brelse(args->trans, state->path.blk[i].bp);
  1722. state->path.blk[i].bp = NULL;
  1723. }
  1724. /*
  1725. * Release the data block if we have it.
  1726. */
  1727. if (state->extravalid && state->extrablk.bp) {
  1728. xfs_da_brelse(args->trans, state->extrablk.bp);
  1729. state->extrablk.bp = NULL;
  1730. }
  1731. xfs_da_state_free(state);
  1732. return rval;
  1733. }
  1734. /*
  1735. * Remove an entry from a node-format directory.
  1736. */
  1737. int /* error */
  1738. xfs_dir2_node_removename(
  1739. xfs_da_args_t *args) /* operation arguments */
  1740. {
  1741. xfs_da_state_blk_t *blk; /* leaf block */
  1742. int error; /* error return value */
  1743. int rval; /* operation return value */
  1744. xfs_da_state_t *state; /* btree cursor */
  1745. xfs_dir2_trace_args("node_removename", args);
  1746. /*
  1747. * Allocate and initialize the btree cursor.
  1748. */
  1749. state = xfs_da_state_alloc();
  1750. state->args = args;
  1751. state->mp = args->dp->i_mount;
  1752. state->blocksize = state->mp->m_dirblksize;
  1753. state->node_ents = state->mp->m_dir_node_ents;
  1754. /*
  1755. * Look up the entry we're deleting, set up the cursor.
  1756. */
  1757. error = xfs_da_node_lookup_int(state, &rval);
  1758. if (error) {
  1759. rval = error;
  1760. }
  1761. /*
  1762. * Didn't find it, upper layer screwed up.
  1763. */
  1764. if (rval != EEXIST) {
  1765. xfs_da_state_free(state);
  1766. return rval;
  1767. }
  1768. blk = &state->path.blk[state->path.active - 1];
  1769. ASSERT(blk->magic == XFS_DIR2_LEAFN_MAGIC);
  1770. ASSERT(state->extravalid);
  1771. /*
  1772. * Remove the leaf and data entries.
  1773. * Extrablk refers to the data block.
  1774. */
  1775. error = xfs_dir2_leafn_remove(args, blk->bp, blk->index,
  1776. &state->extrablk, &rval);
  1777. if (error) {
  1778. return error;
  1779. }
  1780. /*
  1781. * Fix the hash values up the btree.
  1782. */
  1783. xfs_da_fixhashpath(state, &state->path);
  1784. /*
  1785. * If we need to join leaf blocks, do it.
  1786. */
  1787. if (rval && state->path.active > 1)
  1788. error = xfs_da_join(state);
  1789. /*
  1790. * If no errors so far, try conversion to leaf format.
  1791. */
  1792. if (!error)
  1793. error = xfs_dir2_node_to_leaf(state);
  1794. xfs_da_state_free(state);
  1795. return error;
  1796. }
  1797. /*
  1798. * Replace an entry's inode number in a node-format directory.
  1799. */
  1800. int /* error */
  1801. xfs_dir2_node_replace(
  1802. xfs_da_args_t *args) /* operation arguments */
  1803. {
  1804. xfs_da_state_blk_t *blk; /* leaf block */
  1805. xfs_dir2_data_t *data; /* data block structure */
  1806. xfs_dir2_data_entry_t *dep; /* data entry changed */
  1807. int error; /* error return value */
  1808. int i; /* btree level */
  1809. xfs_ino_t inum; /* new inode number */
  1810. xfs_dir2_leaf_t *leaf; /* leaf structure */
  1811. xfs_dir2_leaf_entry_t *lep; /* leaf entry being changed */
  1812. int rval; /* internal return value */
  1813. xfs_da_state_t *state; /* btree cursor */
  1814. xfs_dir2_trace_args("node_replace", args);
  1815. /*
  1816. * Allocate and initialize the btree cursor.
  1817. */
  1818. state = xfs_da_state_alloc();
  1819. state->args = args;
  1820. state->mp = args->dp->i_mount;
  1821. state->blocksize = state->mp->m_dirblksize;
  1822. state->node_ents = state->mp->m_dir_node_ents;
  1823. inum = args->inumber;
  1824. /*
  1825. * Lookup the entry to change in the btree.
  1826. */
  1827. error = xfs_da_node_lookup_int(state, &rval);
  1828. if (error) {
  1829. rval = error;
  1830. }
  1831. /*
  1832. * It should be found, since the vnodeops layer has looked it up
  1833. * and locked it. But paranoia is good.
  1834. */
  1835. if (rval == EEXIST) {
  1836. /*
  1837. * Find the leaf entry.
  1838. */
  1839. blk = &state->path.blk[state->path.active - 1];
  1840. ASSERT(blk->magic == XFS_DIR2_LEAFN_MAGIC);
  1841. leaf = blk->bp->data;
  1842. lep = &leaf->ents[blk->index];
  1843. ASSERT(state->extravalid);
  1844. /*
  1845. * Point to the data entry.
  1846. */
  1847. data = state->extrablk.bp->data;
  1848. ASSERT(be32_to_cpu(data->hdr.magic) == XFS_DIR2_DATA_MAGIC);
  1849. dep = (xfs_dir2_data_entry_t *)
  1850. ((char *)data +
  1851. XFS_DIR2_DATAPTR_TO_OFF(state->mp, be32_to_cpu(lep->address)));
  1852. ASSERT(inum != be64_to_cpu(dep->inumber));
  1853. /*
  1854. * Fill in the new inode number and log the entry.
  1855. */
  1856. dep->inumber = cpu_to_be64(inum);
  1857. xfs_dir2_data_log_entry(args->trans, state->extrablk.bp, dep);
  1858. rval = 0;
  1859. }
  1860. /*
  1861. * Didn't find it, and we're holding a data block. Drop it.
  1862. */
  1863. else if (state->extravalid) {
  1864. xfs_da_brelse(args->trans, state->extrablk.bp);
  1865. state->extrablk.bp = NULL;
  1866. }
  1867. /*
  1868. * Release all the buffers in the cursor.
  1869. */
  1870. for (i = 0; i < state->path.active; i++) {
  1871. xfs_da_brelse(args->trans, state->path.blk[i].bp);
  1872. state->path.blk[i].bp = NULL;
  1873. }
  1874. xfs_da_state_free(state);
  1875. return rval;
  1876. }
  1877. /*
  1878. * Trim off a trailing empty freespace block.
  1879. * Return (in rvalp) 1 if we did it, 0 if not.
  1880. */
  1881. int /* error */
  1882. xfs_dir2_node_trim_free(
  1883. xfs_da_args_t *args, /* operation arguments */
  1884. xfs_fileoff_t fo, /* free block number */
  1885. int *rvalp) /* out: did something */
  1886. {
  1887. xfs_dabuf_t *bp; /* freespace buffer */
  1888. xfs_inode_t *dp; /* incore directory inode */
  1889. int error; /* error return code */
  1890. xfs_dir2_free_t *free; /* freespace structure */
  1891. xfs_mount_t *mp; /* filesystem mount point */
  1892. xfs_trans_t *tp; /* transaction pointer */
  1893. dp = args->dp;
  1894. mp = dp->i_mount;
  1895. tp = args->trans;
  1896. /*
  1897. * Read the freespace block.
  1898. */
  1899. if (unlikely(error = xfs_da_read_buf(tp, dp, (xfs_dablk_t)fo, -2, &bp,
  1900. XFS_DATA_FORK))) {
  1901. return error;
  1902. }
  1903. /*
  1904. * There can be holes in freespace. If fo is a hole, there's
  1905. * nothing to do.
  1906. */
  1907. if (bp == NULL) {
  1908. return 0;
  1909. }
  1910. free = bp->data;
  1911. ASSERT(be32_to_cpu(free->hdr.magic) == XFS_DIR2_FREE_MAGIC);
  1912. /*
  1913. * If there are used entries, there's nothing to do.
  1914. */
  1915. if (be32_to_cpu(free->hdr.nused) > 0) {
  1916. xfs_da_brelse(tp, bp);
  1917. *rvalp = 0;
  1918. return 0;
  1919. }
  1920. /*
  1921. * Blow the block away.
  1922. */
  1923. if ((error =
  1924. xfs_dir2_shrink_inode(args, XFS_DIR2_DA_TO_DB(mp, (xfs_dablk_t)fo),
  1925. bp))) {
  1926. /*
  1927. * Can't fail with ENOSPC since that only happens with no
  1928. * space reservation, when breaking up an extent into two
  1929. * pieces. This is the last block of an extent.
  1930. */
  1931. ASSERT(error != ENOSPC);
  1932. xfs_da_brelse(tp, bp);
  1933. return error;
  1934. }
  1935. /*
  1936. * Return that we succeeded.
  1937. */
  1938. *rvalp = 1;
  1939. return 0;
  1940. }