xfs_alloc.c 74 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768176917701771177217731774177517761777177817791780178117821783178417851786178717881789179017911792179317941795179617971798179918001801180218031804180518061807180818091810181118121813181418151816181718181819182018211822182318241825182618271828182918301831183218331834183518361837183818391840184118421843184418451846184718481849185018511852185318541855185618571858185918601861186218631864186518661867186818691870187118721873187418751876187718781879188018811882188318841885188618871888188918901891189218931894189518961897189818991900190119021903190419051906190719081909191019111912191319141915191619171918191919201921192219231924192519261927192819291930193119321933193419351936193719381939194019411942194319441945194619471948194919501951195219531954195519561957195819591960196119621963196419651966196719681969197019711972197319741975197619771978197919801981198219831984198519861987198819891990199119921993199419951996199719981999200020012002200320042005200620072008200920102011201220132014201520162017201820192020202120222023202420252026202720282029203020312032203320342035203620372038203920402041204220432044204520462047204820492050205120522053205420552056205720582059206020612062206320642065206620672068206920702071207220732074207520762077207820792080208120822083208420852086208720882089209020912092209320942095209620972098209921002101210221032104210521062107210821092110211121122113211421152116211721182119212021212122212321242125212621272128212921302131213221332134213521362137213821392140214121422143214421452146214721482149215021512152215321542155215621572158215921602161216221632164216521662167216821692170217121722173217421752176217721782179218021812182218321842185218621872188218921902191219221932194219521962197219821992200220122022203220422052206220722082209221022112212221322142215221622172218221922202221222222232224222522262227222822292230223122322233223422352236223722382239224022412242224322442245224622472248224922502251225222532254225522562257225822592260226122622263226422652266226722682269227022712272227322742275227622772278227922802281228222832284228522862287228822892290229122922293229422952296229722982299230023012302230323042305230623072308230923102311231223132314231523162317231823192320232123222323232423252326232723282329233023312332233323342335233623372338233923402341234223432344234523462347234823492350235123522353235423552356235723582359236023612362236323642365236623672368236923702371237223732374237523762377237823792380238123822383238423852386238723882389239023912392239323942395239623972398239924002401240224032404240524062407240824092410241124122413241424152416241724182419242024212422242324242425242624272428242924302431243224332434243524362437243824392440244124422443244424452446244724482449245024512452245324542455245624572458245924602461246224632464246524662467246824692470247124722473247424752476247724782479248024812482248324842485248624872488248924902491249224932494249524962497249824992500250125022503250425052506250725082509251025112512251325142515251625172518251925202521252225232524252525262527252825292530253125322533253425352536253725382539254025412542254325442545254625472548254925502551255225532554255525562557255825592560256125622563256425652566256725682569257025712572257325742575257625772578257925802581258225832584258525862587258825892590259125922593259425952596259725982599260026012602260326042605260626072608260926102611261226132614261526162617261826192620262126222623262426252626
  1. /*
  2. * Copyright (c) 2000-2002,2005 Silicon Graphics, Inc.
  3. * All Rights Reserved.
  4. *
  5. * This program is free software; you can redistribute it and/or
  6. * modify it under the terms of the GNU General Public License as
  7. * published by the Free Software Foundation.
  8. *
  9. * This program is distributed in the hope that it would be useful,
  10. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  12. * GNU General Public License for more details.
  13. *
  14. * You should have received a copy of the GNU General Public License
  15. * along with this program; if not, write the Free Software Foundation,
  16. * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
  17. */
  18. #include "xfs.h"
  19. #include "xfs_fs.h"
  20. #include "xfs_types.h"
  21. #include "xfs_bit.h"
  22. #include "xfs_log.h"
  23. #include "xfs_inum.h"
  24. #include "xfs_trans.h"
  25. #include "xfs_sb.h"
  26. #include "xfs_ag.h"
  27. #include "xfs_dir2.h"
  28. #include "xfs_dmapi.h"
  29. #include "xfs_mount.h"
  30. #include "xfs_bmap_btree.h"
  31. #include "xfs_alloc_btree.h"
  32. #include "xfs_ialloc_btree.h"
  33. #include "xfs_dir2_sf.h"
  34. #include "xfs_attr_sf.h"
  35. #include "xfs_dinode.h"
  36. #include "xfs_inode.h"
  37. #include "xfs_btree.h"
  38. #include "xfs_ialloc.h"
  39. #include "xfs_alloc.h"
  40. #include "xfs_error.h"
  41. #define XFS_ABSDIFF(a,b) (((a) <= (b)) ? ((b) - (a)) : ((a) - (b)))
  42. #define XFSA_FIXUP_BNO_OK 1
  43. #define XFSA_FIXUP_CNT_OK 2
  44. STATIC int
  45. xfs_alloc_search_busy(xfs_trans_t *tp,
  46. xfs_agnumber_t agno,
  47. xfs_agblock_t bno,
  48. xfs_extlen_t len);
  49. #if defined(XFS_ALLOC_TRACE)
  50. ktrace_t *xfs_alloc_trace_buf;
  51. #define TRACE_ALLOC(s,a) \
  52. xfs_alloc_trace_alloc(fname, s, a, __LINE__)
  53. #define TRACE_FREE(s,a,b,x,f) \
  54. xfs_alloc_trace_free(fname, s, mp, a, b, x, f, __LINE__)
  55. #define TRACE_MODAGF(s,a,f) \
  56. xfs_alloc_trace_modagf(fname, s, mp, a, f, __LINE__)
  57. #define TRACE_BUSY(fname,s,ag,agb,l,sl,tp) \
  58. xfs_alloc_trace_busy(fname, s, mp, ag, agb, l, sl, tp, XFS_ALLOC_KTRACE_BUSY, __LINE__)
  59. #define TRACE_UNBUSY(fname,s,ag,sl,tp) \
  60. xfs_alloc_trace_busy(fname, s, mp, ag, -1, -1, sl, tp, XFS_ALLOC_KTRACE_UNBUSY, __LINE__)
  61. #define TRACE_BUSYSEARCH(fname,s,ag,agb,l,sl,tp) \
  62. xfs_alloc_trace_busy(fname, s, mp, ag, agb, l, sl, tp, XFS_ALLOC_KTRACE_BUSYSEARCH, __LINE__)
  63. #else
  64. #define TRACE_ALLOC(s,a)
  65. #define TRACE_FREE(s,a,b,x,f)
  66. #define TRACE_MODAGF(s,a,f)
  67. #define TRACE_BUSY(s,a,ag,agb,l,sl,tp)
  68. #define TRACE_UNBUSY(fname,s,ag,sl,tp)
  69. #define TRACE_BUSYSEARCH(fname,s,ag,agb,l,sl,tp)
  70. #endif /* XFS_ALLOC_TRACE */
  71. /*
  72. * Prototypes for per-ag allocation routines
  73. */
  74. STATIC int xfs_alloc_ag_vextent_exact(xfs_alloc_arg_t *);
  75. STATIC int xfs_alloc_ag_vextent_near(xfs_alloc_arg_t *);
  76. STATIC int xfs_alloc_ag_vextent_size(xfs_alloc_arg_t *);
  77. STATIC int xfs_alloc_ag_vextent_small(xfs_alloc_arg_t *,
  78. xfs_btree_cur_t *, xfs_agblock_t *, xfs_extlen_t *, int *);
  79. /*
  80. * Internal functions.
  81. */
  82. /*
  83. * Compute aligned version of the found extent.
  84. * Takes alignment and min length into account.
  85. */
  86. STATIC int /* success (>= minlen) */
  87. xfs_alloc_compute_aligned(
  88. xfs_agblock_t foundbno, /* starting block in found extent */
  89. xfs_extlen_t foundlen, /* length in found extent */
  90. xfs_extlen_t alignment, /* alignment for allocation */
  91. xfs_extlen_t minlen, /* minimum length for allocation */
  92. xfs_agblock_t *resbno, /* result block number */
  93. xfs_extlen_t *reslen) /* result length */
  94. {
  95. xfs_agblock_t bno;
  96. xfs_extlen_t diff;
  97. xfs_extlen_t len;
  98. if (alignment > 1 && foundlen >= minlen) {
  99. bno = roundup(foundbno, alignment);
  100. diff = bno - foundbno;
  101. len = diff >= foundlen ? 0 : foundlen - diff;
  102. } else {
  103. bno = foundbno;
  104. len = foundlen;
  105. }
  106. *resbno = bno;
  107. *reslen = len;
  108. return len >= minlen;
  109. }
  110. /*
  111. * Compute best start block and diff for "near" allocations.
  112. * freelen >= wantlen already checked by caller.
  113. */
  114. STATIC xfs_extlen_t /* difference value (absolute) */
  115. xfs_alloc_compute_diff(
  116. xfs_agblock_t wantbno, /* target starting block */
  117. xfs_extlen_t wantlen, /* target length */
  118. xfs_extlen_t alignment, /* target alignment */
  119. xfs_agblock_t freebno, /* freespace's starting block */
  120. xfs_extlen_t freelen, /* freespace's length */
  121. xfs_agblock_t *newbnop) /* result: best start block from free */
  122. {
  123. xfs_agblock_t freeend; /* end of freespace extent */
  124. xfs_agblock_t newbno1; /* return block number */
  125. xfs_agblock_t newbno2; /* other new block number */
  126. xfs_extlen_t newlen1=0; /* length with newbno1 */
  127. xfs_extlen_t newlen2=0; /* length with newbno2 */
  128. xfs_agblock_t wantend; /* end of target extent */
  129. ASSERT(freelen >= wantlen);
  130. freeend = freebno + freelen;
  131. wantend = wantbno + wantlen;
  132. if (freebno >= wantbno) {
  133. if ((newbno1 = roundup(freebno, alignment)) >= freeend)
  134. newbno1 = NULLAGBLOCK;
  135. } else if (freeend >= wantend && alignment > 1) {
  136. newbno1 = roundup(wantbno, alignment);
  137. newbno2 = newbno1 - alignment;
  138. if (newbno1 >= freeend)
  139. newbno1 = NULLAGBLOCK;
  140. else
  141. newlen1 = XFS_EXTLEN_MIN(wantlen, freeend - newbno1);
  142. if (newbno2 < freebno)
  143. newbno2 = NULLAGBLOCK;
  144. else
  145. newlen2 = XFS_EXTLEN_MIN(wantlen, freeend - newbno2);
  146. if (newbno1 != NULLAGBLOCK && newbno2 != NULLAGBLOCK) {
  147. if (newlen1 < newlen2 ||
  148. (newlen1 == newlen2 &&
  149. XFS_ABSDIFF(newbno1, wantbno) >
  150. XFS_ABSDIFF(newbno2, wantbno)))
  151. newbno1 = newbno2;
  152. } else if (newbno2 != NULLAGBLOCK)
  153. newbno1 = newbno2;
  154. } else if (freeend >= wantend) {
  155. newbno1 = wantbno;
  156. } else if (alignment > 1) {
  157. newbno1 = roundup(freeend - wantlen, alignment);
  158. if (newbno1 > freeend - wantlen &&
  159. newbno1 - alignment >= freebno)
  160. newbno1 -= alignment;
  161. else if (newbno1 >= freeend)
  162. newbno1 = NULLAGBLOCK;
  163. } else
  164. newbno1 = freeend - wantlen;
  165. *newbnop = newbno1;
  166. return newbno1 == NULLAGBLOCK ? 0 : XFS_ABSDIFF(newbno1, wantbno);
  167. }
  168. /*
  169. * Fix up the length, based on mod and prod.
  170. * len should be k * prod + mod for some k.
  171. * If len is too small it is returned unchanged.
  172. * If len hits maxlen it is left alone.
  173. */
  174. STATIC void
  175. xfs_alloc_fix_len(
  176. xfs_alloc_arg_t *args) /* allocation argument structure */
  177. {
  178. xfs_extlen_t k;
  179. xfs_extlen_t rlen;
  180. ASSERT(args->mod < args->prod);
  181. rlen = args->len;
  182. ASSERT(rlen >= args->minlen);
  183. ASSERT(rlen <= args->maxlen);
  184. if (args->prod <= 1 || rlen < args->mod || rlen == args->maxlen ||
  185. (args->mod == 0 && rlen < args->prod))
  186. return;
  187. k = rlen % args->prod;
  188. if (k == args->mod)
  189. return;
  190. if (k > args->mod) {
  191. if ((int)(rlen = rlen - k - args->mod) < (int)args->minlen)
  192. return;
  193. } else {
  194. if ((int)(rlen = rlen - args->prod - (args->mod - k)) <
  195. (int)args->minlen)
  196. return;
  197. }
  198. ASSERT(rlen >= args->minlen);
  199. ASSERT(rlen <= args->maxlen);
  200. args->len = rlen;
  201. }
  202. /*
  203. * Fix up length if there is too little space left in the a.g.
  204. * Return 1 if ok, 0 if too little, should give up.
  205. */
  206. STATIC int
  207. xfs_alloc_fix_minleft(
  208. xfs_alloc_arg_t *args) /* allocation argument structure */
  209. {
  210. xfs_agf_t *agf; /* a.g. freelist header */
  211. int diff; /* free space difference */
  212. if (args->minleft == 0)
  213. return 1;
  214. agf = XFS_BUF_TO_AGF(args->agbp);
  215. diff = be32_to_cpu(agf->agf_freeblks)
  216. + be32_to_cpu(agf->agf_flcount)
  217. - args->len - args->minleft;
  218. if (diff >= 0)
  219. return 1;
  220. args->len += diff; /* shrink the allocated space */
  221. if (args->len >= args->minlen)
  222. return 1;
  223. args->agbno = NULLAGBLOCK;
  224. return 0;
  225. }
  226. /*
  227. * Update the two btrees, logically removing from freespace the extent
  228. * starting at rbno, rlen blocks. The extent is contained within the
  229. * actual (current) free extent fbno for flen blocks.
  230. * Flags are passed in indicating whether the cursors are set to the
  231. * relevant records.
  232. */
  233. STATIC int /* error code */
  234. xfs_alloc_fixup_trees(
  235. xfs_btree_cur_t *cnt_cur, /* cursor for by-size btree */
  236. xfs_btree_cur_t *bno_cur, /* cursor for by-block btree */
  237. xfs_agblock_t fbno, /* starting block of free extent */
  238. xfs_extlen_t flen, /* length of free extent */
  239. xfs_agblock_t rbno, /* starting block of returned extent */
  240. xfs_extlen_t rlen, /* length of returned extent */
  241. int flags) /* flags, XFSA_FIXUP_... */
  242. {
  243. int error; /* error code */
  244. int i; /* operation results */
  245. xfs_agblock_t nfbno1; /* first new free startblock */
  246. xfs_agblock_t nfbno2; /* second new free startblock */
  247. xfs_extlen_t nflen1=0; /* first new free length */
  248. xfs_extlen_t nflen2=0; /* second new free length */
  249. /*
  250. * Look up the record in the by-size tree if necessary.
  251. */
  252. if (flags & XFSA_FIXUP_CNT_OK) {
  253. #ifdef DEBUG
  254. if ((error = xfs_alloc_get_rec(cnt_cur, &nfbno1, &nflen1, &i)))
  255. return error;
  256. XFS_WANT_CORRUPTED_RETURN(
  257. i == 1 && nfbno1 == fbno && nflen1 == flen);
  258. #endif
  259. } else {
  260. if ((error = xfs_alloc_lookup_eq(cnt_cur, fbno, flen, &i)))
  261. return error;
  262. XFS_WANT_CORRUPTED_RETURN(i == 1);
  263. }
  264. /*
  265. * Look up the record in the by-block tree if necessary.
  266. */
  267. if (flags & XFSA_FIXUP_BNO_OK) {
  268. #ifdef DEBUG
  269. if ((error = xfs_alloc_get_rec(bno_cur, &nfbno1, &nflen1, &i)))
  270. return error;
  271. XFS_WANT_CORRUPTED_RETURN(
  272. i == 1 && nfbno1 == fbno && nflen1 == flen);
  273. #endif
  274. } else {
  275. if ((error = xfs_alloc_lookup_eq(bno_cur, fbno, flen, &i)))
  276. return error;
  277. XFS_WANT_CORRUPTED_RETURN(i == 1);
  278. }
  279. #ifdef DEBUG
  280. {
  281. xfs_alloc_block_t *bnoblock;
  282. xfs_alloc_block_t *cntblock;
  283. if (bno_cur->bc_nlevels == 1 &&
  284. cnt_cur->bc_nlevels == 1) {
  285. bnoblock = XFS_BUF_TO_ALLOC_BLOCK(bno_cur->bc_bufs[0]);
  286. cntblock = XFS_BUF_TO_ALLOC_BLOCK(cnt_cur->bc_bufs[0]);
  287. XFS_WANT_CORRUPTED_RETURN(
  288. be16_to_cpu(bnoblock->bb_numrecs) ==
  289. be16_to_cpu(cntblock->bb_numrecs));
  290. }
  291. }
  292. #endif
  293. /*
  294. * Deal with all four cases: the allocated record is contained
  295. * within the freespace record, so we can have new freespace
  296. * at either (or both) end, or no freespace remaining.
  297. */
  298. if (rbno == fbno && rlen == flen)
  299. nfbno1 = nfbno2 = NULLAGBLOCK;
  300. else if (rbno == fbno) {
  301. nfbno1 = rbno + rlen;
  302. nflen1 = flen - rlen;
  303. nfbno2 = NULLAGBLOCK;
  304. } else if (rbno + rlen == fbno + flen) {
  305. nfbno1 = fbno;
  306. nflen1 = flen - rlen;
  307. nfbno2 = NULLAGBLOCK;
  308. } else {
  309. nfbno1 = fbno;
  310. nflen1 = rbno - fbno;
  311. nfbno2 = rbno + rlen;
  312. nflen2 = (fbno + flen) - nfbno2;
  313. }
  314. /*
  315. * Delete the entry from the by-size btree.
  316. */
  317. if ((error = xfs_alloc_delete(cnt_cur, &i)))
  318. return error;
  319. XFS_WANT_CORRUPTED_RETURN(i == 1);
  320. /*
  321. * Add new by-size btree entry(s).
  322. */
  323. if (nfbno1 != NULLAGBLOCK) {
  324. if ((error = xfs_alloc_lookup_eq(cnt_cur, nfbno1, nflen1, &i)))
  325. return error;
  326. XFS_WANT_CORRUPTED_RETURN(i == 0);
  327. if ((error = xfs_alloc_insert(cnt_cur, &i)))
  328. return error;
  329. XFS_WANT_CORRUPTED_RETURN(i == 1);
  330. }
  331. if (nfbno2 != NULLAGBLOCK) {
  332. if ((error = xfs_alloc_lookup_eq(cnt_cur, nfbno2, nflen2, &i)))
  333. return error;
  334. XFS_WANT_CORRUPTED_RETURN(i == 0);
  335. if ((error = xfs_alloc_insert(cnt_cur, &i)))
  336. return error;
  337. XFS_WANT_CORRUPTED_RETURN(i == 1);
  338. }
  339. /*
  340. * Fix up the by-block btree entry(s).
  341. */
  342. if (nfbno1 == NULLAGBLOCK) {
  343. /*
  344. * No remaining freespace, just delete the by-block tree entry.
  345. */
  346. if ((error = xfs_alloc_delete(bno_cur, &i)))
  347. return error;
  348. XFS_WANT_CORRUPTED_RETURN(i == 1);
  349. } else {
  350. /*
  351. * Update the by-block entry to start later|be shorter.
  352. */
  353. if ((error = xfs_alloc_update(bno_cur, nfbno1, nflen1)))
  354. return error;
  355. }
  356. if (nfbno2 != NULLAGBLOCK) {
  357. /*
  358. * 2 resulting free entries, need to add one.
  359. */
  360. if ((error = xfs_alloc_lookup_eq(bno_cur, nfbno2, nflen2, &i)))
  361. return error;
  362. XFS_WANT_CORRUPTED_RETURN(i == 0);
  363. if ((error = xfs_alloc_insert(bno_cur, &i)))
  364. return error;
  365. XFS_WANT_CORRUPTED_RETURN(i == 1);
  366. }
  367. return 0;
  368. }
  369. /*
  370. * Read in the allocation group free block array.
  371. */
  372. STATIC int /* error */
  373. xfs_alloc_read_agfl(
  374. xfs_mount_t *mp, /* mount point structure */
  375. xfs_trans_t *tp, /* transaction pointer */
  376. xfs_agnumber_t agno, /* allocation group number */
  377. xfs_buf_t **bpp) /* buffer for the ag free block array */
  378. {
  379. xfs_buf_t *bp; /* return value */
  380. int error;
  381. ASSERT(agno != NULLAGNUMBER);
  382. error = xfs_trans_read_buf(
  383. mp, tp, mp->m_ddev_targp,
  384. XFS_AG_DADDR(mp, agno, XFS_AGFL_DADDR(mp)),
  385. XFS_FSS_TO_BB(mp, 1), 0, &bp);
  386. if (error)
  387. return error;
  388. ASSERT(bp);
  389. ASSERT(!XFS_BUF_GETERROR(bp));
  390. XFS_BUF_SET_VTYPE_REF(bp, B_FS_AGFL, XFS_AGFL_REF);
  391. *bpp = bp;
  392. return 0;
  393. }
  394. #if defined(XFS_ALLOC_TRACE)
  395. /*
  396. * Add an allocation trace entry for an alloc call.
  397. */
  398. STATIC void
  399. xfs_alloc_trace_alloc(
  400. char *name, /* function tag string */
  401. char *str, /* additional string */
  402. xfs_alloc_arg_t *args, /* allocation argument structure */
  403. int line) /* source line number */
  404. {
  405. ktrace_enter(xfs_alloc_trace_buf,
  406. (void *)(__psint_t)(XFS_ALLOC_KTRACE_ALLOC | (line << 16)),
  407. (void *)name,
  408. (void *)str,
  409. (void *)args->mp,
  410. (void *)(__psunsigned_t)args->agno,
  411. (void *)(__psunsigned_t)args->agbno,
  412. (void *)(__psunsigned_t)args->minlen,
  413. (void *)(__psunsigned_t)args->maxlen,
  414. (void *)(__psunsigned_t)args->mod,
  415. (void *)(__psunsigned_t)args->prod,
  416. (void *)(__psunsigned_t)args->minleft,
  417. (void *)(__psunsigned_t)args->total,
  418. (void *)(__psunsigned_t)args->alignment,
  419. (void *)(__psunsigned_t)args->len,
  420. (void *)((((__psint_t)args->type) << 16) |
  421. (__psint_t)args->otype),
  422. (void *)(__psint_t)((args->wasdel << 3) |
  423. (args->wasfromfl << 2) |
  424. (args->isfl << 1) |
  425. (args->userdata << 0)));
  426. }
  427. /*
  428. * Add an allocation trace entry for a free call.
  429. */
  430. STATIC void
  431. xfs_alloc_trace_free(
  432. char *name, /* function tag string */
  433. char *str, /* additional string */
  434. xfs_mount_t *mp, /* file system mount point */
  435. xfs_agnumber_t agno, /* allocation group number */
  436. xfs_agblock_t agbno, /* a.g. relative block number */
  437. xfs_extlen_t len, /* length of extent */
  438. int isfl, /* set if is freelist allocation/free */
  439. int line) /* source line number */
  440. {
  441. ktrace_enter(xfs_alloc_trace_buf,
  442. (void *)(__psint_t)(XFS_ALLOC_KTRACE_FREE | (line << 16)),
  443. (void *)name,
  444. (void *)str,
  445. (void *)mp,
  446. (void *)(__psunsigned_t)agno,
  447. (void *)(__psunsigned_t)agbno,
  448. (void *)(__psunsigned_t)len,
  449. (void *)(__psint_t)isfl,
  450. NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL);
  451. }
  452. /*
  453. * Add an allocation trace entry for modifying an agf.
  454. */
  455. STATIC void
  456. xfs_alloc_trace_modagf(
  457. char *name, /* function tag string */
  458. char *str, /* additional string */
  459. xfs_mount_t *mp, /* file system mount point */
  460. xfs_agf_t *agf, /* new agf value */
  461. int flags, /* logging flags for agf */
  462. int line) /* source line number */
  463. {
  464. ktrace_enter(xfs_alloc_trace_buf,
  465. (void *)(__psint_t)(XFS_ALLOC_KTRACE_MODAGF | (line << 16)),
  466. (void *)name,
  467. (void *)str,
  468. (void *)mp,
  469. (void *)(__psint_t)flags,
  470. (void *)(__psunsigned_t)be32_to_cpu(agf->agf_seqno),
  471. (void *)(__psunsigned_t)be32_to_cpu(agf->agf_length),
  472. (void *)(__psunsigned_t)be32_to_cpu(agf->agf_roots[XFS_BTNUM_BNO]),
  473. (void *)(__psunsigned_t)be32_to_cpu(agf->agf_roots[XFS_BTNUM_CNT]),
  474. (void *)(__psunsigned_t)be32_to_cpu(agf->agf_levels[XFS_BTNUM_BNO]),
  475. (void *)(__psunsigned_t)be32_to_cpu(agf->agf_levels[XFS_BTNUM_CNT]),
  476. (void *)(__psunsigned_t)be32_to_cpu(agf->agf_flfirst),
  477. (void *)(__psunsigned_t)be32_to_cpu(agf->agf_fllast),
  478. (void *)(__psunsigned_t)be32_to_cpu(agf->agf_flcount),
  479. (void *)(__psunsigned_t)be32_to_cpu(agf->agf_freeblks),
  480. (void *)(__psunsigned_t)be32_to_cpu(agf->agf_longest));
  481. }
  482. STATIC void
  483. xfs_alloc_trace_busy(
  484. char *name, /* function tag string */
  485. char *str, /* additional string */
  486. xfs_mount_t *mp, /* file system mount point */
  487. xfs_agnumber_t agno, /* allocation group number */
  488. xfs_agblock_t agbno, /* a.g. relative block number */
  489. xfs_extlen_t len, /* length of extent */
  490. int slot, /* perag Busy slot */
  491. xfs_trans_t *tp,
  492. int trtype, /* type: add, delete, search */
  493. int line) /* source line number */
  494. {
  495. ktrace_enter(xfs_alloc_trace_buf,
  496. (void *)(__psint_t)(trtype | (line << 16)),
  497. (void *)name,
  498. (void *)str,
  499. (void *)mp,
  500. (void *)(__psunsigned_t)agno,
  501. (void *)(__psunsigned_t)agbno,
  502. (void *)(__psunsigned_t)len,
  503. (void *)(__psint_t)slot,
  504. (void *)tp,
  505. NULL, NULL, NULL, NULL, NULL, NULL, NULL);
  506. }
  507. #endif /* XFS_ALLOC_TRACE */
  508. /*
  509. * Allocation group level functions.
  510. */
  511. /*
  512. * Allocate a variable extent in the allocation group agno.
  513. * Type and bno are used to determine where in the allocation group the
  514. * extent will start.
  515. * Extent's length (returned in *len) will be between minlen and maxlen,
  516. * and of the form k * prod + mod unless there's nothing that large.
  517. * Return the starting a.g. block, or NULLAGBLOCK if we can't do it.
  518. */
  519. STATIC int /* error */
  520. xfs_alloc_ag_vextent(
  521. xfs_alloc_arg_t *args) /* argument structure for allocation */
  522. {
  523. int error=0;
  524. #ifdef XFS_ALLOC_TRACE
  525. static char fname[] = "xfs_alloc_ag_vextent";
  526. #endif
  527. ASSERT(args->minlen > 0);
  528. ASSERT(args->maxlen > 0);
  529. ASSERT(args->minlen <= args->maxlen);
  530. ASSERT(args->mod < args->prod);
  531. ASSERT(args->alignment > 0);
  532. /*
  533. * Branch to correct routine based on the type.
  534. */
  535. args->wasfromfl = 0;
  536. switch (args->type) {
  537. case XFS_ALLOCTYPE_THIS_AG:
  538. error = xfs_alloc_ag_vextent_size(args);
  539. break;
  540. case XFS_ALLOCTYPE_NEAR_BNO:
  541. error = xfs_alloc_ag_vextent_near(args);
  542. break;
  543. case XFS_ALLOCTYPE_THIS_BNO:
  544. error = xfs_alloc_ag_vextent_exact(args);
  545. break;
  546. default:
  547. ASSERT(0);
  548. /* NOTREACHED */
  549. }
  550. if (error)
  551. return error;
  552. /*
  553. * If the allocation worked, need to change the agf structure
  554. * (and log it), and the superblock.
  555. */
  556. if (args->agbno != NULLAGBLOCK) {
  557. xfs_agf_t *agf; /* allocation group freelist header */
  558. #ifdef XFS_ALLOC_TRACE
  559. xfs_mount_t *mp = args->mp;
  560. #endif
  561. long slen = (long)args->len;
  562. ASSERT(args->len >= args->minlen && args->len <= args->maxlen);
  563. ASSERT(!(args->wasfromfl) || !args->isfl);
  564. ASSERT(args->agbno % args->alignment == 0);
  565. if (!(args->wasfromfl)) {
  566. agf = XFS_BUF_TO_AGF(args->agbp);
  567. be32_add(&agf->agf_freeblks, -(args->len));
  568. xfs_trans_agblocks_delta(args->tp,
  569. -((long)(args->len)));
  570. args->pag->pagf_freeblks -= args->len;
  571. ASSERT(be32_to_cpu(agf->agf_freeblks) <=
  572. be32_to_cpu(agf->agf_length));
  573. TRACE_MODAGF(NULL, agf, XFS_AGF_FREEBLKS);
  574. xfs_alloc_log_agf(args->tp, args->agbp,
  575. XFS_AGF_FREEBLKS);
  576. /* search the busylist for these blocks */
  577. xfs_alloc_search_busy(args->tp, args->agno,
  578. args->agbno, args->len);
  579. }
  580. if (!args->isfl)
  581. xfs_trans_mod_sb(args->tp,
  582. args->wasdel ? XFS_TRANS_SB_RES_FDBLOCKS :
  583. XFS_TRANS_SB_FDBLOCKS, -slen);
  584. XFS_STATS_INC(xs_allocx);
  585. XFS_STATS_ADD(xs_allocb, args->len);
  586. }
  587. return 0;
  588. }
  589. /*
  590. * Allocate a variable extent at exactly agno/bno.
  591. * Extent's length (returned in *len) will be between minlen and maxlen,
  592. * and of the form k * prod + mod unless there's nothing that large.
  593. * Return the starting a.g. block (bno), or NULLAGBLOCK if we can't do it.
  594. */
  595. STATIC int /* error */
  596. xfs_alloc_ag_vextent_exact(
  597. xfs_alloc_arg_t *args) /* allocation argument structure */
  598. {
  599. xfs_btree_cur_t *bno_cur;/* by block-number btree cursor */
  600. xfs_btree_cur_t *cnt_cur;/* by count btree cursor */
  601. xfs_agblock_t end; /* end of allocated extent */
  602. int error;
  603. xfs_agblock_t fbno; /* start block of found extent */
  604. xfs_agblock_t fend; /* end block of found extent */
  605. xfs_extlen_t flen; /* length of found extent */
  606. #ifdef XFS_ALLOC_TRACE
  607. static char fname[] = "xfs_alloc_ag_vextent_exact";
  608. #endif
  609. int i; /* success/failure of operation */
  610. xfs_agblock_t maxend; /* end of maximal extent */
  611. xfs_agblock_t minend; /* end of minimal extent */
  612. xfs_extlen_t rlen; /* length of returned extent */
  613. ASSERT(args->alignment == 1);
  614. /*
  615. * Allocate/initialize a cursor for the by-number freespace btree.
  616. */
  617. bno_cur = xfs_btree_init_cursor(args->mp, args->tp, args->agbp,
  618. args->agno, XFS_BTNUM_BNO, NULL, 0);
  619. /*
  620. * Lookup bno and minlen in the btree (minlen is irrelevant, really).
  621. * Look for the closest free block <= bno, it must contain bno
  622. * if any free block does.
  623. */
  624. if ((error = xfs_alloc_lookup_le(bno_cur, args->agbno, args->minlen, &i)))
  625. goto error0;
  626. if (!i) {
  627. /*
  628. * Didn't find it, return null.
  629. */
  630. xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
  631. args->agbno = NULLAGBLOCK;
  632. return 0;
  633. }
  634. /*
  635. * Grab the freespace record.
  636. */
  637. if ((error = xfs_alloc_get_rec(bno_cur, &fbno, &flen, &i)))
  638. goto error0;
  639. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  640. ASSERT(fbno <= args->agbno);
  641. minend = args->agbno + args->minlen;
  642. maxend = args->agbno + args->maxlen;
  643. fend = fbno + flen;
  644. /*
  645. * Give up if the freespace isn't long enough for the minimum request.
  646. */
  647. if (fend < minend) {
  648. xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
  649. args->agbno = NULLAGBLOCK;
  650. return 0;
  651. }
  652. /*
  653. * End of extent will be smaller of the freespace end and the
  654. * maximal requested end.
  655. */
  656. end = XFS_AGBLOCK_MIN(fend, maxend);
  657. /*
  658. * Fix the length according to mod and prod if given.
  659. */
  660. args->len = end - args->agbno;
  661. xfs_alloc_fix_len(args);
  662. if (!xfs_alloc_fix_minleft(args)) {
  663. xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
  664. return 0;
  665. }
  666. rlen = args->len;
  667. ASSERT(args->agbno + rlen <= fend);
  668. end = args->agbno + rlen;
  669. /*
  670. * We are allocating agbno for rlen [agbno .. end]
  671. * Allocate/initialize a cursor for the by-size btree.
  672. */
  673. cnt_cur = xfs_btree_init_cursor(args->mp, args->tp, args->agbp,
  674. args->agno, XFS_BTNUM_CNT, NULL, 0);
  675. ASSERT(args->agbno + args->len <=
  676. be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_length));
  677. if ((error = xfs_alloc_fixup_trees(cnt_cur, bno_cur, fbno, flen,
  678. args->agbno, args->len, XFSA_FIXUP_BNO_OK))) {
  679. xfs_btree_del_cursor(cnt_cur, XFS_BTREE_ERROR);
  680. goto error0;
  681. }
  682. xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
  683. xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
  684. TRACE_ALLOC("normal", args);
  685. args->wasfromfl = 0;
  686. return 0;
  687. error0:
  688. xfs_btree_del_cursor(bno_cur, XFS_BTREE_ERROR);
  689. TRACE_ALLOC("error", args);
  690. return error;
  691. }
  692. /*
  693. * Allocate a variable extent near bno in the allocation group agno.
  694. * Extent's length (returned in len) will be between minlen and maxlen,
  695. * and of the form k * prod + mod unless there's nothing that large.
  696. * Return the starting a.g. block, or NULLAGBLOCK if we can't do it.
  697. */
  698. STATIC int /* error */
  699. xfs_alloc_ag_vextent_near(
  700. xfs_alloc_arg_t *args) /* allocation argument structure */
  701. {
  702. xfs_btree_cur_t *bno_cur_gt; /* cursor for bno btree, right side */
  703. xfs_btree_cur_t *bno_cur_lt; /* cursor for bno btree, left side */
  704. xfs_btree_cur_t *cnt_cur; /* cursor for count btree */
  705. #ifdef XFS_ALLOC_TRACE
  706. static char fname[] = "xfs_alloc_ag_vextent_near";
  707. #endif
  708. xfs_agblock_t gtbno; /* start bno of right side entry */
  709. xfs_agblock_t gtbnoa; /* aligned ... */
  710. xfs_extlen_t gtdiff; /* difference to right side entry */
  711. xfs_extlen_t gtlen; /* length of right side entry */
  712. xfs_extlen_t gtlena; /* aligned ... */
  713. xfs_agblock_t gtnew; /* useful start bno of right side */
  714. int error; /* error code */
  715. int i; /* result code, temporary */
  716. int j; /* result code, temporary */
  717. xfs_agblock_t ltbno; /* start bno of left side entry */
  718. xfs_agblock_t ltbnoa; /* aligned ... */
  719. xfs_extlen_t ltdiff; /* difference to left side entry */
  720. /*REFERENCED*/
  721. xfs_agblock_t ltend; /* end bno of left side entry */
  722. xfs_extlen_t ltlen; /* length of left side entry */
  723. xfs_extlen_t ltlena; /* aligned ... */
  724. xfs_agblock_t ltnew; /* useful start bno of left side */
  725. xfs_extlen_t rlen; /* length of returned extent */
  726. #if defined(DEBUG) && defined(__KERNEL__)
  727. /*
  728. * Randomly don't execute the first algorithm.
  729. */
  730. int dofirst; /* set to do first algorithm */
  731. dofirst = random() & 1;
  732. #endif
  733. /*
  734. * Get a cursor for the by-size btree.
  735. */
  736. cnt_cur = xfs_btree_init_cursor(args->mp, args->tp, args->agbp,
  737. args->agno, XFS_BTNUM_CNT, NULL, 0);
  738. ltlen = 0;
  739. bno_cur_lt = bno_cur_gt = NULL;
  740. /*
  741. * See if there are any free extents as big as maxlen.
  742. */
  743. if ((error = xfs_alloc_lookup_ge(cnt_cur, 0, args->maxlen, &i)))
  744. goto error0;
  745. /*
  746. * If none, then pick up the last entry in the tree unless the
  747. * tree is empty.
  748. */
  749. if (!i) {
  750. if ((error = xfs_alloc_ag_vextent_small(args, cnt_cur, &ltbno,
  751. &ltlen, &i)))
  752. goto error0;
  753. if (i == 0 || ltlen == 0) {
  754. xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
  755. return 0;
  756. }
  757. ASSERT(i == 1);
  758. }
  759. args->wasfromfl = 0;
  760. /*
  761. * First algorithm.
  762. * If the requested extent is large wrt the freespaces available
  763. * in this a.g., then the cursor will be pointing to a btree entry
  764. * near the right edge of the tree. If it's in the last btree leaf
  765. * block, then we just examine all the entries in that block
  766. * that are big enough, and pick the best one.
  767. * This is written as a while loop so we can break out of it,
  768. * but we never loop back to the top.
  769. */
  770. while (xfs_btree_islastblock(cnt_cur, 0)) {
  771. xfs_extlen_t bdiff;
  772. int besti=0;
  773. xfs_extlen_t blen=0;
  774. xfs_agblock_t bnew=0;
  775. #if defined(DEBUG) && defined(__KERNEL__)
  776. if (!dofirst)
  777. break;
  778. #endif
  779. /*
  780. * Start from the entry that lookup found, sequence through
  781. * all larger free blocks. If we're actually pointing at a
  782. * record smaller than maxlen, go to the start of this block,
  783. * and skip all those smaller than minlen.
  784. */
  785. if (ltlen || args->alignment > 1) {
  786. cnt_cur->bc_ptrs[0] = 1;
  787. do {
  788. if ((error = xfs_alloc_get_rec(cnt_cur, &ltbno,
  789. &ltlen, &i)))
  790. goto error0;
  791. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  792. if (ltlen >= args->minlen)
  793. break;
  794. if ((error = xfs_alloc_increment(cnt_cur, 0, &i)))
  795. goto error0;
  796. } while (i);
  797. ASSERT(ltlen >= args->minlen);
  798. if (!i)
  799. break;
  800. }
  801. i = cnt_cur->bc_ptrs[0];
  802. for (j = 1, blen = 0, bdiff = 0;
  803. !error && j && (blen < args->maxlen || bdiff > 0);
  804. error = xfs_alloc_increment(cnt_cur, 0, &j)) {
  805. /*
  806. * For each entry, decide if it's better than
  807. * the previous best entry.
  808. */
  809. if ((error = xfs_alloc_get_rec(cnt_cur, &ltbno, &ltlen, &i)))
  810. goto error0;
  811. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  812. if (!xfs_alloc_compute_aligned(ltbno, ltlen,
  813. args->alignment, args->minlen,
  814. &ltbnoa, &ltlena))
  815. continue;
  816. args->len = XFS_EXTLEN_MIN(ltlena, args->maxlen);
  817. xfs_alloc_fix_len(args);
  818. ASSERT(args->len >= args->minlen);
  819. if (args->len < blen)
  820. continue;
  821. ltdiff = xfs_alloc_compute_diff(args->agbno, args->len,
  822. args->alignment, ltbno, ltlen, &ltnew);
  823. if (ltnew != NULLAGBLOCK &&
  824. (args->len > blen || ltdiff < bdiff)) {
  825. bdiff = ltdiff;
  826. bnew = ltnew;
  827. blen = args->len;
  828. besti = cnt_cur->bc_ptrs[0];
  829. }
  830. }
  831. /*
  832. * It didn't work. We COULD be in a case where
  833. * there's a good record somewhere, so try again.
  834. */
  835. if (blen == 0)
  836. break;
  837. /*
  838. * Point at the best entry, and retrieve it again.
  839. */
  840. cnt_cur->bc_ptrs[0] = besti;
  841. if ((error = xfs_alloc_get_rec(cnt_cur, &ltbno, &ltlen, &i)))
  842. goto error0;
  843. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  844. ltend = ltbno + ltlen;
  845. ASSERT(ltend <= be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_length));
  846. args->len = blen;
  847. if (!xfs_alloc_fix_minleft(args)) {
  848. xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
  849. TRACE_ALLOC("nominleft", args);
  850. return 0;
  851. }
  852. blen = args->len;
  853. /*
  854. * We are allocating starting at bnew for blen blocks.
  855. */
  856. args->agbno = bnew;
  857. ASSERT(bnew >= ltbno);
  858. ASSERT(bnew + blen <= ltend);
  859. /*
  860. * Set up a cursor for the by-bno tree.
  861. */
  862. bno_cur_lt = xfs_btree_init_cursor(args->mp, args->tp,
  863. args->agbp, args->agno, XFS_BTNUM_BNO, NULL, 0);
  864. /*
  865. * Fix up the btree entries.
  866. */
  867. if ((error = xfs_alloc_fixup_trees(cnt_cur, bno_cur_lt, ltbno,
  868. ltlen, bnew, blen, XFSA_FIXUP_CNT_OK)))
  869. goto error0;
  870. xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
  871. xfs_btree_del_cursor(bno_cur_lt, XFS_BTREE_NOERROR);
  872. TRACE_ALLOC("first", args);
  873. return 0;
  874. }
  875. /*
  876. * Second algorithm.
  877. * Search in the by-bno tree to the left and to the right
  878. * simultaneously, until in each case we find a space big enough,
  879. * or run into the edge of the tree. When we run into the edge,
  880. * we deallocate that cursor.
  881. * If both searches succeed, we compare the two spaces and pick
  882. * the better one.
  883. * With alignment, it's possible for both to fail; the upper
  884. * level algorithm that picks allocation groups for allocations
  885. * is not supposed to do this.
  886. */
  887. /*
  888. * Allocate and initialize the cursor for the leftward search.
  889. */
  890. bno_cur_lt = xfs_btree_init_cursor(args->mp, args->tp, args->agbp,
  891. args->agno, XFS_BTNUM_BNO, NULL, 0);
  892. /*
  893. * Lookup <= bno to find the leftward search's starting point.
  894. */
  895. if ((error = xfs_alloc_lookup_le(bno_cur_lt, args->agbno, args->maxlen, &i)))
  896. goto error0;
  897. if (!i) {
  898. /*
  899. * Didn't find anything; use this cursor for the rightward
  900. * search.
  901. */
  902. bno_cur_gt = bno_cur_lt;
  903. bno_cur_lt = NULL;
  904. }
  905. /*
  906. * Found something. Duplicate the cursor for the rightward search.
  907. */
  908. else if ((error = xfs_btree_dup_cursor(bno_cur_lt, &bno_cur_gt)))
  909. goto error0;
  910. /*
  911. * Increment the cursor, so we will point at the entry just right
  912. * of the leftward entry if any, or to the leftmost entry.
  913. */
  914. if ((error = xfs_alloc_increment(bno_cur_gt, 0, &i)))
  915. goto error0;
  916. if (!i) {
  917. /*
  918. * It failed, there are no rightward entries.
  919. */
  920. xfs_btree_del_cursor(bno_cur_gt, XFS_BTREE_NOERROR);
  921. bno_cur_gt = NULL;
  922. }
  923. /*
  924. * Loop going left with the leftward cursor, right with the
  925. * rightward cursor, until either both directions give up or
  926. * we find an entry at least as big as minlen.
  927. */
  928. do {
  929. if (bno_cur_lt) {
  930. if ((error = xfs_alloc_get_rec(bno_cur_lt, &ltbno, &ltlen, &i)))
  931. goto error0;
  932. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  933. if (xfs_alloc_compute_aligned(ltbno, ltlen,
  934. args->alignment, args->minlen,
  935. &ltbnoa, &ltlena))
  936. break;
  937. if ((error = xfs_alloc_decrement(bno_cur_lt, 0, &i)))
  938. goto error0;
  939. if (!i) {
  940. xfs_btree_del_cursor(bno_cur_lt,
  941. XFS_BTREE_NOERROR);
  942. bno_cur_lt = NULL;
  943. }
  944. }
  945. if (bno_cur_gt) {
  946. if ((error = xfs_alloc_get_rec(bno_cur_gt, &gtbno, &gtlen, &i)))
  947. goto error0;
  948. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  949. if (xfs_alloc_compute_aligned(gtbno, gtlen,
  950. args->alignment, args->minlen,
  951. &gtbnoa, &gtlena))
  952. break;
  953. if ((error = xfs_alloc_increment(bno_cur_gt, 0, &i)))
  954. goto error0;
  955. if (!i) {
  956. xfs_btree_del_cursor(bno_cur_gt,
  957. XFS_BTREE_NOERROR);
  958. bno_cur_gt = NULL;
  959. }
  960. }
  961. } while (bno_cur_lt || bno_cur_gt);
  962. /*
  963. * Got both cursors still active, need to find better entry.
  964. */
  965. if (bno_cur_lt && bno_cur_gt) {
  966. /*
  967. * Left side is long enough, look for a right side entry.
  968. */
  969. if (ltlena >= args->minlen) {
  970. /*
  971. * Fix up the length.
  972. */
  973. args->len = XFS_EXTLEN_MIN(ltlena, args->maxlen);
  974. xfs_alloc_fix_len(args);
  975. rlen = args->len;
  976. ltdiff = xfs_alloc_compute_diff(args->agbno, rlen,
  977. args->alignment, ltbno, ltlen, &ltnew);
  978. /*
  979. * Not perfect.
  980. */
  981. if (ltdiff) {
  982. /*
  983. * Look until we find a better one, run out of
  984. * space, or run off the end.
  985. */
  986. while (bno_cur_lt && bno_cur_gt) {
  987. if ((error = xfs_alloc_get_rec(
  988. bno_cur_gt, &gtbno,
  989. &gtlen, &i)))
  990. goto error0;
  991. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  992. xfs_alloc_compute_aligned(gtbno, gtlen,
  993. args->alignment, args->minlen,
  994. &gtbnoa, &gtlena);
  995. /*
  996. * The left one is clearly better.
  997. */
  998. if (gtbnoa >= args->agbno + ltdiff) {
  999. xfs_btree_del_cursor(
  1000. bno_cur_gt,
  1001. XFS_BTREE_NOERROR);
  1002. bno_cur_gt = NULL;
  1003. break;
  1004. }
  1005. /*
  1006. * If we reach a big enough entry,
  1007. * compare the two and pick the best.
  1008. */
  1009. if (gtlena >= args->minlen) {
  1010. args->len =
  1011. XFS_EXTLEN_MIN(gtlena,
  1012. args->maxlen);
  1013. xfs_alloc_fix_len(args);
  1014. rlen = args->len;
  1015. gtdiff = xfs_alloc_compute_diff(
  1016. args->agbno, rlen,
  1017. args->alignment,
  1018. gtbno, gtlen, &gtnew);
  1019. /*
  1020. * Right side is better.
  1021. */
  1022. if (gtdiff < ltdiff) {
  1023. xfs_btree_del_cursor(
  1024. bno_cur_lt,
  1025. XFS_BTREE_NOERROR);
  1026. bno_cur_lt = NULL;
  1027. }
  1028. /*
  1029. * Left side is better.
  1030. */
  1031. else {
  1032. xfs_btree_del_cursor(
  1033. bno_cur_gt,
  1034. XFS_BTREE_NOERROR);
  1035. bno_cur_gt = NULL;
  1036. }
  1037. break;
  1038. }
  1039. /*
  1040. * Fell off the right end.
  1041. */
  1042. if ((error = xfs_alloc_increment(
  1043. bno_cur_gt, 0, &i)))
  1044. goto error0;
  1045. if (!i) {
  1046. xfs_btree_del_cursor(
  1047. bno_cur_gt,
  1048. XFS_BTREE_NOERROR);
  1049. bno_cur_gt = NULL;
  1050. break;
  1051. }
  1052. }
  1053. }
  1054. /*
  1055. * The left side is perfect, trash the right side.
  1056. */
  1057. else {
  1058. xfs_btree_del_cursor(bno_cur_gt,
  1059. XFS_BTREE_NOERROR);
  1060. bno_cur_gt = NULL;
  1061. }
  1062. }
  1063. /*
  1064. * It's the right side that was found first, look left.
  1065. */
  1066. else {
  1067. /*
  1068. * Fix up the length.
  1069. */
  1070. args->len = XFS_EXTLEN_MIN(gtlena, args->maxlen);
  1071. xfs_alloc_fix_len(args);
  1072. rlen = args->len;
  1073. gtdiff = xfs_alloc_compute_diff(args->agbno, rlen,
  1074. args->alignment, gtbno, gtlen, &gtnew);
  1075. /*
  1076. * Right side entry isn't perfect.
  1077. */
  1078. if (gtdiff) {
  1079. /*
  1080. * Look until we find a better one, run out of
  1081. * space, or run off the end.
  1082. */
  1083. while (bno_cur_lt && bno_cur_gt) {
  1084. if ((error = xfs_alloc_get_rec(
  1085. bno_cur_lt, &ltbno,
  1086. &ltlen, &i)))
  1087. goto error0;
  1088. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  1089. xfs_alloc_compute_aligned(ltbno, ltlen,
  1090. args->alignment, args->minlen,
  1091. &ltbnoa, &ltlena);
  1092. /*
  1093. * The right one is clearly better.
  1094. */
  1095. if (ltbnoa <= args->agbno - gtdiff) {
  1096. xfs_btree_del_cursor(
  1097. bno_cur_lt,
  1098. XFS_BTREE_NOERROR);
  1099. bno_cur_lt = NULL;
  1100. break;
  1101. }
  1102. /*
  1103. * If we reach a big enough entry,
  1104. * compare the two and pick the best.
  1105. */
  1106. if (ltlena >= args->minlen) {
  1107. args->len = XFS_EXTLEN_MIN(
  1108. ltlena, args->maxlen);
  1109. xfs_alloc_fix_len(args);
  1110. rlen = args->len;
  1111. ltdiff = xfs_alloc_compute_diff(
  1112. args->agbno, rlen,
  1113. args->alignment,
  1114. ltbno, ltlen, &ltnew);
  1115. /*
  1116. * Left side is better.
  1117. */
  1118. if (ltdiff < gtdiff) {
  1119. xfs_btree_del_cursor(
  1120. bno_cur_gt,
  1121. XFS_BTREE_NOERROR);
  1122. bno_cur_gt = NULL;
  1123. }
  1124. /*
  1125. * Right side is better.
  1126. */
  1127. else {
  1128. xfs_btree_del_cursor(
  1129. bno_cur_lt,
  1130. XFS_BTREE_NOERROR);
  1131. bno_cur_lt = NULL;
  1132. }
  1133. break;
  1134. }
  1135. /*
  1136. * Fell off the left end.
  1137. */
  1138. if ((error = xfs_alloc_decrement(
  1139. bno_cur_lt, 0, &i)))
  1140. goto error0;
  1141. if (!i) {
  1142. xfs_btree_del_cursor(bno_cur_lt,
  1143. XFS_BTREE_NOERROR);
  1144. bno_cur_lt = NULL;
  1145. break;
  1146. }
  1147. }
  1148. }
  1149. /*
  1150. * The right side is perfect, trash the left side.
  1151. */
  1152. else {
  1153. xfs_btree_del_cursor(bno_cur_lt,
  1154. XFS_BTREE_NOERROR);
  1155. bno_cur_lt = NULL;
  1156. }
  1157. }
  1158. }
  1159. /*
  1160. * If we couldn't get anything, give up.
  1161. */
  1162. if (bno_cur_lt == NULL && bno_cur_gt == NULL) {
  1163. TRACE_ALLOC("neither", args);
  1164. args->agbno = NULLAGBLOCK;
  1165. return 0;
  1166. }
  1167. /*
  1168. * At this point we have selected a freespace entry, either to the
  1169. * left or to the right. If it's on the right, copy all the
  1170. * useful variables to the "left" set so we only have one
  1171. * copy of this code.
  1172. */
  1173. if (bno_cur_gt) {
  1174. bno_cur_lt = bno_cur_gt;
  1175. bno_cur_gt = NULL;
  1176. ltbno = gtbno;
  1177. ltbnoa = gtbnoa;
  1178. ltlen = gtlen;
  1179. ltlena = gtlena;
  1180. j = 1;
  1181. } else
  1182. j = 0;
  1183. /*
  1184. * Fix up the length and compute the useful address.
  1185. */
  1186. ltend = ltbno + ltlen;
  1187. args->len = XFS_EXTLEN_MIN(ltlena, args->maxlen);
  1188. xfs_alloc_fix_len(args);
  1189. if (!xfs_alloc_fix_minleft(args)) {
  1190. TRACE_ALLOC("nominleft", args);
  1191. xfs_btree_del_cursor(bno_cur_lt, XFS_BTREE_NOERROR);
  1192. xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
  1193. return 0;
  1194. }
  1195. rlen = args->len;
  1196. (void)xfs_alloc_compute_diff(args->agbno, rlen, args->alignment, ltbno,
  1197. ltlen, &ltnew);
  1198. ASSERT(ltnew >= ltbno);
  1199. ASSERT(ltnew + rlen <= ltend);
  1200. ASSERT(ltnew + rlen <= be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_length));
  1201. args->agbno = ltnew;
  1202. if ((error = xfs_alloc_fixup_trees(cnt_cur, bno_cur_lt, ltbno, ltlen,
  1203. ltnew, rlen, XFSA_FIXUP_BNO_OK)))
  1204. goto error0;
  1205. TRACE_ALLOC(j ? "gt" : "lt", args);
  1206. xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
  1207. xfs_btree_del_cursor(bno_cur_lt, XFS_BTREE_NOERROR);
  1208. return 0;
  1209. error0:
  1210. TRACE_ALLOC("error", args);
  1211. if (cnt_cur != NULL)
  1212. xfs_btree_del_cursor(cnt_cur, XFS_BTREE_ERROR);
  1213. if (bno_cur_lt != NULL)
  1214. xfs_btree_del_cursor(bno_cur_lt, XFS_BTREE_ERROR);
  1215. if (bno_cur_gt != NULL)
  1216. xfs_btree_del_cursor(bno_cur_gt, XFS_BTREE_ERROR);
  1217. return error;
  1218. }
  1219. /*
  1220. * Allocate a variable extent anywhere in the allocation group agno.
  1221. * Extent's length (returned in len) will be between minlen and maxlen,
  1222. * and of the form k * prod + mod unless there's nothing that large.
  1223. * Return the starting a.g. block, or NULLAGBLOCK if we can't do it.
  1224. */
  1225. STATIC int /* error */
  1226. xfs_alloc_ag_vextent_size(
  1227. xfs_alloc_arg_t *args) /* allocation argument structure */
  1228. {
  1229. xfs_btree_cur_t *bno_cur; /* cursor for bno btree */
  1230. xfs_btree_cur_t *cnt_cur; /* cursor for cnt btree */
  1231. int error; /* error result */
  1232. xfs_agblock_t fbno; /* start of found freespace */
  1233. xfs_extlen_t flen; /* length of found freespace */
  1234. #ifdef XFS_ALLOC_TRACE
  1235. static char fname[] = "xfs_alloc_ag_vextent_size";
  1236. #endif
  1237. int i; /* temp status variable */
  1238. xfs_agblock_t rbno; /* returned block number */
  1239. xfs_extlen_t rlen; /* length of returned extent */
  1240. /*
  1241. * Allocate and initialize a cursor for the by-size btree.
  1242. */
  1243. cnt_cur = xfs_btree_init_cursor(args->mp, args->tp, args->agbp,
  1244. args->agno, XFS_BTNUM_CNT, NULL, 0);
  1245. bno_cur = NULL;
  1246. /*
  1247. * Look for an entry >= maxlen+alignment-1 blocks.
  1248. */
  1249. if ((error = xfs_alloc_lookup_ge(cnt_cur, 0,
  1250. args->maxlen + args->alignment - 1, &i)))
  1251. goto error0;
  1252. /*
  1253. * If none, then pick up the last entry in the tree unless the
  1254. * tree is empty.
  1255. */
  1256. if (!i) {
  1257. if ((error = xfs_alloc_ag_vextent_small(args, cnt_cur, &fbno,
  1258. &flen, &i)))
  1259. goto error0;
  1260. if (i == 0 || flen == 0) {
  1261. xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
  1262. TRACE_ALLOC("noentry", args);
  1263. return 0;
  1264. }
  1265. ASSERT(i == 1);
  1266. }
  1267. /*
  1268. * There's a freespace as big as maxlen+alignment-1, get it.
  1269. */
  1270. else {
  1271. if ((error = xfs_alloc_get_rec(cnt_cur, &fbno, &flen, &i)))
  1272. goto error0;
  1273. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  1274. }
  1275. /*
  1276. * In the first case above, we got the last entry in the
  1277. * by-size btree. Now we check to see if the space hits maxlen
  1278. * once aligned; if not, we search left for something better.
  1279. * This can't happen in the second case above.
  1280. */
  1281. xfs_alloc_compute_aligned(fbno, flen, args->alignment, args->minlen,
  1282. &rbno, &rlen);
  1283. rlen = XFS_EXTLEN_MIN(args->maxlen, rlen);
  1284. XFS_WANT_CORRUPTED_GOTO(rlen == 0 ||
  1285. (rlen <= flen && rbno + rlen <= fbno + flen), error0);
  1286. if (rlen < args->maxlen) {
  1287. xfs_agblock_t bestfbno;
  1288. xfs_extlen_t bestflen;
  1289. xfs_agblock_t bestrbno;
  1290. xfs_extlen_t bestrlen;
  1291. bestrlen = rlen;
  1292. bestrbno = rbno;
  1293. bestflen = flen;
  1294. bestfbno = fbno;
  1295. for (;;) {
  1296. if ((error = xfs_alloc_decrement(cnt_cur, 0, &i)))
  1297. goto error0;
  1298. if (i == 0)
  1299. break;
  1300. if ((error = xfs_alloc_get_rec(cnt_cur, &fbno, &flen,
  1301. &i)))
  1302. goto error0;
  1303. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  1304. if (flen < bestrlen)
  1305. break;
  1306. xfs_alloc_compute_aligned(fbno, flen, args->alignment,
  1307. args->minlen, &rbno, &rlen);
  1308. rlen = XFS_EXTLEN_MIN(args->maxlen, rlen);
  1309. XFS_WANT_CORRUPTED_GOTO(rlen == 0 ||
  1310. (rlen <= flen && rbno + rlen <= fbno + flen),
  1311. error0);
  1312. if (rlen > bestrlen) {
  1313. bestrlen = rlen;
  1314. bestrbno = rbno;
  1315. bestflen = flen;
  1316. bestfbno = fbno;
  1317. if (rlen == args->maxlen)
  1318. break;
  1319. }
  1320. }
  1321. if ((error = xfs_alloc_lookup_eq(cnt_cur, bestfbno, bestflen,
  1322. &i)))
  1323. goto error0;
  1324. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  1325. rlen = bestrlen;
  1326. rbno = bestrbno;
  1327. flen = bestflen;
  1328. fbno = bestfbno;
  1329. }
  1330. args->wasfromfl = 0;
  1331. /*
  1332. * Fix up the length.
  1333. */
  1334. args->len = rlen;
  1335. xfs_alloc_fix_len(args);
  1336. if (rlen < args->minlen || !xfs_alloc_fix_minleft(args)) {
  1337. xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
  1338. TRACE_ALLOC("nominleft", args);
  1339. args->agbno = NULLAGBLOCK;
  1340. return 0;
  1341. }
  1342. rlen = args->len;
  1343. XFS_WANT_CORRUPTED_GOTO(rlen <= flen, error0);
  1344. /*
  1345. * Allocate and initialize a cursor for the by-block tree.
  1346. */
  1347. bno_cur = xfs_btree_init_cursor(args->mp, args->tp, args->agbp,
  1348. args->agno, XFS_BTNUM_BNO, NULL, 0);
  1349. if ((error = xfs_alloc_fixup_trees(cnt_cur, bno_cur, fbno, flen,
  1350. rbno, rlen, XFSA_FIXUP_CNT_OK)))
  1351. goto error0;
  1352. xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
  1353. xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
  1354. cnt_cur = bno_cur = NULL;
  1355. args->len = rlen;
  1356. args->agbno = rbno;
  1357. XFS_WANT_CORRUPTED_GOTO(
  1358. args->agbno + args->len <=
  1359. be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_length),
  1360. error0);
  1361. TRACE_ALLOC("normal", args);
  1362. return 0;
  1363. error0:
  1364. TRACE_ALLOC("error", args);
  1365. if (cnt_cur)
  1366. xfs_btree_del_cursor(cnt_cur, XFS_BTREE_ERROR);
  1367. if (bno_cur)
  1368. xfs_btree_del_cursor(bno_cur, XFS_BTREE_ERROR);
  1369. return error;
  1370. }
  1371. /*
  1372. * Deal with the case where only small freespaces remain.
  1373. * Either return the contents of the last freespace record,
  1374. * or allocate space from the freelist if there is nothing in the tree.
  1375. */
  1376. STATIC int /* error */
  1377. xfs_alloc_ag_vextent_small(
  1378. xfs_alloc_arg_t *args, /* allocation argument structure */
  1379. xfs_btree_cur_t *ccur, /* by-size cursor */
  1380. xfs_agblock_t *fbnop, /* result block number */
  1381. xfs_extlen_t *flenp, /* result length */
  1382. int *stat) /* status: 0-freelist, 1-normal/none */
  1383. {
  1384. int error;
  1385. xfs_agblock_t fbno;
  1386. xfs_extlen_t flen;
  1387. #ifdef XFS_ALLOC_TRACE
  1388. static char fname[] = "xfs_alloc_ag_vextent_small";
  1389. #endif
  1390. int i;
  1391. if ((error = xfs_alloc_decrement(ccur, 0, &i)))
  1392. goto error0;
  1393. if (i) {
  1394. if ((error = xfs_alloc_get_rec(ccur, &fbno, &flen, &i)))
  1395. goto error0;
  1396. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  1397. }
  1398. /*
  1399. * Nothing in the btree, try the freelist. Make sure
  1400. * to respect minleft even when pulling from the
  1401. * freelist.
  1402. */
  1403. else if (args->minlen == 1 && args->alignment == 1 && !args->isfl &&
  1404. (be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_flcount)
  1405. > args->minleft)) {
  1406. if ((error = xfs_alloc_get_freelist(args->tp, args->agbp, &fbno)))
  1407. goto error0;
  1408. if (fbno != NULLAGBLOCK) {
  1409. if (args->userdata) {
  1410. xfs_buf_t *bp;
  1411. bp = xfs_btree_get_bufs(args->mp, args->tp,
  1412. args->agno, fbno, 0);
  1413. xfs_trans_binval(args->tp, bp);
  1414. }
  1415. args->len = 1;
  1416. args->agbno = fbno;
  1417. XFS_WANT_CORRUPTED_GOTO(
  1418. args->agbno + args->len <=
  1419. be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_length),
  1420. error0);
  1421. args->wasfromfl = 1;
  1422. TRACE_ALLOC("freelist", args);
  1423. *stat = 0;
  1424. return 0;
  1425. }
  1426. /*
  1427. * Nothing in the freelist.
  1428. */
  1429. else
  1430. flen = 0;
  1431. }
  1432. /*
  1433. * Can't allocate from the freelist for some reason.
  1434. */
  1435. else {
  1436. fbno = NULLAGBLOCK;
  1437. flen = 0;
  1438. }
  1439. /*
  1440. * Can't do the allocation, give up.
  1441. */
  1442. if (flen < args->minlen) {
  1443. args->agbno = NULLAGBLOCK;
  1444. TRACE_ALLOC("notenough", args);
  1445. flen = 0;
  1446. }
  1447. *fbnop = fbno;
  1448. *flenp = flen;
  1449. *stat = 1;
  1450. TRACE_ALLOC("normal", args);
  1451. return 0;
  1452. error0:
  1453. TRACE_ALLOC("error", args);
  1454. return error;
  1455. }
  1456. /*
  1457. * Free the extent starting at agno/bno for length.
  1458. */
  1459. STATIC int /* error */
  1460. xfs_free_ag_extent(
  1461. xfs_trans_t *tp, /* transaction pointer */
  1462. xfs_buf_t *agbp, /* buffer for a.g. freelist header */
  1463. xfs_agnumber_t agno, /* allocation group number */
  1464. xfs_agblock_t bno, /* starting block number */
  1465. xfs_extlen_t len, /* length of extent */
  1466. int isfl) /* set if is freelist blocks - no sb acctg */
  1467. {
  1468. xfs_btree_cur_t *bno_cur; /* cursor for by-block btree */
  1469. xfs_btree_cur_t *cnt_cur; /* cursor for by-size btree */
  1470. int error; /* error return value */
  1471. #ifdef XFS_ALLOC_TRACE
  1472. static char fname[] = "xfs_free_ag_extent";
  1473. #endif
  1474. xfs_agblock_t gtbno; /* start of right neighbor block */
  1475. xfs_extlen_t gtlen; /* length of right neighbor block */
  1476. int haveleft; /* have a left neighbor block */
  1477. int haveright; /* have a right neighbor block */
  1478. int i; /* temp, result code */
  1479. xfs_agblock_t ltbno; /* start of left neighbor block */
  1480. xfs_extlen_t ltlen; /* length of left neighbor block */
  1481. xfs_mount_t *mp; /* mount point struct for filesystem */
  1482. xfs_agblock_t nbno; /* new starting block of freespace */
  1483. xfs_extlen_t nlen; /* new length of freespace */
  1484. mp = tp->t_mountp;
  1485. /*
  1486. * Allocate and initialize a cursor for the by-block btree.
  1487. */
  1488. bno_cur = xfs_btree_init_cursor(mp, tp, agbp, agno, XFS_BTNUM_BNO, NULL,
  1489. 0);
  1490. cnt_cur = NULL;
  1491. /*
  1492. * Look for a neighboring block on the left (lower block numbers)
  1493. * that is contiguous with this space.
  1494. */
  1495. if ((error = xfs_alloc_lookup_le(bno_cur, bno, len, &haveleft)))
  1496. goto error0;
  1497. if (haveleft) {
  1498. /*
  1499. * There is a block to our left.
  1500. */
  1501. if ((error = xfs_alloc_get_rec(bno_cur, &ltbno, &ltlen, &i)))
  1502. goto error0;
  1503. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  1504. /*
  1505. * It's not contiguous, though.
  1506. */
  1507. if (ltbno + ltlen < bno)
  1508. haveleft = 0;
  1509. else {
  1510. /*
  1511. * If this failure happens the request to free this
  1512. * space was invalid, it's (partly) already free.
  1513. * Very bad.
  1514. */
  1515. XFS_WANT_CORRUPTED_GOTO(ltbno + ltlen <= bno, error0);
  1516. }
  1517. }
  1518. /*
  1519. * Look for a neighboring block on the right (higher block numbers)
  1520. * that is contiguous with this space.
  1521. */
  1522. if ((error = xfs_alloc_increment(bno_cur, 0, &haveright)))
  1523. goto error0;
  1524. if (haveright) {
  1525. /*
  1526. * There is a block to our right.
  1527. */
  1528. if ((error = xfs_alloc_get_rec(bno_cur, &gtbno, &gtlen, &i)))
  1529. goto error0;
  1530. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  1531. /*
  1532. * It's not contiguous, though.
  1533. */
  1534. if (bno + len < gtbno)
  1535. haveright = 0;
  1536. else {
  1537. /*
  1538. * If this failure happens the request to free this
  1539. * space was invalid, it's (partly) already free.
  1540. * Very bad.
  1541. */
  1542. XFS_WANT_CORRUPTED_GOTO(gtbno >= bno + len, error0);
  1543. }
  1544. }
  1545. /*
  1546. * Now allocate and initialize a cursor for the by-size tree.
  1547. */
  1548. cnt_cur = xfs_btree_init_cursor(mp, tp, agbp, agno, XFS_BTNUM_CNT, NULL,
  1549. 0);
  1550. /*
  1551. * Have both left and right contiguous neighbors.
  1552. * Merge all three into a single free block.
  1553. */
  1554. if (haveleft && haveright) {
  1555. /*
  1556. * Delete the old by-size entry on the left.
  1557. */
  1558. if ((error = xfs_alloc_lookup_eq(cnt_cur, ltbno, ltlen, &i)))
  1559. goto error0;
  1560. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  1561. if ((error = xfs_alloc_delete(cnt_cur, &i)))
  1562. goto error0;
  1563. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  1564. /*
  1565. * Delete the old by-size entry on the right.
  1566. */
  1567. if ((error = xfs_alloc_lookup_eq(cnt_cur, gtbno, gtlen, &i)))
  1568. goto error0;
  1569. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  1570. if ((error = xfs_alloc_delete(cnt_cur, &i)))
  1571. goto error0;
  1572. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  1573. /*
  1574. * Delete the old by-block entry for the right block.
  1575. */
  1576. if ((error = xfs_alloc_delete(bno_cur, &i)))
  1577. goto error0;
  1578. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  1579. /*
  1580. * Move the by-block cursor back to the left neighbor.
  1581. */
  1582. if ((error = xfs_alloc_decrement(bno_cur, 0, &i)))
  1583. goto error0;
  1584. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  1585. #ifdef DEBUG
  1586. /*
  1587. * Check that this is the right record: delete didn't
  1588. * mangle the cursor.
  1589. */
  1590. {
  1591. xfs_agblock_t xxbno;
  1592. xfs_extlen_t xxlen;
  1593. if ((error = xfs_alloc_get_rec(bno_cur, &xxbno, &xxlen,
  1594. &i)))
  1595. goto error0;
  1596. XFS_WANT_CORRUPTED_GOTO(
  1597. i == 1 && xxbno == ltbno && xxlen == ltlen,
  1598. error0);
  1599. }
  1600. #endif
  1601. /*
  1602. * Update remaining by-block entry to the new, joined block.
  1603. */
  1604. nbno = ltbno;
  1605. nlen = len + ltlen + gtlen;
  1606. if ((error = xfs_alloc_update(bno_cur, nbno, nlen)))
  1607. goto error0;
  1608. }
  1609. /*
  1610. * Have only a left contiguous neighbor.
  1611. * Merge it together with the new freespace.
  1612. */
  1613. else if (haveleft) {
  1614. /*
  1615. * Delete the old by-size entry on the left.
  1616. */
  1617. if ((error = xfs_alloc_lookup_eq(cnt_cur, ltbno, ltlen, &i)))
  1618. goto error0;
  1619. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  1620. if ((error = xfs_alloc_delete(cnt_cur, &i)))
  1621. goto error0;
  1622. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  1623. /*
  1624. * Back up the by-block cursor to the left neighbor, and
  1625. * update its length.
  1626. */
  1627. if ((error = xfs_alloc_decrement(bno_cur, 0, &i)))
  1628. goto error0;
  1629. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  1630. nbno = ltbno;
  1631. nlen = len + ltlen;
  1632. if ((error = xfs_alloc_update(bno_cur, nbno, nlen)))
  1633. goto error0;
  1634. }
  1635. /*
  1636. * Have only a right contiguous neighbor.
  1637. * Merge it together with the new freespace.
  1638. */
  1639. else if (haveright) {
  1640. /*
  1641. * Delete the old by-size entry on the right.
  1642. */
  1643. if ((error = xfs_alloc_lookup_eq(cnt_cur, gtbno, gtlen, &i)))
  1644. goto error0;
  1645. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  1646. if ((error = xfs_alloc_delete(cnt_cur, &i)))
  1647. goto error0;
  1648. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  1649. /*
  1650. * Update the starting block and length of the right
  1651. * neighbor in the by-block tree.
  1652. */
  1653. nbno = bno;
  1654. nlen = len + gtlen;
  1655. if ((error = xfs_alloc_update(bno_cur, nbno, nlen)))
  1656. goto error0;
  1657. }
  1658. /*
  1659. * No contiguous neighbors.
  1660. * Insert the new freespace into the by-block tree.
  1661. */
  1662. else {
  1663. nbno = bno;
  1664. nlen = len;
  1665. if ((error = xfs_alloc_insert(bno_cur, &i)))
  1666. goto error0;
  1667. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  1668. }
  1669. xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
  1670. bno_cur = NULL;
  1671. /*
  1672. * In all cases we need to insert the new freespace in the by-size tree.
  1673. */
  1674. if ((error = xfs_alloc_lookup_eq(cnt_cur, nbno, nlen, &i)))
  1675. goto error0;
  1676. XFS_WANT_CORRUPTED_GOTO(i == 0, error0);
  1677. if ((error = xfs_alloc_insert(cnt_cur, &i)))
  1678. goto error0;
  1679. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  1680. xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
  1681. cnt_cur = NULL;
  1682. /*
  1683. * Update the freespace totals in the ag and superblock.
  1684. */
  1685. {
  1686. xfs_agf_t *agf;
  1687. xfs_perag_t *pag; /* per allocation group data */
  1688. agf = XFS_BUF_TO_AGF(agbp);
  1689. pag = &mp->m_perag[agno];
  1690. be32_add(&agf->agf_freeblks, len);
  1691. xfs_trans_agblocks_delta(tp, len);
  1692. pag->pagf_freeblks += len;
  1693. XFS_WANT_CORRUPTED_GOTO(
  1694. be32_to_cpu(agf->agf_freeblks) <=
  1695. be32_to_cpu(agf->agf_length),
  1696. error0);
  1697. TRACE_MODAGF(NULL, agf, XFS_AGF_FREEBLKS);
  1698. xfs_alloc_log_agf(tp, agbp, XFS_AGF_FREEBLKS);
  1699. if (!isfl)
  1700. xfs_trans_mod_sb(tp, XFS_TRANS_SB_FDBLOCKS, (long)len);
  1701. XFS_STATS_INC(xs_freex);
  1702. XFS_STATS_ADD(xs_freeb, len);
  1703. }
  1704. TRACE_FREE(haveleft ?
  1705. (haveright ? "both" : "left") :
  1706. (haveright ? "right" : "none"),
  1707. agno, bno, len, isfl);
  1708. /*
  1709. * Since blocks move to the free list without the coordination
  1710. * used in xfs_bmap_finish, we can't allow block to be available
  1711. * for reallocation and non-transaction writing (user data)
  1712. * until we know that the transaction that moved it to the free
  1713. * list is permanently on disk. We track the blocks by declaring
  1714. * these blocks as "busy"; the busy list is maintained on a per-ag
  1715. * basis and each transaction records which entries should be removed
  1716. * when the iclog commits to disk. If a busy block is allocated,
  1717. * the iclog is pushed up to the LSN that freed the block.
  1718. */
  1719. xfs_alloc_mark_busy(tp, agno, bno, len);
  1720. return 0;
  1721. error0:
  1722. TRACE_FREE("error", agno, bno, len, isfl);
  1723. if (bno_cur)
  1724. xfs_btree_del_cursor(bno_cur, XFS_BTREE_ERROR);
  1725. if (cnt_cur)
  1726. xfs_btree_del_cursor(cnt_cur, XFS_BTREE_ERROR);
  1727. return error;
  1728. }
  1729. /*
  1730. * Visible (exported) allocation/free functions.
  1731. * Some of these are used just by xfs_alloc_btree.c and this file.
  1732. */
  1733. /*
  1734. * Compute and fill in value of m_ag_maxlevels.
  1735. */
  1736. void
  1737. xfs_alloc_compute_maxlevels(
  1738. xfs_mount_t *mp) /* file system mount structure */
  1739. {
  1740. int level;
  1741. uint maxblocks;
  1742. uint maxleafents;
  1743. int minleafrecs;
  1744. int minnoderecs;
  1745. maxleafents = (mp->m_sb.sb_agblocks + 1) / 2;
  1746. minleafrecs = mp->m_alloc_mnr[0];
  1747. minnoderecs = mp->m_alloc_mnr[1];
  1748. maxblocks = (maxleafents + minleafrecs - 1) / minleafrecs;
  1749. for (level = 1; maxblocks > 1; level++)
  1750. maxblocks = (maxblocks + minnoderecs - 1) / minnoderecs;
  1751. mp->m_ag_maxlevels = level;
  1752. }
  1753. /*
  1754. * Decide whether to use this allocation group for this allocation.
  1755. * If so, fix up the btree freelist's size.
  1756. */
  1757. STATIC int /* error */
  1758. xfs_alloc_fix_freelist(
  1759. xfs_alloc_arg_t *args, /* allocation argument structure */
  1760. int flags) /* XFS_ALLOC_FLAG_... */
  1761. {
  1762. xfs_buf_t *agbp; /* agf buffer pointer */
  1763. xfs_agf_t *agf; /* a.g. freespace structure pointer */
  1764. xfs_buf_t *agflbp;/* agfl buffer pointer */
  1765. xfs_agblock_t bno; /* freelist block */
  1766. xfs_extlen_t delta; /* new blocks needed in freelist */
  1767. int error; /* error result code */
  1768. xfs_extlen_t longest;/* longest extent in allocation group */
  1769. xfs_mount_t *mp; /* file system mount point structure */
  1770. xfs_extlen_t need; /* total blocks needed in freelist */
  1771. xfs_perag_t *pag; /* per-ag information structure */
  1772. xfs_alloc_arg_t targs; /* local allocation arguments */
  1773. xfs_trans_t *tp; /* transaction pointer */
  1774. mp = args->mp;
  1775. pag = args->pag;
  1776. tp = args->tp;
  1777. if (!pag->pagf_init) {
  1778. if ((error = xfs_alloc_read_agf(mp, tp, args->agno, flags,
  1779. &agbp)))
  1780. return error;
  1781. if (!pag->pagf_init) {
  1782. ASSERT(flags & XFS_ALLOC_FLAG_TRYLOCK);
  1783. ASSERT(!(flags & XFS_ALLOC_FLAG_FREEING));
  1784. args->agbp = NULL;
  1785. return 0;
  1786. }
  1787. } else
  1788. agbp = NULL;
  1789. /*
  1790. * If this is a metadata preferred pag and we are user data
  1791. * then try somewhere else if we are not being asked to
  1792. * try harder at this point
  1793. */
  1794. if (pag->pagf_metadata && args->userdata &&
  1795. (flags & XFS_ALLOC_FLAG_TRYLOCK)) {
  1796. ASSERT(!(flags & XFS_ALLOC_FLAG_FREEING));
  1797. args->agbp = NULL;
  1798. return 0;
  1799. }
  1800. if (!(flags & XFS_ALLOC_FLAG_FREEING)) {
  1801. need = XFS_MIN_FREELIST_PAG(pag, mp);
  1802. delta = need > pag->pagf_flcount ? need - pag->pagf_flcount : 0;
  1803. /*
  1804. * If it looks like there isn't a long enough extent, or enough
  1805. * total blocks, reject it.
  1806. */
  1807. longest = (pag->pagf_longest > delta) ?
  1808. (pag->pagf_longest - delta) :
  1809. (pag->pagf_flcount > 0 || pag->pagf_longest > 0);
  1810. if ((args->minlen + args->alignment + args->minalignslop - 1) >
  1811. longest ||
  1812. ((int)(pag->pagf_freeblks + pag->pagf_flcount -
  1813. need - args->total) < (int)args->minleft)) {
  1814. if (agbp)
  1815. xfs_trans_brelse(tp, agbp);
  1816. args->agbp = NULL;
  1817. return 0;
  1818. }
  1819. }
  1820. /*
  1821. * Get the a.g. freespace buffer.
  1822. * Can fail if we're not blocking on locks, and it's held.
  1823. */
  1824. if (agbp == NULL) {
  1825. if ((error = xfs_alloc_read_agf(mp, tp, args->agno, flags,
  1826. &agbp)))
  1827. return error;
  1828. if (agbp == NULL) {
  1829. ASSERT(flags & XFS_ALLOC_FLAG_TRYLOCK);
  1830. ASSERT(!(flags & XFS_ALLOC_FLAG_FREEING));
  1831. args->agbp = NULL;
  1832. return 0;
  1833. }
  1834. }
  1835. /*
  1836. * Figure out how many blocks we should have in the freelist.
  1837. */
  1838. agf = XFS_BUF_TO_AGF(agbp);
  1839. need = XFS_MIN_FREELIST(agf, mp);
  1840. /*
  1841. * If there isn't enough total or single-extent, reject it.
  1842. */
  1843. if (!(flags & XFS_ALLOC_FLAG_FREEING)) {
  1844. delta = need > be32_to_cpu(agf->agf_flcount) ?
  1845. (need - be32_to_cpu(agf->agf_flcount)) : 0;
  1846. longest = be32_to_cpu(agf->agf_longest);
  1847. longest = (longest > delta) ? (longest - delta) :
  1848. (be32_to_cpu(agf->agf_flcount) > 0 || longest > 0);
  1849. if ((args->minlen + args->alignment + args->minalignslop - 1) >
  1850. longest ||
  1851. ((int)(be32_to_cpu(agf->agf_freeblks) +
  1852. be32_to_cpu(agf->agf_flcount) - need - args->total) <
  1853. (int)args->minleft)) {
  1854. xfs_trans_brelse(tp, agbp);
  1855. args->agbp = NULL;
  1856. return 0;
  1857. }
  1858. }
  1859. /*
  1860. * Make the freelist shorter if it's too long.
  1861. */
  1862. while (be32_to_cpu(agf->agf_flcount) > need) {
  1863. xfs_buf_t *bp;
  1864. if ((error = xfs_alloc_get_freelist(tp, agbp, &bno)))
  1865. return error;
  1866. if ((error = xfs_free_ag_extent(tp, agbp, args->agno, bno, 1, 1)))
  1867. return error;
  1868. bp = xfs_btree_get_bufs(mp, tp, args->agno, bno, 0);
  1869. xfs_trans_binval(tp, bp);
  1870. }
  1871. /*
  1872. * Initialize the args structure.
  1873. */
  1874. targs.tp = tp;
  1875. targs.mp = mp;
  1876. targs.agbp = agbp;
  1877. targs.agno = args->agno;
  1878. targs.mod = targs.minleft = targs.wasdel = targs.userdata =
  1879. targs.minalignslop = 0;
  1880. targs.alignment = targs.minlen = targs.prod = targs.isfl = 1;
  1881. targs.type = XFS_ALLOCTYPE_THIS_AG;
  1882. targs.pag = pag;
  1883. if ((error = xfs_alloc_read_agfl(mp, tp, targs.agno, &agflbp)))
  1884. return error;
  1885. /*
  1886. * Make the freelist longer if it's too short.
  1887. */
  1888. while (be32_to_cpu(agf->agf_flcount) < need) {
  1889. targs.agbno = 0;
  1890. targs.maxlen = need - be32_to_cpu(agf->agf_flcount);
  1891. /*
  1892. * Allocate as many blocks as possible at once.
  1893. */
  1894. if ((error = xfs_alloc_ag_vextent(&targs))) {
  1895. xfs_trans_brelse(tp, agflbp);
  1896. return error;
  1897. }
  1898. /*
  1899. * Stop if we run out. Won't happen if callers are obeying
  1900. * the restrictions correctly. Can happen for free calls
  1901. * on a completely full ag.
  1902. */
  1903. if (targs.agbno == NULLAGBLOCK) {
  1904. if (flags & XFS_ALLOC_FLAG_FREEING)
  1905. break;
  1906. xfs_trans_brelse(tp, agflbp);
  1907. args->agbp = NULL;
  1908. return 0;
  1909. }
  1910. /*
  1911. * Put each allocated block on the list.
  1912. */
  1913. for (bno = targs.agbno; bno < targs.agbno + targs.len; bno++) {
  1914. if ((error = xfs_alloc_put_freelist(tp, agbp, agflbp,
  1915. bno)))
  1916. return error;
  1917. }
  1918. }
  1919. xfs_trans_brelse(tp, agflbp);
  1920. args->agbp = agbp;
  1921. return 0;
  1922. }
  1923. /*
  1924. * Get a block from the freelist.
  1925. * Returns with the buffer for the block gotten.
  1926. */
  1927. int /* error */
  1928. xfs_alloc_get_freelist(
  1929. xfs_trans_t *tp, /* transaction pointer */
  1930. xfs_buf_t *agbp, /* buffer containing the agf structure */
  1931. xfs_agblock_t *bnop) /* block address retrieved from freelist */
  1932. {
  1933. xfs_agf_t *agf; /* a.g. freespace structure */
  1934. xfs_agfl_t *agfl; /* a.g. freelist structure */
  1935. xfs_buf_t *agflbp;/* buffer for a.g. freelist structure */
  1936. xfs_agblock_t bno; /* block number returned */
  1937. int error;
  1938. #ifdef XFS_ALLOC_TRACE
  1939. static char fname[] = "xfs_alloc_get_freelist";
  1940. #endif
  1941. xfs_mount_t *mp; /* mount structure */
  1942. xfs_perag_t *pag; /* per allocation group data */
  1943. agf = XFS_BUF_TO_AGF(agbp);
  1944. /*
  1945. * Freelist is empty, give up.
  1946. */
  1947. if (!agf->agf_flcount) {
  1948. *bnop = NULLAGBLOCK;
  1949. return 0;
  1950. }
  1951. /*
  1952. * Read the array of free blocks.
  1953. */
  1954. mp = tp->t_mountp;
  1955. if ((error = xfs_alloc_read_agfl(mp, tp,
  1956. be32_to_cpu(agf->agf_seqno), &agflbp)))
  1957. return error;
  1958. agfl = XFS_BUF_TO_AGFL(agflbp);
  1959. /*
  1960. * Get the block number and update the data structures.
  1961. */
  1962. bno = be32_to_cpu(agfl->agfl_bno[be32_to_cpu(agf->agf_flfirst)]);
  1963. be32_add(&agf->agf_flfirst, 1);
  1964. xfs_trans_brelse(tp, agflbp);
  1965. if (be32_to_cpu(agf->agf_flfirst) == XFS_AGFL_SIZE(mp))
  1966. agf->agf_flfirst = 0;
  1967. pag = &mp->m_perag[be32_to_cpu(agf->agf_seqno)];
  1968. be32_add(&agf->agf_flcount, -1);
  1969. xfs_trans_agflist_delta(tp, -1);
  1970. pag->pagf_flcount--;
  1971. TRACE_MODAGF(NULL, agf, XFS_AGF_FLFIRST | XFS_AGF_FLCOUNT);
  1972. xfs_alloc_log_agf(tp, agbp, XFS_AGF_FLFIRST | XFS_AGF_FLCOUNT);
  1973. *bnop = bno;
  1974. /*
  1975. * As blocks are freed, they are added to the per-ag busy list
  1976. * and remain there until the freeing transaction is committed to
  1977. * disk. Now that we have allocated blocks, this list must be
  1978. * searched to see if a block is being reused. If one is, then
  1979. * the freeing transaction must be pushed to disk NOW by forcing
  1980. * to disk all iclogs up that transaction's LSN.
  1981. */
  1982. xfs_alloc_search_busy(tp, be32_to_cpu(agf->agf_seqno), bno, 1);
  1983. return 0;
  1984. }
  1985. /*
  1986. * Log the given fields from the agf structure.
  1987. */
  1988. void
  1989. xfs_alloc_log_agf(
  1990. xfs_trans_t *tp, /* transaction pointer */
  1991. xfs_buf_t *bp, /* buffer for a.g. freelist header */
  1992. int fields) /* mask of fields to be logged (XFS_AGF_...) */
  1993. {
  1994. int first; /* first byte offset */
  1995. int last; /* last byte offset */
  1996. static const short offsets[] = {
  1997. offsetof(xfs_agf_t, agf_magicnum),
  1998. offsetof(xfs_agf_t, agf_versionnum),
  1999. offsetof(xfs_agf_t, agf_seqno),
  2000. offsetof(xfs_agf_t, agf_length),
  2001. offsetof(xfs_agf_t, agf_roots[0]),
  2002. offsetof(xfs_agf_t, agf_levels[0]),
  2003. offsetof(xfs_agf_t, agf_flfirst),
  2004. offsetof(xfs_agf_t, agf_fllast),
  2005. offsetof(xfs_agf_t, agf_flcount),
  2006. offsetof(xfs_agf_t, agf_freeblks),
  2007. offsetof(xfs_agf_t, agf_longest),
  2008. sizeof(xfs_agf_t)
  2009. };
  2010. xfs_btree_offsets(fields, offsets, XFS_AGF_NUM_BITS, &first, &last);
  2011. xfs_trans_log_buf(tp, bp, (uint)first, (uint)last);
  2012. }
  2013. /*
  2014. * Interface for inode allocation to force the pag data to be initialized.
  2015. */
  2016. int /* error */
  2017. xfs_alloc_pagf_init(
  2018. xfs_mount_t *mp, /* file system mount structure */
  2019. xfs_trans_t *tp, /* transaction pointer */
  2020. xfs_agnumber_t agno, /* allocation group number */
  2021. int flags) /* XFS_ALLOC_FLAGS_... */
  2022. {
  2023. xfs_buf_t *bp;
  2024. int error;
  2025. if ((error = xfs_alloc_read_agf(mp, tp, agno, flags, &bp)))
  2026. return error;
  2027. if (bp)
  2028. xfs_trans_brelse(tp, bp);
  2029. return 0;
  2030. }
  2031. /*
  2032. * Put the block on the freelist for the allocation group.
  2033. */
  2034. int /* error */
  2035. xfs_alloc_put_freelist(
  2036. xfs_trans_t *tp, /* transaction pointer */
  2037. xfs_buf_t *agbp, /* buffer for a.g. freelist header */
  2038. xfs_buf_t *agflbp,/* buffer for a.g. free block array */
  2039. xfs_agblock_t bno) /* block being freed */
  2040. {
  2041. xfs_agf_t *agf; /* a.g. freespace structure */
  2042. xfs_agfl_t *agfl; /* a.g. free block array */
  2043. __be32 *blockp;/* pointer to array entry */
  2044. int error;
  2045. #ifdef XFS_ALLOC_TRACE
  2046. static char fname[] = "xfs_alloc_put_freelist";
  2047. #endif
  2048. xfs_mount_t *mp; /* mount structure */
  2049. xfs_perag_t *pag; /* per allocation group data */
  2050. agf = XFS_BUF_TO_AGF(agbp);
  2051. mp = tp->t_mountp;
  2052. if (!agflbp && (error = xfs_alloc_read_agfl(mp, tp,
  2053. be32_to_cpu(agf->agf_seqno), &agflbp)))
  2054. return error;
  2055. agfl = XFS_BUF_TO_AGFL(agflbp);
  2056. be32_add(&agf->agf_fllast, 1);
  2057. if (be32_to_cpu(agf->agf_fllast) == XFS_AGFL_SIZE(mp))
  2058. agf->agf_fllast = 0;
  2059. pag = &mp->m_perag[be32_to_cpu(agf->agf_seqno)];
  2060. be32_add(&agf->agf_flcount, 1);
  2061. xfs_trans_agflist_delta(tp, 1);
  2062. pag->pagf_flcount++;
  2063. ASSERT(be32_to_cpu(agf->agf_flcount) <= XFS_AGFL_SIZE(mp));
  2064. blockp = &agfl->agfl_bno[be32_to_cpu(agf->agf_fllast)];
  2065. *blockp = cpu_to_be32(bno);
  2066. TRACE_MODAGF(NULL, agf, XFS_AGF_FLLAST | XFS_AGF_FLCOUNT);
  2067. xfs_alloc_log_agf(tp, agbp, XFS_AGF_FLLAST | XFS_AGF_FLCOUNT);
  2068. xfs_trans_log_buf(tp, agflbp,
  2069. (int)((xfs_caddr_t)blockp - (xfs_caddr_t)agfl),
  2070. (int)((xfs_caddr_t)blockp - (xfs_caddr_t)agfl +
  2071. sizeof(xfs_agblock_t) - 1));
  2072. return 0;
  2073. }
  2074. /*
  2075. * Read in the allocation group header (free/alloc section).
  2076. */
  2077. int /* error */
  2078. xfs_alloc_read_agf(
  2079. xfs_mount_t *mp, /* mount point structure */
  2080. xfs_trans_t *tp, /* transaction pointer */
  2081. xfs_agnumber_t agno, /* allocation group number */
  2082. int flags, /* XFS_ALLOC_FLAG_... */
  2083. xfs_buf_t **bpp) /* buffer for the ag freelist header */
  2084. {
  2085. xfs_agf_t *agf; /* ag freelist header */
  2086. int agf_ok; /* set if agf is consistent */
  2087. xfs_buf_t *bp; /* return value */
  2088. xfs_perag_t *pag; /* per allocation group data */
  2089. int error;
  2090. ASSERT(agno != NULLAGNUMBER);
  2091. error = xfs_trans_read_buf(
  2092. mp, tp, mp->m_ddev_targp,
  2093. XFS_AG_DADDR(mp, agno, XFS_AGF_DADDR(mp)),
  2094. XFS_FSS_TO_BB(mp, 1),
  2095. (flags & XFS_ALLOC_FLAG_TRYLOCK) ? XFS_BUF_TRYLOCK : 0U,
  2096. &bp);
  2097. if (error)
  2098. return error;
  2099. ASSERT(!bp || !XFS_BUF_GETERROR(bp));
  2100. if (!bp) {
  2101. *bpp = NULL;
  2102. return 0;
  2103. }
  2104. /*
  2105. * Validate the magic number of the agf block.
  2106. */
  2107. agf = XFS_BUF_TO_AGF(bp);
  2108. agf_ok =
  2109. be32_to_cpu(agf->agf_magicnum) == XFS_AGF_MAGIC &&
  2110. XFS_AGF_GOOD_VERSION(be32_to_cpu(agf->agf_versionnum)) &&
  2111. be32_to_cpu(agf->agf_freeblks) <= be32_to_cpu(agf->agf_length) &&
  2112. be32_to_cpu(agf->agf_flfirst) < XFS_AGFL_SIZE(mp) &&
  2113. be32_to_cpu(agf->agf_fllast) < XFS_AGFL_SIZE(mp) &&
  2114. be32_to_cpu(agf->agf_flcount) <= XFS_AGFL_SIZE(mp);
  2115. if (unlikely(XFS_TEST_ERROR(!agf_ok, mp, XFS_ERRTAG_ALLOC_READ_AGF,
  2116. XFS_RANDOM_ALLOC_READ_AGF))) {
  2117. XFS_CORRUPTION_ERROR("xfs_alloc_read_agf",
  2118. XFS_ERRLEVEL_LOW, mp, agf);
  2119. xfs_trans_brelse(tp, bp);
  2120. return XFS_ERROR(EFSCORRUPTED);
  2121. }
  2122. pag = &mp->m_perag[agno];
  2123. if (!pag->pagf_init) {
  2124. pag->pagf_freeblks = be32_to_cpu(agf->agf_freeblks);
  2125. pag->pagf_flcount = be32_to_cpu(agf->agf_flcount);
  2126. pag->pagf_longest = be32_to_cpu(agf->agf_longest);
  2127. pag->pagf_levels[XFS_BTNUM_BNOi] =
  2128. be32_to_cpu(agf->agf_levels[XFS_BTNUM_BNOi]);
  2129. pag->pagf_levels[XFS_BTNUM_CNTi] =
  2130. be32_to_cpu(agf->agf_levels[XFS_BTNUM_CNTi]);
  2131. spinlock_init(&pag->pagb_lock, "xfspagb");
  2132. pag->pagb_list = kmem_zalloc(XFS_PAGB_NUM_SLOTS *
  2133. sizeof(xfs_perag_busy_t), KM_SLEEP);
  2134. pag->pagf_init = 1;
  2135. }
  2136. #ifdef DEBUG
  2137. else if (!XFS_FORCED_SHUTDOWN(mp)) {
  2138. ASSERT(pag->pagf_freeblks == be32_to_cpu(agf->agf_freeblks));
  2139. ASSERT(pag->pagf_flcount == be32_to_cpu(agf->agf_flcount));
  2140. ASSERT(pag->pagf_longest == be32_to_cpu(agf->agf_longest));
  2141. ASSERT(pag->pagf_levels[XFS_BTNUM_BNOi] ==
  2142. be32_to_cpu(agf->agf_levels[XFS_BTNUM_BNOi]));
  2143. ASSERT(pag->pagf_levels[XFS_BTNUM_CNTi] ==
  2144. be32_to_cpu(agf->agf_levels[XFS_BTNUM_CNTi]));
  2145. }
  2146. #endif
  2147. XFS_BUF_SET_VTYPE_REF(bp, B_FS_AGF, XFS_AGF_REF);
  2148. *bpp = bp;
  2149. return 0;
  2150. }
  2151. /*
  2152. * Allocate an extent (variable-size).
  2153. * Depending on the allocation type, we either look in a single allocation
  2154. * group or loop over the allocation groups to find the result.
  2155. */
  2156. int /* error */
  2157. xfs_alloc_vextent(
  2158. xfs_alloc_arg_t *args) /* allocation argument structure */
  2159. {
  2160. xfs_agblock_t agsize; /* allocation group size */
  2161. int error;
  2162. int flags; /* XFS_ALLOC_FLAG_... locking flags */
  2163. #ifdef XFS_ALLOC_TRACE
  2164. static char fname[] = "xfs_alloc_vextent";
  2165. #endif
  2166. xfs_extlen_t minleft;/* minimum left value, temp copy */
  2167. xfs_mount_t *mp; /* mount structure pointer */
  2168. xfs_agnumber_t sagno; /* starting allocation group number */
  2169. xfs_alloctype_t type; /* input allocation type */
  2170. int bump_rotor = 0;
  2171. int no_min = 0;
  2172. xfs_agnumber_t rotorstep = xfs_rotorstep; /* inode32 agf stepper */
  2173. mp = args->mp;
  2174. type = args->otype = args->type;
  2175. args->agbno = NULLAGBLOCK;
  2176. /*
  2177. * Just fix this up, for the case where the last a.g. is shorter
  2178. * (or there's only one a.g.) and the caller couldn't easily figure
  2179. * that out (xfs_bmap_alloc).
  2180. */
  2181. agsize = mp->m_sb.sb_agblocks;
  2182. if (args->maxlen > agsize)
  2183. args->maxlen = agsize;
  2184. if (args->alignment == 0)
  2185. args->alignment = 1;
  2186. ASSERT(XFS_FSB_TO_AGNO(mp, args->fsbno) < mp->m_sb.sb_agcount);
  2187. ASSERT(XFS_FSB_TO_AGBNO(mp, args->fsbno) < agsize);
  2188. ASSERT(args->minlen <= args->maxlen);
  2189. ASSERT(args->minlen <= agsize);
  2190. ASSERT(args->mod < args->prod);
  2191. if (XFS_FSB_TO_AGNO(mp, args->fsbno) >= mp->m_sb.sb_agcount ||
  2192. XFS_FSB_TO_AGBNO(mp, args->fsbno) >= agsize ||
  2193. args->minlen > args->maxlen || args->minlen > agsize ||
  2194. args->mod >= args->prod) {
  2195. args->fsbno = NULLFSBLOCK;
  2196. TRACE_ALLOC("badargs", args);
  2197. return 0;
  2198. }
  2199. minleft = args->minleft;
  2200. switch (type) {
  2201. case XFS_ALLOCTYPE_THIS_AG:
  2202. case XFS_ALLOCTYPE_NEAR_BNO:
  2203. case XFS_ALLOCTYPE_THIS_BNO:
  2204. /*
  2205. * These three force us into a single a.g.
  2206. */
  2207. args->agno = XFS_FSB_TO_AGNO(mp, args->fsbno);
  2208. down_read(&mp->m_peraglock);
  2209. args->pag = &mp->m_perag[args->agno];
  2210. args->minleft = 0;
  2211. error = xfs_alloc_fix_freelist(args, 0);
  2212. args->minleft = minleft;
  2213. if (error) {
  2214. TRACE_ALLOC("nofix", args);
  2215. goto error0;
  2216. }
  2217. if (!args->agbp) {
  2218. up_read(&mp->m_peraglock);
  2219. TRACE_ALLOC("noagbp", args);
  2220. break;
  2221. }
  2222. args->agbno = XFS_FSB_TO_AGBNO(mp, args->fsbno);
  2223. if ((error = xfs_alloc_ag_vextent(args)))
  2224. goto error0;
  2225. up_read(&mp->m_peraglock);
  2226. break;
  2227. case XFS_ALLOCTYPE_START_BNO:
  2228. /*
  2229. * Try near allocation first, then anywhere-in-ag after
  2230. * the first a.g. fails.
  2231. */
  2232. if ((args->userdata == XFS_ALLOC_INITIAL_USER_DATA) &&
  2233. (mp->m_flags & XFS_MOUNT_32BITINODES)) {
  2234. args->fsbno = XFS_AGB_TO_FSB(mp,
  2235. ((mp->m_agfrotor / rotorstep) %
  2236. mp->m_sb.sb_agcount), 0);
  2237. bump_rotor = 1;
  2238. }
  2239. args->agbno = XFS_FSB_TO_AGBNO(mp, args->fsbno);
  2240. args->type = XFS_ALLOCTYPE_NEAR_BNO;
  2241. /* FALLTHROUGH */
  2242. case XFS_ALLOCTYPE_ANY_AG:
  2243. case XFS_ALLOCTYPE_START_AG:
  2244. case XFS_ALLOCTYPE_FIRST_AG:
  2245. /*
  2246. * Rotate through the allocation groups looking for a winner.
  2247. */
  2248. if (type == XFS_ALLOCTYPE_ANY_AG) {
  2249. /*
  2250. * Start with the last place we left off.
  2251. */
  2252. args->agno = sagno = (mp->m_agfrotor / rotorstep) %
  2253. mp->m_sb.sb_agcount;
  2254. args->type = XFS_ALLOCTYPE_THIS_AG;
  2255. flags = XFS_ALLOC_FLAG_TRYLOCK;
  2256. } else if (type == XFS_ALLOCTYPE_FIRST_AG) {
  2257. /*
  2258. * Start with allocation group given by bno.
  2259. */
  2260. args->agno = XFS_FSB_TO_AGNO(mp, args->fsbno);
  2261. args->type = XFS_ALLOCTYPE_THIS_AG;
  2262. sagno = 0;
  2263. flags = 0;
  2264. } else {
  2265. if (type == XFS_ALLOCTYPE_START_AG)
  2266. args->type = XFS_ALLOCTYPE_THIS_AG;
  2267. /*
  2268. * Start with the given allocation group.
  2269. */
  2270. args->agno = sagno = XFS_FSB_TO_AGNO(mp, args->fsbno);
  2271. flags = XFS_ALLOC_FLAG_TRYLOCK;
  2272. }
  2273. /*
  2274. * Loop over allocation groups twice; first time with
  2275. * trylock set, second time without.
  2276. */
  2277. down_read(&mp->m_peraglock);
  2278. for (;;) {
  2279. args->pag = &mp->m_perag[args->agno];
  2280. if (no_min) args->minleft = 0;
  2281. error = xfs_alloc_fix_freelist(args, flags);
  2282. args->minleft = minleft;
  2283. if (error) {
  2284. TRACE_ALLOC("nofix", args);
  2285. goto error0;
  2286. }
  2287. /*
  2288. * If we get a buffer back then the allocation will fly.
  2289. */
  2290. if (args->agbp) {
  2291. if ((error = xfs_alloc_ag_vextent(args)))
  2292. goto error0;
  2293. break;
  2294. }
  2295. TRACE_ALLOC("loopfailed", args);
  2296. /*
  2297. * Didn't work, figure out the next iteration.
  2298. */
  2299. if (args->agno == sagno &&
  2300. type == XFS_ALLOCTYPE_START_BNO)
  2301. args->type = XFS_ALLOCTYPE_THIS_AG;
  2302. /*
  2303. * For the first allocation, we can try any AG to get
  2304. * space. However, if we already have allocated a
  2305. * block, we don't want to try AGs whose number is below
  2306. * sagno. Otherwise, we may end up with out-of-order
  2307. * locking of AGF, which might cause deadlock.
  2308. */
  2309. if (++(args->agno) == mp->m_sb.sb_agcount) {
  2310. if (args->firstblock != NULLFSBLOCK)
  2311. args->agno = sagno;
  2312. else
  2313. args->agno = 0;
  2314. }
  2315. /*
  2316. * Reached the starting a.g., must either be done
  2317. * or switch to non-trylock mode.
  2318. */
  2319. if (args->agno == sagno) {
  2320. if (no_min == 1) {
  2321. args->agbno = NULLAGBLOCK;
  2322. TRACE_ALLOC("allfailed", args);
  2323. break;
  2324. }
  2325. if (flags == 0) {
  2326. no_min = 1;
  2327. } else {
  2328. flags = 0;
  2329. if (type == XFS_ALLOCTYPE_START_BNO) {
  2330. args->agbno = XFS_FSB_TO_AGBNO(mp,
  2331. args->fsbno);
  2332. args->type = XFS_ALLOCTYPE_NEAR_BNO;
  2333. }
  2334. }
  2335. }
  2336. }
  2337. up_read(&mp->m_peraglock);
  2338. if (bump_rotor || (type == XFS_ALLOCTYPE_ANY_AG)) {
  2339. if (args->agno == sagno)
  2340. mp->m_agfrotor = (mp->m_agfrotor + 1) %
  2341. (mp->m_sb.sb_agcount * rotorstep);
  2342. else
  2343. mp->m_agfrotor = (args->agno * rotorstep + 1) %
  2344. (mp->m_sb.sb_agcount * rotorstep);
  2345. }
  2346. break;
  2347. default:
  2348. ASSERT(0);
  2349. /* NOTREACHED */
  2350. }
  2351. if (args->agbno == NULLAGBLOCK)
  2352. args->fsbno = NULLFSBLOCK;
  2353. else {
  2354. args->fsbno = XFS_AGB_TO_FSB(mp, args->agno, args->agbno);
  2355. #ifdef DEBUG
  2356. ASSERT(args->len >= args->minlen);
  2357. ASSERT(args->len <= args->maxlen);
  2358. ASSERT(args->agbno % args->alignment == 0);
  2359. XFS_AG_CHECK_DADDR(mp, XFS_FSB_TO_DADDR(mp, args->fsbno),
  2360. args->len);
  2361. #endif
  2362. }
  2363. return 0;
  2364. error0:
  2365. up_read(&mp->m_peraglock);
  2366. return error;
  2367. }
  2368. /*
  2369. * Free an extent.
  2370. * Just break up the extent address and hand off to xfs_free_ag_extent
  2371. * after fixing up the freelist.
  2372. */
  2373. int /* error */
  2374. xfs_free_extent(
  2375. xfs_trans_t *tp, /* transaction pointer */
  2376. xfs_fsblock_t bno, /* starting block number of extent */
  2377. xfs_extlen_t len) /* length of extent */
  2378. {
  2379. xfs_alloc_arg_t args;
  2380. int error;
  2381. ASSERT(len != 0);
  2382. memset(&args, 0, sizeof(xfs_alloc_arg_t));
  2383. args.tp = tp;
  2384. args.mp = tp->t_mountp;
  2385. args.agno = XFS_FSB_TO_AGNO(args.mp, bno);
  2386. ASSERT(args.agno < args.mp->m_sb.sb_agcount);
  2387. args.agbno = XFS_FSB_TO_AGBNO(args.mp, bno);
  2388. down_read(&args.mp->m_peraglock);
  2389. args.pag = &args.mp->m_perag[args.agno];
  2390. if ((error = xfs_alloc_fix_freelist(&args, XFS_ALLOC_FLAG_FREEING)))
  2391. goto error0;
  2392. #ifdef DEBUG
  2393. ASSERT(args.agbp != NULL);
  2394. ASSERT((args.agbno + len) <=
  2395. be32_to_cpu(XFS_BUF_TO_AGF(args.agbp)->agf_length));
  2396. #endif
  2397. error = xfs_free_ag_extent(tp, args.agbp, args.agno, args.agbno, len, 0);
  2398. error0:
  2399. up_read(&args.mp->m_peraglock);
  2400. return error;
  2401. }
  2402. /*
  2403. * AG Busy list management
  2404. * The busy list contains block ranges that have been freed but whose
  2405. * transactions have not yet hit disk. If any block listed in a busy
  2406. * list is reused, the transaction that freed it must be forced to disk
  2407. * before continuing to use the block.
  2408. *
  2409. * xfs_alloc_mark_busy - add to the per-ag busy list
  2410. * xfs_alloc_clear_busy - remove an item from the per-ag busy list
  2411. */
  2412. void
  2413. xfs_alloc_mark_busy(xfs_trans_t *tp,
  2414. xfs_agnumber_t agno,
  2415. xfs_agblock_t bno,
  2416. xfs_extlen_t len)
  2417. {
  2418. xfs_mount_t *mp;
  2419. xfs_perag_busy_t *bsy;
  2420. int n;
  2421. SPLDECL(s);
  2422. mp = tp->t_mountp;
  2423. s = mutex_spinlock(&mp->m_perag[agno].pagb_lock);
  2424. /* search pagb_list for an open slot */
  2425. for (bsy = mp->m_perag[agno].pagb_list, n = 0;
  2426. n < XFS_PAGB_NUM_SLOTS;
  2427. bsy++, n++) {
  2428. if (bsy->busy_tp == NULL) {
  2429. break;
  2430. }
  2431. }
  2432. if (n < XFS_PAGB_NUM_SLOTS) {
  2433. bsy = &mp->m_perag[agno].pagb_list[n];
  2434. mp->m_perag[agno].pagb_count++;
  2435. TRACE_BUSY("xfs_alloc_mark_busy", "got", agno, bno, len, n, tp);
  2436. bsy->busy_start = bno;
  2437. bsy->busy_length = len;
  2438. bsy->busy_tp = tp;
  2439. xfs_trans_add_busy(tp, agno, n);
  2440. } else {
  2441. TRACE_BUSY("xfs_alloc_mark_busy", "FULL", agno, bno, len, -1, tp);
  2442. /*
  2443. * The busy list is full! Since it is now not possible to
  2444. * track the free block, make this a synchronous transaction
  2445. * to insure that the block is not reused before this
  2446. * transaction commits.
  2447. */
  2448. xfs_trans_set_sync(tp);
  2449. }
  2450. mutex_spinunlock(&mp->m_perag[agno].pagb_lock, s);
  2451. }
  2452. void
  2453. xfs_alloc_clear_busy(xfs_trans_t *tp,
  2454. xfs_agnumber_t agno,
  2455. int idx)
  2456. {
  2457. xfs_mount_t *mp;
  2458. xfs_perag_busy_t *list;
  2459. SPLDECL(s);
  2460. mp = tp->t_mountp;
  2461. s = mutex_spinlock(&mp->m_perag[agno].pagb_lock);
  2462. list = mp->m_perag[agno].pagb_list;
  2463. ASSERT(idx < XFS_PAGB_NUM_SLOTS);
  2464. if (list[idx].busy_tp == tp) {
  2465. TRACE_UNBUSY("xfs_alloc_clear_busy", "found", agno, idx, tp);
  2466. list[idx].busy_tp = NULL;
  2467. mp->m_perag[agno].pagb_count--;
  2468. } else {
  2469. TRACE_UNBUSY("xfs_alloc_clear_busy", "missing", agno, idx, tp);
  2470. }
  2471. mutex_spinunlock(&mp->m_perag[agno].pagb_lock, s);
  2472. }
  2473. /*
  2474. * returns non-zero if any of (agno,bno):len is in a busy list
  2475. */
  2476. STATIC int
  2477. xfs_alloc_search_busy(xfs_trans_t *tp,
  2478. xfs_agnumber_t agno,
  2479. xfs_agblock_t bno,
  2480. xfs_extlen_t len)
  2481. {
  2482. xfs_mount_t *mp;
  2483. xfs_perag_busy_t *bsy;
  2484. int n;
  2485. xfs_agblock_t uend, bend;
  2486. xfs_lsn_t lsn;
  2487. int cnt;
  2488. SPLDECL(s);
  2489. mp = tp->t_mountp;
  2490. s = mutex_spinlock(&mp->m_perag[agno].pagb_lock);
  2491. cnt = mp->m_perag[agno].pagb_count;
  2492. uend = bno + len - 1;
  2493. /* search pagb_list for this slot, skipping open slots */
  2494. for (bsy = mp->m_perag[agno].pagb_list, n = 0;
  2495. cnt; bsy++, n++) {
  2496. /*
  2497. * (start1,length1) within (start2, length2)
  2498. */
  2499. if (bsy->busy_tp != NULL) {
  2500. bend = bsy->busy_start + bsy->busy_length - 1;
  2501. if ((bno > bend) ||
  2502. (uend < bsy->busy_start)) {
  2503. cnt--;
  2504. } else {
  2505. TRACE_BUSYSEARCH("xfs_alloc_search_busy",
  2506. "found1", agno, bno, len, n,
  2507. tp);
  2508. break;
  2509. }
  2510. }
  2511. }
  2512. /*
  2513. * If a block was found, force the log through the LSN of the
  2514. * transaction that freed the block
  2515. */
  2516. if (cnt) {
  2517. TRACE_BUSYSEARCH("xfs_alloc_search_busy", "found", agno, bno, len, n, tp);
  2518. lsn = bsy->busy_tp->t_commit_lsn;
  2519. mutex_spinunlock(&mp->m_perag[agno].pagb_lock, s);
  2520. xfs_log_force(mp, lsn, XFS_LOG_FORCE|XFS_LOG_SYNC);
  2521. } else {
  2522. TRACE_BUSYSEARCH("xfs_alloc_search_busy", "not-found", agno, bno, len, n, tp);
  2523. n = -1;
  2524. mutex_spinunlock(&mp->m_perag[agno].pagb_lock, s);
  2525. }
  2526. return n;
  2527. }