xfs_dir2_leaf.c 50 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844
  1. // SPDX-License-Identifier: GPL-2.0
  2. /*
  3. * Copyright (c) 2000-2003,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_format.h"
  10. #include "xfs_log_format.h"
  11. #include "xfs_trans_resv.h"
  12. #include "xfs_mount.h"
  13. #include "xfs_da_format.h"
  14. #include "xfs_da_btree.h"
  15. #include "xfs_inode.h"
  16. #include "xfs_bmap.h"
  17. #include "xfs_dir2.h"
  18. #include "xfs_dir2_priv.h"
  19. #include "xfs_error.h"
  20. #include "xfs_trace.h"
  21. #include "xfs_trans.h"
  22. #include "xfs_buf_item.h"
  23. #include "xfs_cksum.h"
  24. #include "xfs_log.h"
  25. /*
  26. * Local function declarations.
  27. */
  28. static int xfs_dir2_leaf_lookup_int(xfs_da_args_t *args, struct xfs_buf **lbpp,
  29. int *indexp, struct xfs_buf **dbpp);
  30. static void xfs_dir3_leaf_log_bests(struct xfs_da_args *args,
  31. struct xfs_buf *bp, int first, int last);
  32. static void xfs_dir3_leaf_log_tail(struct xfs_da_args *args,
  33. struct xfs_buf *bp);
  34. /*
  35. * Check the internal consistency of a leaf1 block.
  36. * Pop an assert if something is wrong.
  37. */
  38. #ifdef DEBUG
  39. static xfs_failaddr_t
  40. xfs_dir3_leaf1_check(
  41. struct xfs_inode *dp,
  42. struct xfs_buf *bp)
  43. {
  44. struct xfs_dir2_leaf *leaf = bp->b_addr;
  45. struct xfs_dir3_icleaf_hdr leafhdr;
  46. dp->d_ops->leaf_hdr_from_disk(&leafhdr, leaf);
  47. if (leafhdr.magic == XFS_DIR3_LEAF1_MAGIC) {
  48. struct xfs_dir3_leaf_hdr *leaf3 = bp->b_addr;
  49. if (be64_to_cpu(leaf3->info.blkno) != bp->b_bn)
  50. return __this_address;
  51. } else if (leafhdr.magic != XFS_DIR2_LEAF1_MAGIC)
  52. return __this_address;
  53. return xfs_dir3_leaf_check_int(dp->i_mount, dp, &leafhdr, leaf);
  54. }
  55. static inline void
  56. xfs_dir3_leaf_check(
  57. struct xfs_inode *dp,
  58. struct xfs_buf *bp)
  59. {
  60. xfs_failaddr_t fa;
  61. fa = xfs_dir3_leaf1_check(dp, bp);
  62. if (!fa)
  63. return;
  64. xfs_corruption_error(__func__, XFS_ERRLEVEL_LOW, dp->i_mount,
  65. bp->b_addr, BBTOB(bp->b_length), __FILE__, __LINE__,
  66. fa);
  67. ASSERT(0);
  68. }
  69. #else
  70. #define xfs_dir3_leaf_check(dp, bp)
  71. #endif
  72. xfs_failaddr_t
  73. xfs_dir3_leaf_check_int(
  74. struct xfs_mount *mp,
  75. struct xfs_inode *dp,
  76. struct xfs_dir3_icleaf_hdr *hdr,
  77. struct xfs_dir2_leaf *leaf)
  78. {
  79. struct xfs_dir2_leaf_entry *ents;
  80. xfs_dir2_leaf_tail_t *ltp;
  81. int stale;
  82. int i;
  83. const struct xfs_dir_ops *ops;
  84. struct xfs_dir3_icleaf_hdr leafhdr;
  85. struct xfs_da_geometry *geo = mp->m_dir_geo;
  86. /*
  87. * we can be passed a null dp here from a verifier, so we need to go the
  88. * hard way to get them.
  89. */
  90. ops = xfs_dir_get_ops(mp, dp);
  91. if (!hdr) {
  92. ops->leaf_hdr_from_disk(&leafhdr, leaf);
  93. hdr = &leafhdr;
  94. }
  95. ents = ops->leaf_ents_p(leaf);
  96. ltp = xfs_dir2_leaf_tail_p(geo, leaf);
  97. /*
  98. * XXX (dgc): This value is not restrictive enough.
  99. * Should factor in the size of the bests table as well.
  100. * We can deduce a value for that from di_size.
  101. */
  102. if (hdr->count > ops->leaf_max_ents(geo))
  103. return __this_address;
  104. /* Leaves and bests don't overlap in leaf format. */
  105. if ((hdr->magic == XFS_DIR2_LEAF1_MAGIC ||
  106. hdr->magic == XFS_DIR3_LEAF1_MAGIC) &&
  107. (char *)&ents[hdr->count] > (char *)xfs_dir2_leaf_bests_p(ltp))
  108. return __this_address;
  109. /* Check hash value order, count stale entries. */
  110. for (i = stale = 0; i < hdr->count; i++) {
  111. if (i + 1 < hdr->count) {
  112. if (be32_to_cpu(ents[i].hashval) >
  113. be32_to_cpu(ents[i + 1].hashval))
  114. return __this_address;
  115. }
  116. if (ents[i].address == cpu_to_be32(XFS_DIR2_NULL_DATAPTR))
  117. stale++;
  118. }
  119. if (hdr->stale != stale)
  120. return __this_address;
  121. return NULL;
  122. }
  123. /*
  124. * We verify the magic numbers before decoding the leaf header so that on debug
  125. * kernels we don't get assertion failures in xfs_dir3_leaf_hdr_from_disk() due
  126. * to incorrect magic numbers.
  127. */
  128. static xfs_failaddr_t
  129. xfs_dir3_leaf_verify(
  130. struct xfs_buf *bp,
  131. uint16_t magic)
  132. {
  133. struct xfs_mount *mp = bp->b_target->bt_mount;
  134. struct xfs_dir2_leaf *leaf = bp->b_addr;
  135. ASSERT(magic == XFS_DIR2_LEAF1_MAGIC || magic == XFS_DIR2_LEAFN_MAGIC);
  136. if (xfs_sb_version_hascrc(&mp->m_sb)) {
  137. struct xfs_dir3_leaf_hdr *leaf3 = bp->b_addr;
  138. uint16_t magic3;
  139. magic3 = (magic == XFS_DIR2_LEAF1_MAGIC) ? XFS_DIR3_LEAF1_MAGIC
  140. : XFS_DIR3_LEAFN_MAGIC;
  141. if (leaf3->info.hdr.magic != cpu_to_be16(magic3))
  142. return __this_address;
  143. if (!uuid_equal(&leaf3->info.uuid, &mp->m_sb.sb_meta_uuid))
  144. return __this_address;
  145. if (be64_to_cpu(leaf3->info.blkno) != bp->b_bn)
  146. return __this_address;
  147. if (!xfs_log_check_lsn(mp, be64_to_cpu(leaf3->info.lsn)))
  148. return __this_address;
  149. } else {
  150. if (leaf->hdr.info.magic != cpu_to_be16(magic))
  151. return __this_address;
  152. }
  153. return xfs_dir3_leaf_check_int(mp, NULL, NULL, leaf);
  154. }
  155. static void
  156. __read_verify(
  157. struct xfs_buf *bp,
  158. uint16_t magic)
  159. {
  160. struct xfs_mount *mp = bp->b_target->bt_mount;
  161. xfs_failaddr_t fa;
  162. if (xfs_sb_version_hascrc(&mp->m_sb) &&
  163. !xfs_buf_verify_cksum(bp, XFS_DIR3_LEAF_CRC_OFF))
  164. xfs_verifier_error(bp, -EFSBADCRC, __this_address);
  165. else {
  166. fa = xfs_dir3_leaf_verify(bp, magic);
  167. if (fa)
  168. xfs_verifier_error(bp, -EFSCORRUPTED, fa);
  169. }
  170. }
  171. static void
  172. __write_verify(
  173. struct xfs_buf *bp,
  174. uint16_t magic)
  175. {
  176. struct xfs_mount *mp = bp->b_target->bt_mount;
  177. struct xfs_buf_log_item *bip = bp->b_log_item;
  178. struct xfs_dir3_leaf_hdr *hdr3 = bp->b_addr;
  179. xfs_failaddr_t fa;
  180. fa = xfs_dir3_leaf_verify(bp, magic);
  181. if (fa) {
  182. xfs_verifier_error(bp, -EFSCORRUPTED, fa);
  183. return;
  184. }
  185. if (!xfs_sb_version_hascrc(&mp->m_sb))
  186. return;
  187. if (bip)
  188. hdr3->info.lsn = cpu_to_be64(bip->bli_item.li_lsn);
  189. xfs_buf_update_cksum(bp, XFS_DIR3_LEAF_CRC_OFF);
  190. }
  191. static xfs_failaddr_t
  192. xfs_dir3_leaf1_verify(
  193. struct xfs_buf *bp)
  194. {
  195. return xfs_dir3_leaf_verify(bp, XFS_DIR2_LEAF1_MAGIC);
  196. }
  197. static void
  198. xfs_dir3_leaf1_read_verify(
  199. struct xfs_buf *bp)
  200. {
  201. __read_verify(bp, XFS_DIR2_LEAF1_MAGIC);
  202. }
  203. static void
  204. xfs_dir3_leaf1_write_verify(
  205. struct xfs_buf *bp)
  206. {
  207. __write_verify(bp, XFS_DIR2_LEAF1_MAGIC);
  208. }
  209. static xfs_failaddr_t
  210. xfs_dir3_leafn_verify(
  211. struct xfs_buf *bp)
  212. {
  213. return xfs_dir3_leaf_verify(bp, XFS_DIR2_LEAFN_MAGIC);
  214. }
  215. static void
  216. xfs_dir3_leafn_read_verify(
  217. struct xfs_buf *bp)
  218. {
  219. __read_verify(bp, XFS_DIR2_LEAFN_MAGIC);
  220. }
  221. static void
  222. xfs_dir3_leafn_write_verify(
  223. struct xfs_buf *bp)
  224. {
  225. __write_verify(bp, XFS_DIR2_LEAFN_MAGIC);
  226. }
  227. const struct xfs_buf_ops xfs_dir3_leaf1_buf_ops = {
  228. .name = "xfs_dir3_leaf1",
  229. .verify_read = xfs_dir3_leaf1_read_verify,
  230. .verify_write = xfs_dir3_leaf1_write_verify,
  231. .verify_struct = xfs_dir3_leaf1_verify,
  232. };
  233. const struct xfs_buf_ops xfs_dir3_leafn_buf_ops = {
  234. .name = "xfs_dir3_leafn",
  235. .verify_read = xfs_dir3_leafn_read_verify,
  236. .verify_write = xfs_dir3_leafn_write_verify,
  237. .verify_struct = xfs_dir3_leafn_verify,
  238. };
  239. int
  240. xfs_dir3_leaf_read(
  241. struct xfs_trans *tp,
  242. struct xfs_inode *dp,
  243. xfs_dablk_t fbno,
  244. xfs_daddr_t mappedbno,
  245. struct xfs_buf **bpp)
  246. {
  247. int err;
  248. err = xfs_da_read_buf(tp, dp, fbno, mappedbno, bpp,
  249. XFS_DATA_FORK, &xfs_dir3_leaf1_buf_ops);
  250. if (!err && tp && *bpp)
  251. xfs_trans_buf_set_type(tp, *bpp, XFS_BLFT_DIR_LEAF1_BUF);
  252. return err;
  253. }
  254. int
  255. xfs_dir3_leafn_read(
  256. struct xfs_trans *tp,
  257. struct xfs_inode *dp,
  258. xfs_dablk_t fbno,
  259. xfs_daddr_t mappedbno,
  260. struct xfs_buf **bpp)
  261. {
  262. int err;
  263. err = xfs_da_read_buf(tp, dp, fbno, mappedbno, bpp,
  264. XFS_DATA_FORK, &xfs_dir3_leafn_buf_ops);
  265. if (!err && tp && *bpp)
  266. xfs_trans_buf_set_type(tp, *bpp, XFS_BLFT_DIR_LEAFN_BUF);
  267. return err;
  268. }
  269. /*
  270. * Initialize a new leaf block, leaf1 or leafn magic accepted.
  271. */
  272. static void
  273. xfs_dir3_leaf_init(
  274. struct xfs_mount *mp,
  275. struct xfs_trans *tp,
  276. struct xfs_buf *bp,
  277. xfs_ino_t owner,
  278. uint16_t type)
  279. {
  280. struct xfs_dir2_leaf *leaf = bp->b_addr;
  281. ASSERT(type == XFS_DIR2_LEAF1_MAGIC || type == XFS_DIR2_LEAFN_MAGIC);
  282. if (xfs_sb_version_hascrc(&mp->m_sb)) {
  283. struct xfs_dir3_leaf_hdr *leaf3 = bp->b_addr;
  284. memset(leaf3, 0, sizeof(*leaf3));
  285. leaf3->info.hdr.magic = (type == XFS_DIR2_LEAF1_MAGIC)
  286. ? cpu_to_be16(XFS_DIR3_LEAF1_MAGIC)
  287. : cpu_to_be16(XFS_DIR3_LEAFN_MAGIC);
  288. leaf3->info.blkno = cpu_to_be64(bp->b_bn);
  289. leaf3->info.owner = cpu_to_be64(owner);
  290. uuid_copy(&leaf3->info.uuid, &mp->m_sb.sb_meta_uuid);
  291. } else {
  292. memset(leaf, 0, sizeof(*leaf));
  293. leaf->hdr.info.magic = cpu_to_be16(type);
  294. }
  295. /*
  296. * If it's a leaf-format directory initialize the tail.
  297. * Caller is responsible for initialising the bests table.
  298. */
  299. if (type == XFS_DIR2_LEAF1_MAGIC) {
  300. struct xfs_dir2_leaf_tail *ltp;
  301. ltp = xfs_dir2_leaf_tail_p(mp->m_dir_geo, leaf);
  302. ltp->bestcount = 0;
  303. bp->b_ops = &xfs_dir3_leaf1_buf_ops;
  304. xfs_trans_buf_set_type(tp, bp, XFS_BLFT_DIR_LEAF1_BUF);
  305. } else {
  306. bp->b_ops = &xfs_dir3_leafn_buf_ops;
  307. xfs_trans_buf_set_type(tp, bp, XFS_BLFT_DIR_LEAFN_BUF);
  308. }
  309. }
  310. int
  311. xfs_dir3_leaf_get_buf(
  312. xfs_da_args_t *args,
  313. xfs_dir2_db_t bno,
  314. struct xfs_buf **bpp,
  315. uint16_t magic)
  316. {
  317. struct xfs_inode *dp = args->dp;
  318. struct xfs_trans *tp = args->trans;
  319. struct xfs_mount *mp = dp->i_mount;
  320. struct xfs_buf *bp;
  321. int error;
  322. ASSERT(magic == XFS_DIR2_LEAF1_MAGIC || magic == XFS_DIR2_LEAFN_MAGIC);
  323. ASSERT(bno >= xfs_dir2_byte_to_db(args->geo, XFS_DIR2_LEAF_OFFSET) &&
  324. bno < xfs_dir2_byte_to_db(args->geo, XFS_DIR2_FREE_OFFSET));
  325. error = xfs_da_get_buf(tp, dp, xfs_dir2_db_to_da(args->geo, bno),
  326. -1, &bp, XFS_DATA_FORK);
  327. if (error)
  328. return error;
  329. xfs_dir3_leaf_init(mp, tp, bp, dp->i_ino, magic);
  330. xfs_dir3_leaf_log_header(args, bp);
  331. if (magic == XFS_DIR2_LEAF1_MAGIC)
  332. xfs_dir3_leaf_log_tail(args, bp);
  333. *bpp = bp;
  334. return 0;
  335. }
  336. /*
  337. * Convert a block form directory to a leaf form directory.
  338. */
  339. int /* error */
  340. xfs_dir2_block_to_leaf(
  341. xfs_da_args_t *args, /* operation arguments */
  342. struct xfs_buf *dbp) /* input block's buffer */
  343. {
  344. __be16 *bestsp; /* leaf's bestsp entries */
  345. xfs_dablk_t blkno; /* leaf block's bno */
  346. xfs_dir2_data_hdr_t *hdr; /* block header */
  347. xfs_dir2_leaf_entry_t *blp; /* block's leaf entries */
  348. xfs_dir2_block_tail_t *btp; /* block's tail */
  349. xfs_inode_t *dp; /* incore directory inode */
  350. int error; /* error return code */
  351. struct xfs_buf *lbp; /* leaf block's buffer */
  352. xfs_dir2_db_t ldb; /* leaf block's bno */
  353. xfs_dir2_leaf_t *leaf; /* leaf structure */
  354. xfs_dir2_leaf_tail_t *ltp; /* leaf's tail */
  355. int needlog; /* need to log block header */
  356. int needscan; /* need to rescan bestfree */
  357. xfs_trans_t *tp; /* transaction pointer */
  358. struct xfs_dir2_data_free *bf;
  359. struct xfs_dir2_leaf_entry *ents;
  360. struct xfs_dir3_icleaf_hdr leafhdr;
  361. trace_xfs_dir2_block_to_leaf(args);
  362. dp = args->dp;
  363. tp = args->trans;
  364. /*
  365. * Add the leaf block to the inode.
  366. * This interface will only put blocks in the leaf/node range.
  367. * Since that's empty now, we'll get the root (block 0 in range).
  368. */
  369. if ((error = xfs_da_grow_inode(args, &blkno))) {
  370. return error;
  371. }
  372. ldb = xfs_dir2_da_to_db(args->geo, blkno);
  373. ASSERT(ldb == xfs_dir2_byte_to_db(args->geo, XFS_DIR2_LEAF_OFFSET));
  374. /*
  375. * Initialize the leaf block, get a buffer for it.
  376. */
  377. error = xfs_dir3_leaf_get_buf(args, ldb, &lbp, XFS_DIR2_LEAF1_MAGIC);
  378. if (error)
  379. return error;
  380. leaf = lbp->b_addr;
  381. hdr = dbp->b_addr;
  382. xfs_dir3_data_check(dp, dbp);
  383. btp = xfs_dir2_block_tail_p(args->geo, hdr);
  384. blp = xfs_dir2_block_leaf_p(btp);
  385. bf = dp->d_ops->data_bestfree_p(hdr);
  386. ents = dp->d_ops->leaf_ents_p(leaf);
  387. /*
  388. * Set the counts in the leaf header.
  389. */
  390. dp->d_ops->leaf_hdr_from_disk(&leafhdr, leaf);
  391. leafhdr.count = be32_to_cpu(btp->count);
  392. leafhdr.stale = be32_to_cpu(btp->stale);
  393. dp->d_ops->leaf_hdr_to_disk(leaf, &leafhdr);
  394. xfs_dir3_leaf_log_header(args, lbp);
  395. /*
  396. * Could compact these but I think we always do the conversion
  397. * after squeezing out stale entries.
  398. */
  399. memcpy(ents, blp, be32_to_cpu(btp->count) * sizeof(xfs_dir2_leaf_entry_t));
  400. xfs_dir3_leaf_log_ents(args, lbp, 0, leafhdr.count - 1);
  401. needscan = 0;
  402. needlog = 1;
  403. /*
  404. * Make the space formerly occupied by the leaf entries and block
  405. * tail be free.
  406. */
  407. xfs_dir2_data_make_free(args, dbp,
  408. (xfs_dir2_data_aoff_t)((char *)blp - (char *)hdr),
  409. (xfs_dir2_data_aoff_t)((char *)hdr + args->geo->blksize -
  410. (char *)blp),
  411. &needlog, &needscan);
  412. /*
  413. * Fix up the block header, make it a data block.
  414. */
  415. dbp->b_ops = &xfs_dir3_data_buf_ops;
  416. xfs_trans_buf_set_type(tp, dbp, XFS_BLFT_DIR_DATA_BUF);
  417. if (hdr->magic == cpu_to_be32(XFS_DIR2_BLOCK_MAGIC))
  418. hdr->magic = cpu_to_be32(XFS_DIR2_DATA_MAGIC);
  419. else
  420. hdr->magic = cpu_to_be32(XFS_DIR3_DATA_MAGIC);
  421. if (needscan)
  422. xfs_dir2_data_freescan(dp, hdr, &needlog);
  423. /*
  424. * Set up leaf tail and bests table.
  425. */
  426. ltp = xfs_dir2_leaf_tail_p(args->geo, leaf);
  427. ltp->bestcount = cpu_to_be32(1);
  428. bestsp = xfs_dir2_leaf_bests_p(ltp);
  429. bestsp[0] = bf[0].length;
  430. /*
  431. * Log the data header and leaf bests table.
  432. */
  433. if (needlog)
  434. xfs_dir2_data_log_header(args, dbp);
  435. xfs_dir3_leaf_check(dp, lbp);
  436. xfs_dir3_data_check(dp, dbp);
  437. xfs_dir3_leaf_log_bests(args, lbp, 0, 0);
  438. return 0;
  439. }
  440. STATIC void
  441. xfs_dir3_leaf_find_stale(
  442. struct xfs_dir3_icleaf_hdr *leafhdr,
  443. struct xfs_dir2_leaf_entry *ents,
  444. int index,
  445. int *lowstale,
  446. int *highstale)
  447. {
  448. /*
  449. * Find the first stale entry before our index, if any.
  450. */
  451. for (*lowstale = index - 1; *lowstale >= 0; --*lowstale) {
  452. if (ents[*lowstale].address ==
  453. cpu_to_be32(XFS_DIR2_NULL_DATAPTR))
  454. break;
  455. }
  456. /*
  457. * Find the first stale entry at or after our index, if any.
  458. * Stop if the result would require moving more entries than using
  459. * lowstale.
  460. */
  461. for (*highstale = index; *highstale < leafhdr->count; ++*highstale) {
  462. if (ents[*highstale].address ==
  463. cpu_to_be32(XFS_DIR2_NULL_DATAPTR))
  464. break;
  465. if (*lowstale >= 0 && index - *lowstale <= *highstale - index)
  466. break;
  467. }
  468. }
  469. struct xfs_dir2_leaf_entry *
  470. xfs_dir3_leaf_find_entry(
  471. struct xfs_dir3_icleaf_hdr *leafhdr,
  472. struct xfs_dir2_leaf_entry *ents,
  473. int index, /* leaf table position */
  474. int compact, /* need to compact leaves */
  475. int lowstale, /* index of prev stale leaf */
  476. int highstale, /* index of next stale leaf */
  477. int *lfloglow, /* low leaf logging index */
  478. int *lfloghigh) /* high leaf logging index */
  479. {
  480. if (!leafhdr->stale) {
  481. xfs_dir2_leaf_entry_t *lep; /* leaf entry table pointer */
  482. /*
  483. * Now we need to make room to insert the leaf entry.
  484. *
  485. * If there are no stale entries, just insert a hole at index.
  486. */
  487. lep = &ents[index];
  488. if (index < leafhdr->count)
  489. memmove(lep + 1, lep,
  490. (leafhdr->count - index) * sizeof(*lep));
  491. /*
  492. * Record low and high logging indices for the leaf.
  493. */
  494. *lfloglow = index;
  495. *lfloghigh = leafhdr->count++;
  496. return lep;
  497. }
  498. /*
  499. * There are stale entries.
  500. *
  501. * We will use one of them for the new entry. It's probably not at
  502. * the right location, so we'll have to shift some up or down first.
  503. *
  504. * If we didn't compact before, we need to find the nearest stale
  505. * entries before and after our insertion point.
  506. */
  507. if (compact == 0)
  508. xfs_dir3_leaf_find_stale(leafhdr, ents, index,
  509. &lowstale, &highstale);
  510. /*
  511. * If the low one is better, use it.
  512. */
  513. if (lowstale >= 0 &&
  514. (highstale == leafhdr->count ||
  515. index - lowstale - 1 < highstale - index)) {
  516. ASSERT(index - lowstale - 1 >= 0);
  517. ASSERT(ents[lowstale].address ==
  518. cpu_to_be32(XFS_DIR2_NULL_DATAPTR));
  519. /*
  520. * Copy entries up to cover the stale entry and make room
  521. * for the new entry.
  522. */
  523. if (index - lowstale - 1 > 0) {
  524. memmove(&ents[lowstale], &ents[lowstale + 1],
  525. (index - lowstale - 1) *
  526. sizeof(xfs_dir2_leaf_entry_t));
  527. }
  528. *lfloglow = min(lowstale, *lfloglow);
  529. *lfloghigh = max(index - 1, *lfloghigh);
  530. leafhdr->stale--;
  531. return &ents[index - 1];
  532. }
  533. /*
  534. * The high one is better, so use that one.
  535. */
  536. ASSERT(highstale - index >= 0);
  537. ASSERT(ents[highstale].address == cpu_to_be32(XFS_DIR2_NULL_DATAPTR));
  538. /*
  539. * Copy entries down to cover the stale entry and make room for the
  540. * new entry.
  541. */
  542. if (highstale - index > 0) {
  543. memmove(&ents[index + 1], &ents[index],
  544. (highstale - index) * sizeof(xfs_dir2_leaf_entry_t));
  545. }
  546. *lfloglow = min(index, *lfloglow);
  547. *lfloghigh = max(highstale, *lfloghigh);
  548. leafhdr->stale--;
  549. return &ents[index];
  550. }
  551. /*
  552. * Add an entry to a leaf form directory.
  553. */
  554. int /* error */
  555. xfs_dir2_leaf_addname(
  556. xfs_da_args_t *args) /* operation arguments */
  557. {
  558. __be16 *bestsp; /* freespace table in leaf */
  559. int compact; /* need to compact leaves */
  560. xfs_dir2_data_hdr_t *hdr; /* data block header */
  561. struct xfs_buf *dbp; /* data block buffer */
  562. xfs_dir2_data_entry_t *dep; /* data block entry */
  563. xfs_inode_t *dp; /* incore directory inode */
  564. xfs_dir2_data_unused_t *dup; /* data unused entry */
  565. int error; /* error return value */
  566. int grown; /* allocated new data block */
  567. int highstale; /* index of next stale leaf */
  568. int i; /* temporary, index */
  569. int index; /* leaf table position */
  570. struct xfs_buf *lbp; /* leaf's buffer */
  571. xfs_dir2_leaf_t *leaf; /* leaf structure */
  572. int length; /* length of new entry */
  573. xfs_dir2_leaf_entry_t *lep; /* leaf entry table pointer */
  574. int lfloglow; /* low leaf logging index */
  575. int lfloghigh; /* high leaf logging index */
  576. int lowstale; /* index of prev stale leaf */
  577. xfs_dir2_leaf_tail_t *ltp; /* leaf tail pointer */
  578. int needbytes; /* leaf block bytes needed */
  579. int needlog; /* need to log data header */
  580. int needscan; /* need to rescan data free */
  581. __be16 *tagp; /* end of data entry */
  582. xfs_trans_t *tp; /* transaction pointer */
  583. xfs_dir2_db_t use_block; /* data block number */
  584. struct xfs_dir2_data_free *bf; /* bestfree table */
  585. struct xfs_dir2_leaf_entry *ents;
  586. struct xfs_dir3_icleaf_hdr leafhdr;
  587. trace_xfs_dir2_leaf_addname(args);
  588. dp = args->dp;
  589. tp = args->trans;
  590. error = xfs_dir3_leaf_read(tp, dp, args->geo->leafblk, -1, &lbp);
  591. if (error)
  592. return error;
  593. /*
  594. * Look up the entry by hash value and name.
  595. * We know it's not there, our caller has already done a lookup.
  596. * So the index is of the entry to insert in front of.
  597. * But if there are dup hash values the index is of the first of those.
  598. */
  599. index = xfs_dir2_leaf_search_hash(args, lbp);
  600. leaf = lbp->b_addr;
  601. ltp = xfs_dir2_leaf_tail_p(args->geo, leaf);
  602. ents = dp->d_ops->leaf_ents_p(leaf);
  603. dp->d_ops->leaf_hdr_from_disk(&leafhdr, leaf);
  604. bestsp = xfs_dir2_leaf_bests_p(ltp);
  605. length = dp->d_ops->data_entsize(args->namelen);
  606. /*
  607. * See if there are any entries with the same hash value
  608. * and space in their block for the new entry.
  609. * This is good because it puts multiple same-hash value entries
  610. * in a data block, improving the lookup of those entries.
  611. */
  612. for (use_block = -1, lep = &ents[index];
  613. index < leafhdr.count && be32_to_cpu(lep->hashval) == args->hashval;
  614. index++, lep++) {
  615. if (be32_to_cpu(lep->address) == XFS_DIR2_NULL_DATAPTR)
  616. continue;
  617. i = xfs_dir2_dataptr_to_db(args->geo, be32_to_cpu(lep->address));
  618. ASSERT(i < be32_to_cpu(ltp->bestcount));
  619. ASSERT(bestsp[i] != cpu_to_be16(NULLDATAOFF));
  620. if (be16_to_cpu(bestsp[i]) >= length) {
  621. use_block = i;
  622. break;
  623. }
  624. }
  625. /*
  626. * Didn't find a block yet, linear search all the data blocks.
  627. */
  628. if (use_block == -1) {
  629. for (i = 0; i < be32_to_cpu(ltp->bestcount); i++) {
  630. /*
  631. * Remember a block we see that's missing.
  632. */
  633. if (bestsp[i] == cpu_to_be16(NULLDATAOFF) &&
  634. use_block == -1)
  635. use_block = i;
  636. else if (be16_to_cpu(bestsp[i]) >= length) {
  637. use_block = i;
  638. break;
  639. }
  640. }
  641. }
  642. /*
  643. * How many bytes do we need in the leaf block?
  644. */
  645. needbytes = 0;
  646. if (!leafhdr.stale)
  647. needbytes += sizeof(xfs_dir2_leaf_entry_t);
  648. if (use_block == -1)
  649. needbytes += sizeof(xfs_dir2_data_off_t);
  650. /*
  651. * Now kill use_block if it refers to a missing block, so we
  652. * can use it as an indication of allocation needed.
  653. */
  654. if (use_block != -1 && bestsp[use_block] == cpu_to_be16(NULLDATAOFF))
  655. use_block = -1;
  656. /*
  657. * If we don't have enough free bytes but we can make enough
  658. * by compacting out stale entries, we'll do that.
  659. */
  660. if ((char *)bestsp - (char *)&ents[leafhdr.count] < needbytes &&
  661. leafhdr.stale > 1)
  662. compact = 1;
  663. /*
  664. * Otherwise if we don't have enough free bytes we need to
  665. * convert to node form.
  666. */
  667. else if ((char *)bestsp - (char *)&ents[leafhdr.count] < needbytes) {
  668. /*
  669. * Just checking or no space reservation, give up.
  670. */
  671. if ((args->op_flags & XFS_DA_OP_JUSTCHECK) ||
  672. args->total == 0) {
  673. xfs_trans_brelse(tp, lbp);
  674. return -ENOSPC;
  675. }
  676. /*
  677. * Convert to node form.
  678. */
  679. error = xfs_dir2_leaf_to_node(args, lbp);
  680. if (error)
  681. return error;
  682. /*
  683. * Then add the new entry.
  684. */
  685. return xfs_dir2_node_addname(args);
  686. }
  687. /*
  688. * Otherwise it will fit without compaction.
  689. */
  690. else
  691. compact = 0;
  692. /*
  693. * If just checking, then it will fit unless we needed to allocate
  694. * a new data block.
  695. */
  696. if (args->op_flags & XFS_DA_OP_JUSTCHECK) {
  697. xfs_trans_brelse(tp, lbp);
  698. return use_block == -1 ? -ENOSPC : 0;
  699. }
  700. /*
  701. * If no allocations are allowed, return now before we've
  702. * changed anything.
  703. */
  704. if (args->total == 0 && use_block == -1) {
  705. xfs_trans_brelse(tp, lbp);
  706. return -ENOSPC;
  707. }
  708. /*
  709. * Need to compact the leaf entries, removing stale ones.
  710. * Leave one stale entry behind - the one closest to our
  711. * insertion index - and we'll shift that one to our insertion
  712. * point later.
  713. */
  714. if (compact) {
  715. xfs_dir3_leaf_compact_x1(&leafhdr, ents, &index, &lowstale,
  716. &highstale, &lfloglow, &lfloghigh);
  717. }
  718. /*
  719. * There are stale entries, so we'll need log-low and log-high
  720. * impossibly bad values later.
  721. */
  722. else if (leafhdr.stale) {
  723. lfloglow = leafhdr.count;
  724. lfloghigh = -1;
  725. }
  726. /*
  727. * If there was no data block space found, we need to allocate
  728. * a new one.
  729. */
  730. if (use_block == -1) {
  731. /*
  732. * Add the new data block.
  733. */
  734. if ((error = xfs_dir2_grow_inode(args, XFS_DIR2_DATA_SPACE,
  735. &use_block))) {
  736. xfs_trans_brelse(tp, lbp);
  737. return error;
  738. }
  739. /*
  740. * Initialize the block.
  741. */
  742. if ((error = xfs_dir3_data_init(args, use_block, &dbp))) {
  743. xfs_trans_brelse(tp, lbp);
  744. return error;
  745. }
  746. /*
  747. * If we're adding a new data block on the end we need to
  748. * extend the bests table. Copy it up one entry.
  749. */
  750. if (use_block >= be32_to_cpu(ltp->bestcount)) {
  751. bestsp--;
  752. memmove(&bestsp[0], &bestsp[1],
  753. be32_to_cpu(ltp->bestcount) * sizeof(bestsp[0]));
  754. be32_add_cpu(&ltp->bestcount, 1);
  755. xfs_dir3_leaf_log_tail(args, lbp);
  756. xfs_dir3_leaf_log_bests(args, lbp, 0,
  757. be32_to_cpu(ltp->bestcount) - 1);
  758. }
  759. /*
  760. * If we're filling in a previously empty block just log it.
  761. */
  762. else
  763. xfs_dir3_leaf_log_bests(args, lbp, use_block, use_block);
  764. hdr = dbp->b_addr;
  765. bf = dp->d_ops->data_bestfree_p(hdr);
  766. bestsp[use_block] = bf[0].length;
  767. grown = 1;
  768. } else {
  769. /*
  770. * Already had space in some data block.
  771. * Just read that one in.
  772. */
  773. error = xfs_dir3_data_read(tp, dp,
  774. xfs_dir2_db_to_da(args->geo, use_block),
  775. -1, &dbp);
  776. if (error) {
  777. xfs_trans_brelse(tp, lbp);
  778. return error;
  779. }
  780. hdr = dbp->b_addr;
  781. bf = dp->d_ops->data_bestfree_p(hdr);
  782. grown = 0;
  783. }
  784. /*
  785. * Point to the biggest freespace in our data block.
  786. */
  787. dup = (xfs_dir2_data_unused_t *)
  788. ((char *)hdr + be16_to_cpu(bf[0].offset));
  789. needscan = needlog = 0;
  790. /*
  791. * Mark the initial part of our freespace in use for the new entry.
  792. */
  793. error = xfs_dir2_data_use_free(args, dbp, dup,
  794. (xfs_dir2_data_aoff_t)((char *)dup - (char *)hdr),
  795. length, &needlog, &needscan);
  796. if (error) {
  797. xfs_trans_brelse(tp, lbp);
  798. return error;
  799. }
  800. /*
  801. * Initialize our new entry (at last).
  802. */
  803. dep = (xfs_dir2_data_entry_t *)dup;
  804. dep->inumber = cpu_to_be64(args->inumber);
  805. dep->namelen = args->namelen;
  806. memcpy(dep->name, args->name, dep->namelen);
  807. dp->d_ops->data_put_ftype(dep, args->filetype);
  808. tagp = dp->d_ops->data_entry_tag_p(dep);
  809. *tagp = cpu_to_be16((char *)dep - (char *)hdr);
  810. /*
  811. * Need to scan fix up the bestfree table.
  812. */
  813. if (needscan)
  814. xfs_dir2_data_freescan(dp, hdr, &needlog);
  815. /*
  816. * Need to log the data block's header.
  817. */
  818. if (needlog)
  819. xfs_dir2_data_log_header(args, dbp);
  820. xfs_dir2_data_log_entry(args, dbp, dep);
  821. /*
  822. * If the bests table needs to be changed, do it.
  823. * Log the change unless we've already done that.
  824. */
  825. if (be16_to_cpu(bestsp[use_block]) != be16_to_cpu(bf[0].length)) {
  826. bestsp[use_block] = bf[0].length;
  827. if (!grown)
  828. xfs_dir3_leaf_log_bests(args, lbp, use_block, use_block);
  829. }
  830. lep = xfs_dir3_leaf_find_entry(&leafhdr, ents, index, compact, lowstale,
  831. highstale, &lfloglow, &lfloghigh);
  832. /*
  833. * Fill in the new leaf entry.
  834. */
  835. lep->hashval = cpu_to_be32(args->hashval);
  836. lep->address = cpu_to_be32(
  837. xfs_dir2_db_off_to_dataptr(args->geo, use_block,
  838. be16_to_cpu(*tagp)));
  839. /*
  840. * Log the leaf fields and give up the buffers.
  841. */
  842. dp->d_ops->leaf_hdr_to_disk(leaf, &leafhdr);
  843. xfs_dir3_leaf_log_header(args, lbp);
  844. xfs_dir3_leaf_log_ents(args, lbp, lfloglow, lfloghigh);
  845. xfs_dir3_leaf_check(dp, lbp);
  846. xfs_dir3_data_check(dp, dbp);
  847. return 0;
  848. }
  849. /*
  850. * Compact out any stale entries in the leaf.
  851. * Log the header and changed leaf entries, if any.
  852. */
  853. void
  854. xfs_dir3_leaf_compact(
  855. xfs_da_args_t *args, /* operation arguments */
  856. struct xfs_dir3_icleaf_hdr *leafhdr,
  857. struct xfs_buf *bp) /* leaf buffer */
  858. {
  859. int from; /* source leaf index */
  860. xfs_dir2_leaf_t *leaf; /* leaf structure */
  861. int loglow; /* first leaf entry to log */
  862. int to; /* target leaf index */
  863. struct xfs_dir2_leaf_entry *ents;
  864. struct xfs_inode *dp = args->dp;
  865. leaf = bp->b_addr;
  866. if (!leafhdr->stale)
  867. return;
  868. /*
  869. * Compress out the stale entries in place.
  870. */
  871. ents = dp->d_ops->leaf_ents_p(leaf);
  872. for (from = to = 0, loglow = -1; from < leafhdr->count; from++) {
  873. if (ents[from].address == cpu_to_be32(XFS_DIR2_NULL_DATAPTR))
  874. continue;
  875. /*
  876. * Only actually copy the entries that are different.
  877. */
  878. if (from > to) {
  879. if (loglow == -1)
  880. loglow = to;
  881. ents[to] = ents[from];
  882. }
  883. to++;
  884. }
  885. /*
  886. * Update and log the header, log the leaf entries.
  887. */
  888. ASSERT(leafhdr->stale == from - to);
  889. leafhdr->count -= leafhdr->stale;
  890. leafhdr->stale = 0;
  891. dp->d_ops->leaf_hdr_to_disk(leaf, leafhdr);
  892. xfs_dir3_leaf_log_header(args, bp);
  893. if (loglow != -1)
  894. xfs_dir3_leaf_log_ents(args, bp, loglow, to - 1);
  895. }
  896. /*
  897. * Compact the leaf entries, removing stale ones.
  898. * Leave one stale entry behind - the one closest to our
  899. * insertion index - and the caller will shift that one to our insertion
  900. * point later.
  901. * Return new insertion index, where the remaining stale entry is,
  902. * and leaf logging indices.
  903. */
  904. void
  905. xfs_dir3_leaf_compact_x1(
  906. struct xfs_dir3_icleaf_hdr *leafhdr,
  907. struct xfs_dir2_leaf_entry *ents,
  908. int *indexp, /* insertion index */
  909. int *lowstalep, /* out: stale entry before us */
  910. int *highstalep, /* out: stale entry after us */
  911. int *lowlogp, /* out: low log index */
  912. int *highlogp) /* out: high log index */
  913. {
  914. int from; /* source copy index */
  915. int highstale; /* stale entry at/after index */
  916. int index; /* insertion index */
  917. int keepstale; /* source index of kept stale */
  918. int lowstale; /* stale entry before index */
  919. int newindex=0; /* new insertion index */
  920. int to; /* destination copy index */
  921. ASSERT(leafhdr->stale > 1);
  922. index = *indexp;
  923. xfs_dir3_leaf_find_stale(leafhdr, ents, index, &lowstale, &highstale);
  924. /*
  925. * Pick the better of lowstale and highstale.
  926. */
  927. if (lowstale >= 0 &&
  928. (highstale == leafhdr->count ||
  929. index - lowstale <= highstale - index))
  930. keepstale = lowstale;
  931. else
  932. keepstale = highstale;
  933. /*
  934. * Copy the entries in place, removing all the stale entries
  935. * except keepstale.
  936. */
  937. for (from = to = 0; from < leafhdr->count; from++) {
  938. /*
  939. * Notice the new value of index.
  940. */
  941. if (index == from)
  942. newindex = to;
  943. if (from != keepstale &&
  944. ents[from].address == cpu_to_be32(XFS_DIR2_NULL_DATAPTR)) {
  945. if (from == to)
  946. *lowlogp = to;
  947. continue;
  948. }
  949. /*
  950. * Record the new keepstale value for the insertion.
  951. */
  952. if (from == keepstale)
  953. lowstale = highstale = to;
  954. /*
  955. * Copy only the entries that have moved.
  956. */
  957. if (from > to)
  958. ents[to] = ents[from];
  959. to++;
  960. }
  961. ASSERT(from > to);
  962. /*
  963. * If the insertion point was past the last entry,
  964. * set the new insertion point accordingly.
  965. */
  966. if (index == from)
  967. newindex = to;
  968. *indexp = newindex;
  969. /*
  970. * Adjust the leaf header values.
  971. */
  972. leafhdr->count -= from - to;
  973. leafhdr->stale = 1;
  974. /*
  975. * Remember the low/high stale value only in the "right"
  976. * direction.
  977. */
  978. if (lowstale >= newindex)
  979. lowstale = -1;
  980. else
  981. highstale = leafhdr->count;
  982. *highlogp = leafhdr->count - 1;
  983. *lowstalep = lowstale;
  984. *highstalep = highstale;
  985. }
  986. /*
  987. * Log the bests entries indicated from a leaf1 block.
  988. */
  989. static void
  990. xfs_dir3_leaf_log_bests(
  991. struct xfs_da_args *args,
  992. struct xfs_buf *bp, /* leaf buffer */
  993. int first, /* first entry to log */
  994. int last) /* last entry to log */
  995. {
  996. __be16 *firstb; /* pointer to first entry */
  997. __be16 *lastb; /* pointer to last entry */
  998. struct xfs_dir2_leaf *leaf = bp->b_addr;
  999. xfs_dir2_leaf_tail_t *ltp; /* leaf tail structure */
  1000. ASSERT(leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAF1_MAGIC) ||
  1001. leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAF1_MAGIC));
  1002. ltp = xfs_dir2_leaf_tail_p(args->geo, leaf);
  1003. firstb = xfs_dir2_leaf_bests_p(ltp) + first;
  1004. lastb = xfs_dir2_leaf_bests_p(ltp) + last;
  1005. xfs_trans_log_buf(args->trans, bp,
  1006. (uint)((char *)firstb - (char *)leaf),
  1007. (uint)((char *)lastb - (char *)leaf + sizeof(*lastb) - 1));
  1008. }
  1009. /*
  1010. * Log the leaf entries indicated from a leaf1 or leafn block.
  1011. */
  1012. void
  1013. xfs_dir3_leaf_log_ents(
  1014. struct xfs_da_args *args,
  1015. struct xfs_buf *bp,
  1016. int first,
  1017. int last)
  1018. {
  1019. xfs_dir2_leaf_entry_t *firstlep; /* pointer to first entry */
  1020. xfs_dir2_leaf_entry_t *lastlep; /* pointer to last entry */
  1021. struct xfs_dir2_leaf *leaf = bp->b_addr;
  1022. struct xfs_dir2_leaf_entry *ents;
  1023. ASSERT(leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAF1_MAGIC) ||
  1024. leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAF1_MAGIC) ||
  1025. leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) ||
  1026. leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC));
  1027. ents = args->dp->d_ops->leaf_ents_p(leaf);
  1028. firstlep = &ents[first];
  1029. lastlep = &ents[last];
  1030. xfs_trans_log_buf(args->trans, bp,
  1031. (uint)((char *)firstlep - (char *)leaf),
  1032. (uint)((char *)lastlep - (char *)leaf + sizeof(*lastlep) - 1));
  1033. }
  1034. /*
  1035. * Log the header of the leaf1 or leafn block.
  1036. */
  1037. void
  1038. xfs_dir3_leaf_log_header(
  1039. struct xfs_da_args *args,
  1040. struct xfs_buf *bp)
  1041. {
  1042. struct xfs_dir2_leaf *leaf = bp->b_addr;
  1043. ASSERT(leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAF1_MAGIC) ||
  1044. leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAF1_MAGIC) ||
  1045. leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) ||
  1046. leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC));
  1047. xfs_trans_log_buf(args->trans, bp,
  1048. (uint)((char *)&leaf->hdr - (char *)leaf),
  1049. args->dp->d_ops->leaf_hdr_size - 1);
  1050. }
  1051. /*
  1052. * Log the tail of the leaf1 block.
  1053. */
  1054. STATIC void
  1055. xfs_dir3_leaf_log_tail(
  1056. struct xfs_da_args *args,
  1057. struct xfs_buf *bp)
  1058. {
  1059. struct xfs_dir2_leaf *leaf = bp->b_addr;
  1060. xfs_dir2_leaf_tail_t *ltp; /* leaf tail structure */
  1061. ASSERT(leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAF1_MAGIC) ||
  1062. leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAF1_MAGIC) ||
  1063. leaf->hdr.info.magic == cpu_to_be16(XFS_DIR2_LEAFN_MAGIC) ||
  1064. leaf->hdr.info.magic == cpu_to_be16(XFS_DIR3_LEAFN_MAGIC));
  1065. ltp = xfs_dir2_leaf_tail_p(args->geo, leaf);
  1066. xfs_trans_log_buf(args->trans, bp, (uint)((char *)ltp - (char *)leaf),
  1067. (uint)(args->geo->blksize - 1));
  1068. }
  1069. /*
  1070. * Look up the entry referred to by args in the leaf format directory.
  1071. * Most of the work is done by the xfs_dir2_leaf_lookup_int routine which
  1072. * is also used by the node-format code.
  1073. */
  1074. int
  1075. xfs_dir2_leaf_lookup(
  1076. xfs_da_args_t *args) /* operation arguments */
  1077. {
  1078. struct xfs_buf *dbp; /* data block buffer */
  1079. xfs_dir2_data_entry_t *dep; /* data block entry */
  1080. xfs_inode_t *dp; /* incore directory inode */
  1081. int error; /* error return code */
  1082. int index; /* found entry index */
  1083. struct xfs_buf *lbp; /* leaf buffer */
  1084. xfs_dir2_leaf_t *leaf; /* leaf structure */
  1085. xfs_dir2_leaf_entry_t *lep; /* leaf entry */
  1086. xfs_trans_t *tp; /* transaction pointer */
  1087. struct xfs_dir2_leaf_entry *ents;
  1088. trace_xfs_dir2_leaf_lookup(args);
  1089. /*
  1090. * Look up name in the leaf block, returning both buffers and index.
  1091. */
  1092. if ((error = xfs_dir2_leaf_lookup_int(args, &lbp, &index, &dbp))) {
  1093. return error;
  1094. }
  1095. tp = args->trans;
  1096. dp = args->dp;
  1097. xfs_dir3_leaf_check(dp, lbp);
  1098. leaf = lbp->b_addr;
  1099. ents = dp->d_ops->leaf_ents_p(leaf);
  1100. /*
  1101. * Get to the leaf entry and contained data entry address.
  1102. */
  1103. lep = &ents[index];
  1104. /*
  1105. * Point to the data entry.
  1106. */
  1107. dep = (xfs_dir2_data_entry_t *)
  1108. ((char *)dbp->b_addr +
  1109. xfs_dir2_dataptr_to_off(args->geo, be32_to_cpu(lep->address)));
  1110. /*
  1111. * Return the found inode number & CI name if appropriate
  1112. */
  1113. args->inumber = be64_to_cpu(dep->inumber);
  1114. args->filetype = dp->d_ops->data_get_ftype(dep);
  1115. error = xfs_dir_cilookup_result(args, dep->name, dep->namelen);
  1116. xfs_trans_brelse(tp, dbp);
  1117. xfs_trans_brelse(tp, lbp);
  1118. return error;
  1119. }
  1120. /*
  1121. * Look up name/hash in the leaf block.
  1122. * Fill in indexp with the found index, and dbpp with the data buffer.
  1123. * If not found dbpp will be NULL, and ENOENT comes back.
  1124. * lbpp will always be filled in with the leaf buffer unless there's an error.
  1125. */
  1126. static int /* error */
  1127. xfs_dir2_leaf_lookup_int(
  1128. xfs_da_args_t *args, /* operation arguments */
  1129. struct xfs_buf **lbpp, /* out: leaf buffer */
  1130. int *indexp, /* out: index in leaf block */
  1131. struct xfs_buf **dbpp) /* out: data buffer */
  1132. {
  1133. xfs_dir2_db_t curdb = -1; /* current data block number */
  1134. struct xfs_buf *dbp = NULL; /* data buffer */
  1135. xfs_dir2_data_entry_t *dep; /* data entry */
  1136. xfs_inode_t *dp; /* incore directory inode */
  1137. int error; /* error return code */
  1138. int index; /* index in leaf block */
  1139. struct xfs_buf *lbp; /* leaf buffer */
  1140. xfs_dir2_leaf_entry_t *lep; /* leaf entry */
  1141. xfs_dir2_leaf_t *leaf; /* leaf structure */
  1142. xfs_mount_t *mp; /* filesystem mount point */
  1143. xfs_dir2_db_t newdb; /* new data block number */
  1144. xfs_trans_t *tp; /* transaction pointer */
  1145. xfs_dir2_db_t cidb = -1; /* case match data block no. */
  1146. enum xfs_dacmp cmp; /* name compare result */
  1147. struct xfs_dir2_leaf_entry *ents;
  1148. struct xfs_dir3_icleaf_hdr leafhdr;
  1149. dp = args->dp;
  1150. tp = args->trans;
  1151. mp = dp->i_mount;
  1152. error = xfs_dir3_leaf_read(tp, dp, args->geo->leafblk, -1, &lbp);
  1153. if (error)
  1154. return error;
  1155. *lbpp = lbp;
  1156. leaf = lbp->b_addr;
  1157. xfs_dir3_leaf_check(dp, lbp);
  1158. ents = dp->d_ops->leaf_ents_p(leaf);
  1159. dp->d_ops->leaf_hdr_from_disk(&leafhdr, leaf);
  1160. /*
  1161. * Look for the first leaf entry with our hash value.
  1162. */
  1163. index = xfs_dir2_leaf_search_hash(args, lbp);
  1164. /*
  1165. * Loop over all the entries with the right hash value
  1166. * looking to match the name.
  1167. */
  1168. for (lep = &ents[index];
  1169. index < leafhdr.count && be32_to_cpu(lep->hashval) == args->hashval;
  1170. lep++, index++) {
  1171. /*
  1172. * Skip over stale leaf entries.
  1173. */
  1174. if (be32_to_cpu(lep->address) == XFS_DIR2_NULL_DATAPTR)
  1175. continue;
  1176. /*
  1177. * Get the new data block number.
  1178. */
  1179. newdb = xfs_dir2_dataptr_to_db(args->geo,
  1180. be32_to_cpu(lep->address));
  1181. /*
  1182. * If it's not the same as the old data block number,
  1183. * need to pitch the old one and read the new one.
  1184. */
  1185. if (newdb != curdb) {
  1186. if (dbp)
  1187. xfs_trans_brelse(tp, dbp);
  1188. error = xfs_dir3_data_read(tp, dp,
  1189. xfs_dir2_db_to_da(args->geo, newdb),
  1190. -1, &dbp);
  1191. if (error) {
  1192. xfs_trans_brelse(tp, lbp);
  1193. return error;
  1194. }
  1195. curdb = newdb;
  1196. }
  1197. /*
  1198. * Point to the data entry.
  1199. */
  1200. dep = (xfs_dir2_data_entry_t *)((char *)dbp->b_addr +
  1201. xfs_dir2_dataptr_to_off(args->geo,
  1202. be32_to_cpu(lep->address)));
  1203. /*
  1204. * Compare name and if it's an exact match, return the index
  1205. * and buffer. If it's the first case-insensitive match, store
  1206. * the index and buffer and continue looking for an exact match.
  1207. */
  1208. cmp = mp->m_dirnameops->compname(args, dep->name, dep->namelen);
  1209. if (cmp != XFS_CMP_DIFFERENT && cmp != args->cmpresult) {
  1210. args->cmpresult = cmp;
  1211. *indexp = index;
  1212. /* case exact match: return the current buffer. */
  1213. if (cmp == XFS_CMP_EXACT) {
  1214. *dbpp = dbp;
  1215. return 0;
  1216. }
  1217. cidb = curdb;
  1218. }
  1219. }
  1220. ASSERT(args->op_flags & XFS_DA_OP_OKNOENT);
  1221. /*
  1222. * Here, we can only be doing a lookup (not a rename or remove).
  1223. * If a case-insensitive match was found earlier, re-read the
  1224. * appropriate data block if required and return it.
  1225. */
  1226. if (args->cmpresult == XFS_CMP_CASE) {
  1227. ASSERT(cidb != -1);
  1228. if (cidb != curdb) {
  1229. xfs_trans_brelse(tp, dbp);
  1230. error = xfs_dir3_data_read(tp, dp,
  1231. xfs_dir2_db_to_da(args->geo, cidb),
  1232. -1, &dbp);
  1233. if (error) {
  1234. xfs_trans_brelse(tp, lbp);
  1235. return error;
  1236. }
  1237. }
  1238. *dbpp = dbp;
  1239. return 0;
  1240. }
  1241. /*
  1242. * No match found, return -ENOENT.
  1243. */
  1244. ASSERT(cidb == -1);
  1245. if (dbp)
  1246. xfs_trans_brelse(tp, dbp);
  1247. xfs_trans_brelse(tp, lbp);
  1248. return -ENOENT;
  1249. }
  1250. /*
  1251. * Remove an entry from a leaf format directory.
  1252. */
  1253. int /* error */
  1254. xfs_dir2_leaf_removename(
  1255. xfs_da_args_t *args) /* operation arguments */
  1256. {
  1257. __be16 *bestsp; /* leaf block best freespace */
  1258. xfs_dir2_data_hdr_t *hdr; /* data block header */
  1259. xfs_dir2_db_t db; /* data block number */
  1260. struct xfs_buf *dbp; /* data block buffer */
  1261. xfs_dir2_data_entry_t *dep; /* data entry structure */
  1262. xfs_inode_t *dp; /* incore directory inode */
  1263. int error; /* error return code */
  1264. xfs_dir2_db_t i; /* temporary data block # */
  1265. int index; /* index into leaf entries */
  1266. struct xfs_buf *lbp; /* leaf buffer */
  1267. xfs_dir2_leaf_t *leaf; /* leaf structure */
  1268. xfs_dir2_leaf_entry_t *lep; /* leaf entry */
  1269. xfs_dir2_leaf_tail_t *ltp; /* leaf tail structure */
  1270. int needlog; /* need to log data header */
  1271. int needscan; /* need to rescan data frees */
  1272. xfs_dir2_data_off_t oldbest; /* old value of best free */
  1273. struct xfs_dir2_data_free *bf; /* bestfree table */
  1274. struct xfs_dir2_leaf_entry *ents;
  1275. struct xfs_dir3_icleaf_hdr leafhdr;
  1276. trace_xfs_dir2_leaf_removename(args);
  1277. /*
  1278. * Lookup the leaf entry, get the leaf and data blocks read in.
  1279. */
  1280. if ((error = xfs_dir2_leaf_lookup_int(args, &lbp, &index, &dbp))) {
  1281. return error;
  1282. }
  1283. dp = args->dp;
  1284. leaf = lbp->b_addr;
  1285. hdr = dbp->b_addr;
  1286. xfs_dir3_data_check(dp, dbp);
  1287. bf = dp->d_ops->data_bestfree_p(hdr);
  1288. dp->d_ops->leaf_hdr_from_disk(&leafhdr, leaf);
  1289. ents = dp->d_ops->leaf_ents_p(leaf);
  1290. /*
  1291. * Point to the leaf entry, use that to point to the data entry.
  1292. */
  1293. lep = &ents[index];
  1294. db = xfs_dir2_dataptr_to_db(args->geo, be32_to_cpu(lep->address));
  1295. dep = (xfs_dir2_data_entry_t *)((char *)hdr +
  1296. xfs_dir2_dataptr_to_off(args->geo, be32_to_cpu(lep->address)));
  1297. needscan = needlog = 0;
  1298. oldbest = be16_to_cpu(bf[0].length);
  1299. ltp = xfs_dir2_leaf_tail_p(args->geo, leaf);
  1300. bestsp = xfs_dir2_leaf_bests_p(ltp);
  1301. if (be16_to_cpu(bestsp[db]) != oldbest)
  1302. return -EFSCORRUPTED;
  1303. /*
  1304. * Mark the former data entry unused.
  1305. */
  1306. xfs_dir2_data_make_free(args, dbp,
  1307. (xfs_dir2_data_aoff_t)((char *)dep - (char *)hdr),
  1308. dp->d_ops->data_entsize(dep->namelen), &needlog, &needscan);
  1309. /*
  1310. * We just mark the leaf entry stale by putting a null in it.
  1311. */
  1312. leafhdr.stale++;
  1313. dp->d_ops->leaf_hdr_to_disk(leaf, &leafhdr);
  1314. xfs_dir3_leaf_log_header(args, lbp);
  1315. lep->address = cpu_to_be32(XFS_DIR2_NULL_DATAPTR);
  1316. xfs_dir3_leaf_log_ents(args, lbp, index, index);
  1317. /*
  1318. * Scan the freespace in the data block again if necessary,
  1319. * log the data block header if necessary.
  1320. */
  1321. if (needscan)
  1322. xfs_dir2_data_freescan(dp, hdr, &needlog);
  1323. if (needlog)
  1324. xfs_dir2_data_log_header(args, dbp);
  1325. /*
  1326. * If the longest freespace in the data block has changed,
  1327. * put the new value in the bests table and log that.
  1328. */
  1329. if (be16_to_cpu(bf[0].length) != oldbest) {
  1330. bestsp[db] = bf[0].length;
  1331. xfs_dir3_leaf_log_bests(args, lbp, db, db);
  1332. }
  1333. xfs_dir3_data_check(dp, dbp);
  1334. /*
  1335. * If the data block is now empty then get rid of the data block.
  1336. */
  1337. if (be16_to_cpu(bf[0].length) ==
  1338. args->geo->blksize - dp->d_ops->data_entry_offset) {
  1339. ASSERT(db != args->geo->datablk);
  1340. if ((error = xfs_dir2_shrink_inode(args, db, dbp))) {
  1341. /*
  1342. * Nope, can't get rid of it because it caused
  1343. * allocation of a bmap btree block to do so.
  1344. * Just go on, returning success, leaving the
  1345. * empty block in place.
  1346. */
  1347. if (error == -ENOSPC && args->total == 0)
  1348. error = 0;
  1349. xfs_dir3_leaf_check(dp, lbp);
  1350. return error;
  1351. }
  1352. dbp = NULL;
  1353. /*
  1354. * If this is the last data block then compact the
  1355. * bests table by getting rid of entries.
  1356. */
  1357. if (db == be32_to_cpu(ltp->bestcount) - 1) {
  1358. /*
  1359. * Look for the last active entry (i).
  1360. */
  1361. for (i = db - 1; i > 0; i--) {
  1362. if (bestsp[i] != cpu_to_be16(NULLDATAOFF))
  1363. break;
  1364. }
  1365. /*
  1366. * Copy the table down so inactive entries at the
  1367. * end are removed.
  1368. */
  1369. memmove(&bestsp[db - i], bestsp,
  1370. (be32_to_cpu(ltp->bestcount) - (db - i)) * sizeof(*bestsp));
  1371. be32_add_cpu(&ltp->bestcount, -(db - i));
  1372. xfs_dir3_leaf_log_tail(args, lbp);
  1373. xfs_dir3_leaf_log_bests(args, lbp, 0,
  1374. be32_to_cpu(ltp->bestcount) - 1);
  1375. } else
  1376. bestsp[db] = cpu_to_be16(NULLDATAOFF);
  1377. }
  1378. /*
  1379. * If the data block was not the first one, drop it.
  1380. */
  1381. else if (db != args->geo->datablk)
  1382. dbp = NULL;
  1383. xfs_dir3_leaf_check(dp, lbp);
  1384. /*
  1385. * See if we can convert to block form.
  1386. */
  1387. return xfs_dir2_leaf_to_block(args, lbp, dbp);
  1388. }
  1389. /*
  1390. * Replace the inode number in a leaf format directory entry.
  1391. */
  1392. int /* error */
  1393. xfs_dir2_leaf_replace(
  1394. xfs_da_args_t *args) /* operation arguments */
  1395. {
  1396. struct xfs_buf *dbp; /* data block buffer */
  1397. xfs_dir2_data_entry_t *dep; /* data block entry */
  1398. xfs_inode_t *dp; /* incore directory inode */
  1399. int error; /* error return code */
  1400. int index; /* index of leaf entry */
  1401. struct xfs_buf *lbp; /* leaf buffer */
  1402. xfs_dir2_leaf_t *leaf; /* leaf structure */
  1403. xfs_dir2_leaf_entry_t *lep; /* leaf entry */
  1404. xfs_trans_t *tp; /* transaction pointer */
  1405. struct xfs_dir2_leaf_entry *ents;
  1406. trace_xfs_dir2_leaf_replace(args);
  1407. /*
  1408. * Look up the entry.
  1409. */
  1410. if ((error = xfs_dir2_leaf_lookup_int(args, &lbp, &index, &dbp))) {
  1411. return error;
  1412. }
  1413. dp = args->dp;
  1414. leaf = lbp->b_addr;
  1415. ents = dp->d_ops->leaf_ents_p(leaf);
  1416. /*
  1417. * Point to the leaf entry, get data address from it.
  1418. */
  1419. lep = &ents[index];
  1420. /*
  1421. * Point to the data entry.
  1422. */
  1423. dep = (xfs_dir2_data_entry_t *)
  1424. ((char *)dbp->b_addr +
  1425. xfs_dir2_dataptr_to_off(args->geo, be32_to_cpu(lep->address)));
  1426. ASSERT(args->inumber != be64_to_cpu(dep->inumber));
  1427. /*
  1428. * Put the new inode number in, log it.
  1429. */
  1430. dep->inumber = cpu_to_be64(args->inumber);
  1431. dp->d_ops->data_put_ftype(dep, args->filetype);
  1432. tp = args->trans;
  1433. xfs_dir2_data_log_entry(args, dbp, dep);
  1434. xfs_dir3_leaf_check(dp, lbp);
  1435. xfs_trans_brelse(tp, lbp);
  1436. return 0;
  1437. }
  1438. /*
  1439. * Return index in the leaf block (lbp) which is either the first
  1440. * one with this hash value, or if there are none, the insert point
  1441. * for that hash value.
  1442. */
  1443. int /* index value */
  1444. xfs_dir2_leaf_search_hash(
  1445. xfs_da_args_t *args, /* operation arguments */
  1446. struct xfs_buf *lbp) /* leaf buffer */
  1447. {
  1448. xfs_dahash_t hash=0; /* hash from this entry */
  1449. xfs_dahash_t hashwant; /* hash value looking for */
  1450. int high; /* high leaf index */
  1451. int low; /* low leaf index */
  1452. xfs_dir2_leaf_t *leaf; /* leaf structure */
  1453. xfs_dir2_leaf_entry_t *lep; /* leaf entry */
  1454. int mid=0; /* current leaf index */
  1455. struct xfs_dir2_leaf_entry *ents;
  1456. struct xfs_dir3_icleaf_hdr leafhdr;
  1457. leaf = lbp->b_addr;
  1458. ents = args->dp->d_ops->leaf_ents_p(leaf);
  1459. args->dp->d_ops->leaf_hdr_from_disk(&leafhdr, leaf);
  1460. /*
  1461. * Note, the table cannot be empty, so we have to go through the loop.
  1462. * Binary search the leaf entries looking for our hash value.
  1463. */
  1464. for (lep = ents, low = 0, high = leafhdr.count - 1,
  1465. hashwant = args->hashval;
  1466. low <= high; ) {
  1467. mid = (low + high) >> 1;
  1468. if ((hash = be32_to_cpu(lep[mid].hashval)) == hashwant)
  1469. break;
  1470. if (hash < hashwant)
  1471. low = mid + 1;
  1472. else
  1473. high = mid - 1;
  1474. }
  1475. /*
  1476. * Found one, back up through all the equal hash values.
  1477. */
  1478. if (hash == hashwant) {
  1479. while (mid > 0 && be32_to_cpu(lep[mid - 1].hashval) == hashwant) {
  1480. mid--;
  1481. }
  1482. }
  1483. /*
  1484. * Need to point to an entry higher than ours.
  1485. */
  1486. else if (hash < hashwant)
  1487. mid++;
  1488. return mid;
  1489. }
  1490. /*
  1491. * Trim off a trailing data block. We know it's empty since the leaf
  1492. * freespace table says so.
  1493. */
  1494. int /* error */
  1495. xfs_dir2_leaf_trim_data(
  1496. xfs_da_args_t *args, /* operation arguments */
  1497. struct xfs_buf *lbp, /* leaf buffer */
  1498. xfs_dir2_db_t db) /* data block number */
  1499. {
  1500. __be16 *bestsp; /* leaf bests table */
  1501. struct xfs_buf *dbp; /* data block buffer */
  1502. xfs_inode_t *dp; /* incore directory inode */
  1503. int error; /* error return value */
  1504. xfs_dir2_leaf_t *leaf; /* leaf structure */
  1505. xfs_dir2_leaf_tail_t *ltp; /* leaf tail structure */
  1506. xfs_trans_t *tp; /* transaction pointer */
  1507. dp = args->dp;
  1508. tp = args->trans;
  1509. /*
  1510. * Read the offending data block. We need its buffer.
  1511. */
  1512. error = xfs_dir3_data_read(tp, dp, xfs_dir2_db_to_da(args->geo, db),
  1513. -1, &dbp);
  1514. if (error)
  1515. return error;
  1516. leaf = lbp->b_addr;
  1517. ltp = xfs_dir2_leaf_tail_p(args->geo, leaf);
  1518. #ifdef DEBUG
  1519. {
  1520. struct xfs_dir2_data_hdr *hdr = dbp->b_addr;
  1521. struct xfs_dir2_data_free *bf = dp->d_ops->data_bestfree_p(hdr);
  1522. ASSERT(hdr->magic == cpu_to_be32(XFS_DIR2_DATA_MAGIC) ||
  1523. hdr->magic == cpu_to_be32(XFS_DIR3_DATA_MAGIC));
  1524. ASSERT(be16_to_cpu(bf[0].length) ==
  1525. args->geo->blksize - dp->d_ops->data_entry_offset);
  1526. ASSERT(db == be32_to_cpu(ltp->bestcount) - 1);
  1527. }
  1528. #endif
  1529. /*
  1530. * Get rid of the data block.
  1531. */
  1532. if ((error = xfs_dir2_shrink_inode(args, db, dbp))) {
  1533. ASSERT(error != -ENOSPC);
  1534. xfs_trans_brelse(tp, dbp);
  1535. return error;
  1536. }
  1537. /*
  1538. * Eliminate the last bests entry from the table.
  1539. */
  1540. bestsp = xfs_dir2_leaf_bests_p(ltp);
  1541. be32_add_cpu(&ltp->bestcount, -1);
  1542. memmove(&bestsp[1], &bestsp[0], be32_to_cpu(ltp->bestcount) * sizeof(*bestsp));
  1543. xfs_dir3_leaf_log_tail(args, lbp);
  1544. xfs_dir3_leaf_log_bests(args, lbp, 0, be32_to_cpu(ltp->bestcount) - 1);
  1545. return 0;
  1546. }
  1547. static inline size_t
  1548. xfs_dir3_leaf_size(
  1549. struct xfs_dir3_icleaf_hdr *hdr,
  1550. int counts)
  1551. {
  1552. int entries;
  1553. int hdrsize;
  1554. entries = hdr->count - hdr->stale;
  1555. if (hdr->magic == XFS_DIR2_LEAF1_MAGIC ||
  1556. hdr->magic == XFS_DIR2_LEAFN_MAGIC)
  1557. hdrsize = sizeof(struct xfs_dir2_leaf_hdr);
  1558. else
  1559. hdrsize = sizeof(struct xfs_dir3_leaf_hdr);
  1560. return hdrsize + entries * sizeof(xfs_dir2_leaf_entry_t)
  1561. + counts * sizeof(xfs_dir2_data_off_t)
  1562. + sizeof(xfs_dir2_leaf_tail_t);
  1563. }
  1564. /*
  1565. * Convert node form directory to leaf form directory.
  1566. * The root of the node form dir needs to already be a LEAFN block.
  1567. * Just return if we can't do anything.
  1568. */
  1569. int /* error */
  1570. xfs_dir2_node_to_leaf(
  1571. xfs_da_state_t *state) /* directory operation state */
  1572. {
  1573. xfs_da_args_t *args; /* operation arguments */
  1574. xfs_inode_t *dp; /* incore directory inode */
  1575. int error; /* error return code */
  1576. struct xfs_buf *fbp; /* buffer for freespace block */
  1577. xfs_fileoff_t fo; /* freespace file offset */
  1578. xfs_dir2_free_t *free; /* freespace structure */
  1579. struct xfs_buf *lbp; /* buffer for leaf block */
  1580. xfs_dir2_leaf_tail_t *ltp; /* tail of leaf structure */
  1581. xfs_dir2_leaf_t *leaf; /* leaf structure */
  1582. xfs_mount_t *mp; /* filesystem mount point */
  1583. int rval; /* successful free trim? */
  1584. xfs_trans_t *tp; /* transaction pointer */
  1585. struct xfs_dir3_icleaf_hdr leafhdr;
  1586. struct xfs_dir3_icfree_hdr freehdr;
  1587. /*
  1588. * There's more than a leaf level in the btree, so there must
  1589. * be multiple leafn blocks. Give up.
  1590. */
  1591. if (state->path.active > 1)
  1592. return 0;
  1593. args = state->args;
  1594. trace_xfs_dir2_node_to_leaf(args);
  1595. mp = state->mp;
  1596. dp = args->dp;
  1597. tp = args->trans;
  1598. /*
  1599. * Get the last offset in the file.
  1600. */
  1601. if ((error = xfs_bmap_last_offset(dp, &fo, XFS_DATA_FORK))) {
  1602. return error;
  1603. }
  1604. fo -= args->geo->fsbcount;
  1605. /*
  1606. * If there are freespace blocks other than the first one,
  1607. * take this opportunity to remove trailing empty freespace blocks
  1608. * that may have been left behind during no-space-reservation
  1609. * operations.
  1610. */
  1611. while (fo > args->geo->freeblk) {
  1612. if ((error = xfs_dir2_node_trim_free(args, fo, &rval))) {
  1613. return error;
  1614. }
  1615. if (rval)
  1616. fo -= args->geo->fsbcount;
  1617. else
  1618. return 0;
  1619. }
  1620. /*
  1621. * Now find the block just before the freespace block.
  1622. */
  1623. if ((error = xfs_bmap_last_before(tp, dp, &fo, XFS_DATA_FORK))) {
  1624. return error;
  1625. }
  1626. /*
  1627. * If it's not the single leaf block, give up.
  1628. */
  1629. if (XFS_FSB_TO_B(mp, fo) > XFS_DIR2_LEAF_OFFSET + args->geo->blksize)
  1630. return 0;
  1631. lbp = state->path.blk[0].bp;
  1632. leaf = lbp->b_addr;
  1633. dp->d_ops->leaf_hdr_from_disk(&leafhdr, leaf);
  1634. ASSERT(leafhdr.magic == XFS_DIR2_LEAFN_MAGIC ||
  1635. leafhdr.magic == XFS_DIR3_LEAFN_MAGIC);
  1636. /*
  1637. * Read the freespace block.
  1638. */
  1639. error = xfs_dir2_free_read(tp, dp, args->geo->freeblk, &fbp);
  1640. if (error)
  1641. return error;
  1642. free = fbp->b_addr;
  1643. dp->d_ops->free_hdr_from_disk(&freehdr, free);
  1644. ASSERT(!freehdr.firstdb);
  1645. /*
  1646. * Now see if the leafn and free data will fit in a leaf1.
  1647. * If not, release the buffer and give up.
  1648. */
  1649. if (xfs_dir3_leaf_size(&leafhdr, freehdr.nvalid) > args->geo->blksize) {
  1650. xfs_trans_brelse(tp, fbp);
  1651. return 0;
  1652. }
  1653. /*
  1654. * If the leaf has any stale entries in it, compress them out.
  1655. */
  1656. if (leafhdr.stale)
  1657. xfs_dir3_leaf_compact(args, &leafhdr, lbp);
  1658. lbp->b_ops = &xfs_dir3_leaf1_buf_ops;
  1659. xfs_trans_buf_set_type(tp, lbp, XFS_BLFT_DIR_LEAF1_BUF);
  1660. leafhdr.magic = (leafhdr.magic == XFS_DIR2_LEAFN_MAGIC)
  1661. ? XFS_DIR2_LEAF1_MAGIC
  1662. : XFS_DIR3_LEAF1_MAGIC;
  1663. /*
  1664. * Set up the leaf tail from the freespace block.
  1665. */
  1666. ltp = xfs_dir2_leaf_tail_p(args->geo, leaf);
  1667. ltp->bestcount = cpu_to_be32(freehdr.nvalid);
  1668. /*
  1669. * Set up the leaf bests table.
  1670. */
  1671. memcpy(xfs_dir2_leaf_bests_p(ltp), dp->d_ops->free_bests_p(free),
  1672. freehdr.nvalid * sizeof(xfs_dir2_data_off_t));
  1673. dp->d_ops->leaf_hdr_to_disk(leaf, &leafhdr);
  1674. xfs_dir3_leaf_log_header(args, lbp);
  1675. xfs_dir3_leaf_log_bests(args, lbp, 0, be32_to_cpu(ltp->bestcount) - 1);
  1676. xfs_dir3_leaf_log_tail(args, lbp);
  1677. xfs_dir3_leaf_check(dp, lbp);
  1678. /*
  1679. * Get rid of the freespace block.
  1680. */
  1681. error = xfs_dir2_shrink_inode(args,
  1682. xfs_dir2_byte_to_db(args->geo, XFS_DIR2_FREE_OFFSET),
  1683. fbp);
  1684. if (error) {
  1685. /*
  1686. * This can't fail here because it can only happen when
  1687. * punching out the middle of an extent, and this is an
  1688. * isolated block.
  1689. */
  1690. ASSERT(error != -ENOSPC);
  1691. return error;
  1692. }
  1693. fbp = NULL;
  1694. /*
  1695. * Now see if we can convert the single-leaf directory
  1696. * down to a block form directory.
  1697. * This routine always kills the dabuf for the leaf, so
  1698. * eliminate it from the path.
  1699. */
  1700. error = xfs_dir2_leaf_to_block(args, lbp, NULL);
  1701. state->path.blk[0].bp = NULL;
  1702. return error;
  1703. }