xfs_alloc.c 83 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768176917701771177217731774177517761777177817791780178117821783178417851786178717881789179017911792179317941795179617971798179918001801180218031804180518061807180818091810181118121813181418151816181718181819182018211822182318241825182618271828182918301831183218331834183518361837183818391840184118421843184418451846184718481849185018511852185318541855185618571858185918601861186218631864186518661867186818691870187118721873187418751876187718781879188018811882188318841885188618871888188918901891189218931894189518961897189818991900190119021903190419051906190719081909191019111912191319141915191619171918191919201921192219231924192519261927192819291930193119321933193419351936193719381939194019411942194319441945194619471948194919501951195219531954195519561957195819591960196119621963196419651966196719681969197019711972197319741975197619771978197919801981198219831984198519861987198819891990199119921993199419951996199719981999200020012002200320042005200620072008200920102011201220132014201520162017201820192020202120222023202420252026202720282029203020312032203320342035203620372038203920402041204220432044204520462047204820492050205120522053205420552056205720582059206020612062206320642065206620672068206920702071207220732074207520762077207820792080208120822083208420852086208720882089209020912092209320942095209620972098209921002101210221032104210521062107210821092110211121122113211421152116211721182119212021212122212321242125212621272128212921302131213221332134213521362137213821392140214121422143214421452146214721482149215021512152215321542155215621572158215921602161216221632164216521662167216821692170217121722173217421752176217721782179218021812182218321842185218621872188218921902191219221932194219521962197219821992200220122022203220422052206220722082209221022112212221322142215221622172218221922202221222222232224222522262227222822292230223122322233223422352236223722382239224022412242224322442245224622472248224922502251225222532254225522562257225822592260226122622263226422652266226722682269227022712272227322742275227622772278227922802281228222832284228522862287228822892290229122922293229422952296229722982299230023012302230323042305230623072308230923102311231223132314231523162317231823192320232123222323232423252326232723282329233023312332233323342335233623372338233923402341234223432344234523462347234823492350235123522353235423552356235723582359236023612362236323642365236623672368236923702371237223732374237523762377237823792380238123822383238423852386238723882389239023912392239323942395239623972398239924002401240224032404240524062407240824092410241124122413241424152416241724182419242024212422242324242425242624272428242924302431243224332434243524362437243824392440244124422443244424452446244724482449245024512452245324542455245624572458245924602461246224632464246524662467246824692470247124722473247424752476247724782479248024812482248324842485248624872488248924902491249224932494249524962497249824992500250125022503250425052506250725082509251025112512251325142515251625172518251925202521252225232524252525262527252825292530253125322533253425352536253725382539254025412542254325442545254625472548254925502551255225532554255525562557255825592560256125622563256425652566256725682569257025712572257325742575257625772578257925802581258225832584258525862587258825892590259125922593259425952596259725982599260026012602260326042605260626072608260926102611261226132614261526162617261826192620262126222623262426252626262726282629263026312632263326342635263626372638263926402641264226432644264526462647264826492650265126522653265426552656265726582659266026612662266326642665266626672668266926702671267226732674267526762677267826792680268126822683268426852686268726882689269026912692269326942695269626972698269927002701270227032704270527062707270827092710271127122713271427152716271727182719272027212722272327242725272627272728272927302731273227332734273527362737273827392740274127422743274427452746274727482749275027512752275327542755275627572758275927602761276227632764276527662767276827692770277127722773277427752776277727782779278027812782278327842785278627872788278927902791279227932794279527962797279827992800280128022803280428052806280728082809281028112812281328142815281628172818281928202821282228232824282528262827282828292830283128322833283428352836283728382839284028412842284328442845284628472848284928502851285228532854285528562857285828592860286128622863286428652866286728682869287028712872287328742875287628772878287928802881288228832884288528862887288828892890289128922893289428952896289728982899290029012902290329042905290629072908290929102911291229132914291529162917291829192920292129222923292429252926292729282929293029312932293329342935293629372938293929402941294229432944294529462947294829492950295129522953295429552956295729582959296029612962296329642965296629672968296929702971297229732974297529762977297829792980298129822983298429852986298729882989299029912992299329942995299629972998299930003001300230033004300530063007300830093010301130123013301430153016301730183019302030213022302330243025302630273028302930303031303230333034303530363037303830393040304130423043304430453046304730483049305030513052305330543055305630573058305930603061306230633064306530663067306830693070307130723073
  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_trans.h"
  24. #include "xfs_sb.h"
  25. #include "xfs_ag.h"
  26. #include "xfs_mount.h"
  27. #include "xfs_bmap_btree.h"
  28. #include "xfs_alloc_btree.h"
  29. #include "xfs_ialloc_btree.h"
  30. #include "xfs_dinode.h"
  31. #include "xfs_inode.h"
  32. #include "xfs_btree.h"
  33. #include "xfs_alloc.h"
  34. #include "xfs_error.h"
  35. #include "xfs_trace.h"
  36. struct workqueue_struct *xfs_alloc_wq;
  37. #define XFS_ABSDIFF(a,b) (((a) <= (b)) ? ((b) - (a)) : ((a) - (b)))
  38. #define XFSA_FIXUP_BNO_OK 1
  39. #define XFSA_FIXUP_CNT_OK 2
  40. STATIC int xfs_alloc_ag_vextent_exact(xfs_alloc_arg_t *);
  41. STATIC int xfs_alloc_ag_vextent_near(xfs_alloc_arg_t *);
  42. STATIC int xfs_alloc_ag_vextent_size(xfs_alloc_arg_t *);
  43. STATIC int xfs_alloc_ag_vextent_small(xfs_alloc_arg_t *,
  44. xfs_btree_cur_t *, xfs_agblock_t *, xfs_extlen_t *, int *);
  45. STATIC void xfs_alloc_busy_trim(struct xfs_alloc_arg *,
  46. xfs_agblock_t, xfs_extlen_t, xfs_agblock_t *, xfs_extlen_t *);
  47. /*
  48. * Lookup the record equal to [bno, len] in the btree given by cur.
  49. */
  50. STATIC int /* error */
  51. xfs_alloc_lookup_eq(
  52. struct xfs_btree_cur *cur, /* btree cursor */
  53. xfs_agblock_t bno, /* starting block of extent */
  54. xfs_extlen_t len, /* length of extent */
  55. int *stat) /* success/failure */
  56. {
  57. cur->bc_rec.a.ar_startblock = bno;
  58. cur->bc_rec.a.ar_blockcount = len;
  59. return xfs_btree_lookup(cur, XFS_LOOKUP_EQ, stat);
  60. }
  61. /*
  62. * Lookup the first record greater than or equal to [bno, len]
  63. * in the btree given by cur.
  64. */
  65. int /* error */
  66. xfs_alloc_lookup_ge(
  67. struct xfs_btree_cur *cur, /* btree cursor */
  68. xfs_agblock_t bno, /* starting block of extent */
  69. xfs_extlen_t len, /* length of extent */
  70. int *stat) /* success/failure */
  71. {
  72. cur->bc_rec.a.ar_startblock = bno;
  73. cur->bc_rec.a.ar_blockcount = len;
  74. return xfs_btree_lookup(cur, XFS_LOOKUP_GE, stat);
  75. }
  76. /*
  77. * Lookup the first record less than or equal to [bno, len]
  78. * in the btree given by cur.
  79. */
  80. int /* error */
  81. xfs_alloc_lookup_le(
  82. struct xfs_btree_cur *cur, /* btree cursor */
  83. xfs_agblock_t bno, /* starting block of extent */
  84. xfs_extlen_t len, /* length of extent */
  85. int *stat) /* success/failure */
  86. {
  87. cur->bc_rec.a.ar_startblock = bno;
  88. cur->bc_rec.a.ar_blockcount = len;
  89. return xfs_btree_lookup(cur, XFS_LOOKUP_LE, stat);
  90. }
  91. /*
  92. * Update the record referred to by cur to the value given
  93. * by [bno, len].
  94. * This either works (return 0) or gets an EFSCORRUPTED error.
  95. */
  96. STATIC int /* error */
  97. xfs_alloc_update(
  98. struct xfs_btree_cur *cur, /* btree cursor */
  99. xfs_agblock_t bno, /* starting block of extent */
  100. xfs_extlen_t len) /* length of extent */
  101. {
  102. union xfs_btree_rec rec;
  103. rec.alloc.ar_startblock = cpu_to_be32(bno);
  104. rec.alloc.ar_blockcount = cpu_to_be32(len);
  105. return xfs_btree_update(cur, &rec);
  106. }
  107. /*
  108. * Get the data from the pointed-to record.
  109. */
  110. int /* error */
  111. xfs_alloc_get_rec(
  112. struct xfs_btree_cur *cur, /* btree cursor */
  113. xfs_agblock_t *bno, /* output: starting block of extent */
  114. xfs_extlen_t *len, /* output: length of extent */
  115. int *stat) /* output: success/failure */
  116. {
  117. union xfs_btree_rec *rec;
  118. int error;
  119. error = xfs_btree_get_rec(cur, &rec, stat);
  120. if (!error && *stat == 1) {
  121. *bno = be32_to_cpu(rec->alloc.ar_startblock);
  122. *len = be32_to_cpu(rec->alloc.ar_blockcount);
  123. }
  124. return error;
  125. }
  126. /*
  127. * Compute aligned version of the found extent.
  128. * Takes alignment and min length into account.
  129. */
  130. STATIC void
  131. xfs_alloc_compute_aligned(
  132. xfs_alloc_arg_t *args, /* allocation argument structure */
  133. xfs_agblock_t foundbno, /* starting block in found extent */
  134. xfs_extlen_t foundlen, /* length in found extent */
  135. xfs_agblock_t *resbno, /* result block number */
  136. xfs_extlen_t *reslen) /* result length */
  137. {
  138. xfs_agblock_t bno;
  139. xfs_extlen_t len;
  140. /* Trim busy sections out of found extent */
  141. xfs_alloc_busy_trim(args, foundbno, foundlen, &bno, &len);
  142. if (args->alignment > 1 && len >= args->minlen) {
  143. xfs_agblock_t aligned_bno = roundup(bno, args->alignment);
  144. xfs_extlen_t diff = aligned_bno - bno;
  145. *resbno = aligned_bno;
  146. *reslen = diff >= len ? 0 : len - diff;
  147. } else {
  148. *resbno = bno;
  149. *reslen = len;
  150. }
  151. }
  152. /*
  153. * Compute best start block and diff for "near" allocations.
  154. * freelen >= wantlen already checked by caller.
  155. */
  156. STATIC xfs_extlen_t /* difference value (absolute) */
  157. xfs_alloc_compute_diff(
  158. xfs_agblock_t wantbno, /* target starting block */
  159. xfs_extlen_t wantlen, /* target length */
  160. xfs_extlen_t alignment, /* target alignment */
  161. xfs_agblock_t freebno, /* freespace's starting block */
  162. xfs_extlen_t freelen, /* freespace's length */
  163. xfs_agblock_t *newbnop) /* result: best start block from free */
  164. {
  165. xfs_agblock_t freeend; /* end of freespace extent */
  166. xfs_agblock_t newbno1; /* return block number */
  167. xfs_agblock_t newbno2; /* other new block number */
  168. xfs_extlen_t newlen1=0; /* length with newbno1 */
  169. xfs_extlen_t newlen2=0; /* length with newbno2 */
  170. xfs_agblock_t wantend; /* end of target extent */
  171. ASSERT(freelen >= wantlen);
  172. freeend = freebno + freelen;
  173. wantend = wantbno + wantlen;
  174. if (freebno >= wantbno) {
  175. if ((newbno1 = roundup(freebno, alignment)) >= freeend)
  176. newbno1 = NULLAGBLOCK;
  177. } else if (freeend >= wantend && alignment > 1) {
  178. newbno1 = roundup(wantbno, alignment);
  179. newbno2 = newbno1 - alignment;
  180. if (newbno1 >= freeend)
  181. newbno1 = NULLAGBLOCK;
  182. else
  183. newlen1 = XFS_EXTLEN_MIN(wantlen, freeend - newbno1);
  184. if (newbno2 < freebno)
  185. newbno2 = NULLAGBLOCK;
  186. else
  187. newlen2 = XFS_EXTLEN_MIN(wantlen, freeend - newbno2);
  188. if (newbno1 != NULLAGBLOCK && newbno2 != NULLAGBLOCK) {
  189. if (newlen1 < newlen2 ||
  190. (newlen1 == newlen2 &&
  191. XFS_ABSDIFF(newbno1, wantbno) >
  192. XFS_ABSDIFF(newbno2, wantbno)))
  193. newbno1 = newbno2;
  194. } else if (newbno2 != NULLAGBLOCK)
  195. newbno1 = newbno2;
  196. } else if (freeend >= wantend) {
  197. newbno1 = wantbno;
  198. } else if (alignment > 1) {
  199. newbno1 = roundup(freeend - wantlen, alignment);
  200. if (newbno1 > freeend - wantlen &&
  201. newbno1 - alignment >= freebno)
  202. newbno1 -= alignment;
  203. else if (newbno1 >= freeend)
  204. newbno1 = NULLAGBLOCK;
  205. } else
  206. newbno1 = freeend - wantlen;
  207. *newbnop = newbno1;
  208. return newbno1 == NULLAGBLOCK ? 0 : XFS_ABSDIFF(newbno1, wantbno);
  209. }
  210. /*
  211. * Fix up the length, based on mod and prod.
  212. * len should be k * prod + mod for some k.
  213. * If len is too small it is returned unchanged.
  214. * If len hits maxlen it is left alone.
  215. */
  216. STATIC void
  217. xfs_alloc_fix_len(
  218. xfs_alloc_arg_t *args) /* allocation argument structure */
  219. {
  220. xfs_extlen_t k;
  221. xfs_extlen_t rlen;
  222. ASSERT(args->mod < args->prod);
  223. rlen = args->len;
  224. ASSERT(rlen >= args->minlen);
  225. ASSERT(rlen <= args->maxlen);
  226. if (args->prod <= 1 || rlen < args->mod || rlen == args->maxlen ||
  227. (args->mod == 0 && rlen < args->prod))
  228. return;
  229. k = rlen % args->prod;
  230. if (k == args->mod)
  231. return;
  232. if (k > args->mod) {
  233. if ((int)(rlen = rlen - k - args->mod) < (int)args->minlen)
  234. return;
  235. } else {
  236. if ((int)(rlen = rlen - args->prod - (args->mod - k)) <
  237. (int)args->minlen)
  238. return;
  239. }
  240. ASSERT(rlen >= args->minlen);
  241. ASSERT(rlen <= args->maxlen);
  242. args->len = rlen;
  243. }
  244. /*
  245. * Fix up length if there is too little space left in the a.g.
  246. * Return 1 if ok, 0 if too little, should give up.
  247. */
  248. STATIC int
  249. xfs_alloc_fix_minleft(
  250. xfs_alloc_arg_t *args) /* allocation argument structure */
  251. {
  252. xfs_agf_t *agf; /* a.g. freelist header */
  253. int diff; /* free space difference */
  254. if (args->minleft == 0)
  255. return 1;
  256. agf = XFS_BUF_TO_AGF(args->agbp);
  257. diff = be32_to_cpu(agf->agf_freeblks)
  258. - args->len - args->minleft;
  259. if (diff >= 0)
  260. return 1;
  261. args->len += diff; /* shrink the allocated space */
  262. if (args->len >= args->minlen)
  263. return 1;
  264. args->agbno = NULLAGBLOCK;
  265. return 0;
  266. }
  267. /*
  268. * Update the two btrees, logically removing from freespace the extent
  269. * starting at rbno, rlen blocks. The extent is contained within the
  270. * actual (current) free extent fbno for flen blocks.
  271. * Flags are passed in indicating whether the cursors are set to the
  272. * relevant records.
  273. */
  274. STATIC int /* error code */
  275. xfs_alloc_fixup_trees(
  276. xfs_btree_cur_t *cnt_cur, /* cursor for by-size btree */
  277. xfs_btree_cur_t *bno_cur, /* cursor for by-block btree */
  278. xfs_agblock_t fbno, /* starting block of free extent */
  279. xfs_extlen_t flen, /* length of free extent */
  280. xfs_agblock_t rbno, /* starting block of returned extent */
  281. xfs_extlen_t rlen, /* length of returned extent */
  282. int flags) /* flags, XFSA_FIXUP_... */
  283. {
  284. int error; /* error code */
  285. int i; /* operation results */
  286. xfs_agblock_t nfbno1; /* first new free startblock */
  287. xfs_agblock_t nfbno2; /* second new free startblock */
  288. xfs_extlen_t nflen1=0; /* first new free length */
  289. xfs_extlen_t nflen2=0; /* second new free length */
  290. /*
  291. * Look up the record in the by-size tree if necessary.
  292. */
  293. if (flags & XFSA_FIXUP_CNT_OK) {
  294. #ifdef DEBUG
  295. if ((error = xfs_alloc_get_rec(cnt_cur, &nfbno1, &nflen1, &i)))
  296. return error;
  297. XFS_WANT_CORRUPTED_RETURN(
  298. i == 1 && nfbno1 == fbno && nflen1 == flen);
  299. #endif
  300. } else {
  301. if ((error = xfs_alloc_lookup_eq(cnt_cur, fbno, flen, &i)))
  302. return error;
  303. XFS_WANT_CORRUPTED_RETURN(i == 1);
  304. }
  305. /*
  306. * Look up the record in the by-block tree if necessary.
  307. */
  308. if (flags & XFSA_FIXUP_BNO_OK) {
  309. #ifdef DEBUG
  310. if ((error = xfs_alloc_get_rec(bno_cur, &nfbno1, &nflen1, &i)))
  311. return error;
  312. XFS_WANT_CORRUPTED_RETURN(
  313. i == 1 && nfbno1 == fbno && nflen1 == flen);
  314. #endif
  315. } else {
  316. if ((error = xfs_alloc_lookup_eq(bno_cur, fbno, flen, &i)))
  317. return error;
  318. XFS_WANT_CORRUPTED_RETURN(i == 1);
  319. }
  320. #ifdef DEBUG
  321. if (bno_cur->bc_nlevels == 1 && cnt_cur->bc_nlevels == 1) {
  322. struct xfs_btree_block *bnoblock;
  323. struct xfs_btree_block *cntblock;
  324. bnoblock = XFS_BUF_TO_BLOCK(bno_cur->bc_bufs[0]);
  325. cntblock = XFS_BUF_TO_BLOCK(cnt_cur->bc_bufs[0]);
  326. XFS_WANT_CORRUPTED_RETURN(
  327. bnoblock->bb_numrecs == cntblock->bb_numrecs);
  328. }
  329. #endif
  330. /*
  331. * Deal with all four cases: the allocated record is contained
  332. * within the freespace record, so we can have new freespace
  333. * at either (or both) end, or no freespace remaining.
  334. */
  335. if (rbno == fbno && rlen == flen)
  336. nfbno1 = nfbno2 = NULLAGBLOCK;
  337. else if (rbno == fbno) {
  338. nfbno1 = rbno + rlen;
  339. nflen1 = flen - rlen;
  340. nfbno2 = NULLAGBLOCK;
  341. } else if (rbno + rlen == fbno + flen) {
  342. nfbno1 = fbno;
  343. nflen1 = flen - rlen;
  344. nfbno2 = NULLAGBLOCK;
  345. } else {
  346. nfbno1 = fbno;
  347. nflen1 = rbno - fbno;
  348. nfbno2 = rbno + rlen;
  349. nflen2 = (fbno + flen) - nfbno2;
  350. }
  351. /*
  352. * Delete the entry from the by-size btree.
  353. */
  354. if ((error = xfs_btree_delete(cnt_cur, &i)))
  355. return error;
  356. XFS_WANT_CORRUPTED_RETURN(i == 1);
  357. /*
  358. * Add new by-size btree entry(s).
  359. */
  360. if (nfbno1 != NULLAGBLOCK) {
  361. if ((error = xfs_alloc_lookup_eq(cnt_cur, nfbno1, nflen1, &i)))
  362. return error;
  363. XFS_WANT_CORRUPTED_RETURN(i == 0);
  364. if ((error = xfs_btree_insert(cnt_cur, &i)))
  365. return error;
  366. XFS_WANT_CORRUPTED_RETURN(i == 1);
  367. }
  368. if (nfbno2 != NULLAGBLOCK) {
  369. if ((error = xfs_alloc_lookup_eq(cnt_cur, nfbno2, nflen2, &i)))
  370. return error;
  371. XFS_WANT_CORRUPTED_RETURN(i == 0);
  372. if ((error = xfs_btree_insert(cnt_cur, &i)))
  373. return error;
  374. XFS_WANT_CORRUPTED_RETURN(i == 1);
  375. }
  376. /*
  377. * Fix up the by-block btree entry(s).
  378. */
  379. if (nfbno1 == NULLAGBLOCK) {
  380. /*
  381. * No remaining freespace, just delete the by-block tree entry.
  382. */
  383. if ((error = xfs_btree_delete(bno_cur, &i)))
  384. return error;
  385. XFS_WANT_CORRUPTED_RETURN(i == 1);
  386. } else {
  387. /*
  388. * Update the by-block entry to start later|be shorter.
  389. */
  390. if ((error = xfs_alloc_update(bno_cur, nfbno1, nflen1)))
  391. return error;
  392. }
  393. if (nfbno2 != NULLAGBLOCK) {
  394. /*
  395. * 2 resulting free entries, need to add one.
  396. */
  397. if ((error = xfs_alloc_lookup_eq(bno_cur, nfbno2, nflen2, &i)))
  398. return error;
  399. XFS_WANT_CORRUPTED_RETURN(i == 0);
  400. if ((error = xfs_btree_insert(bno_cur, &i)))
  401. return error;
  402. XFS_WANT_CORRUPTED_RETURN(i == 1);
  403. }
  404. return 0;
  405. }
  406. /*
  407. * Read in the allocation group free block array.
  408. */
  409. STATIC int /* error */
  410. xfs_alloc_read_agfl(
  411. xfs_mount_t *mp, /* mount point structure */
  412. xfs_trans_t *tp, /* transaction pointer */
  413. xfs_agnumber_t agno, /* allocation group number */
  414. xfs_buf_t **bpp) /* buffer for the ag free block array */
  415. {
  416. xfs_buf_t *bp; /* return value */
  417. int error;
  418. ASSERT(agno != NULLAGNUMBER);
  419. error = xfs_trans_read_buf(
  420. mp, tp, mp->m_ddev_targp,
  421. XFS_AG_DADDR(mp, agno, XFS_AGFL_DADDR(mp)),
  422. XFS_FSS_TO_BB(mp, 1), 0, &bp);
  423. if (error)
  424. return error;
  425. ASSERT(!xfs_buf_geterror(bp));
  426. xfs_buf_set_ref(bp, XFS_AGFL_REF);
  427. *bpp = bp;
  428. return 0;
  429. }
  430. STATIC int
  431. xfs_alloc_update_counters(
  432. struct xfs_trans *tp,
  433. struct xfs_perag *pag,
  434. struct xfs_buf *agbp,
  435. long len)
  436. {
  437. struct xfs_agf *agf = XFS_BUF_TO_AGF(agbp);
  438. pag->pagf_freeblks += len;
  439. be32_add_cpu(&agf->agf_freeblks, len);
  440. xfs_trans_agblocks_delta(tp, len);
  441. if (unlikely(be32_to_cpu(agf->agf_freeblks) >
  442. be32_to_cpu(agf->agf_length)))
  443. return EFSCORRUPTED;
  444. xfs_alloc_log_agf(tp, agbp, XFS_AGF_FREEBLKS);
  445. return 0;
  446. }
  447. /*
  448. * Allocation group level functions.
  449. */
  450. /*
  451. * Allocate a variable extent in the allocation group agno.
  452. * Type and bno are used to determine where in the allocation group the
  453. * extent will start.
  454. * Extent's length (returned in *len) will be between minlen and maxlen,
  455. * and of the form k * prod + mod unless there's nothing that large.
  456. * Return the starting a.g. block, or NULLAGBLOCK if we can't do it.
  457. */
  458. STATIC int /* error */
  459. xfs_alloc_ag_vextent(
  460. xfs_alloc_arg_t *args) /* argument structure for allocation */
  461. {
  462. int error=0;
  463. ASSERT(args->minlen > 0);
  464. ASSERT(args->maxlen > 0);
  465. ASSERT(args->minlen <= args->maxlen);
  466. ASSERT(args->mod < args->prod);
  467. ASSERT(args->alignment > 0);
  468. /*
  469. * Branch to correct routine based on the type.
  470. */
  471. args->wasfromfl = 0;
  472. switch (args->type) {
  473. case XFS_ALLOCTYPE_THIS_AG:
  474. error = xfs_alloc_ag_vextent_size(args);
  475. break;
  476. case XFS_ALLOCTYPE_NEAR_BNO:
  477. error = xfs_alloc_ag_vextent_near(args);
  478. break;
  479. case XFS_ALLOCTYPE_THIS_BNO:
  480. error = xfs_alloc_ag_vextent_exact(args);
  481. break;
  482. default:
  483. ASSERT(0);
  484. /* NOTREACHED */
  485. }
  486. if (error || args->agbno == NULLAGBLOCK)
  487. return error;
  488. ASSERT(args->len >= args->minlen);
  489. ASSERT(args->len <= args->maxlen);
  490. ASSERT(!args->wasfromfl || !args->isfl);
  491. ASSERT(args->agbno % args->alignment == 0);
  492. if (!args->wasfromfl) {
  493. error = xfs_alloc_update_counters(args->tp, args->pag,
  494. args->agbp,
  495. -((long)(args->len)));
  496. if (error)
  497. return error;
  498. ASSERT(!xfs_alloc_busy_search(args->mp, args->agno,
  499. args->agbno, args->len));
  500. }
  501. if (!args->isfl) {
  502. xfs_trans_mod_sb(args->tp, args->wasdel ?
  503. XFS_TRANS_SB_RES_FDBLOCKS :
  504. XFS_TRANS_SB_FDBLOCKS,
  505. -((long)(args->len)));
  506. }
  507. XFS_STATS_INC(xs_allocx);
  508. XFS_STATS_ADD(xs_allocb, args->len);
  509. return error;
  510. }
  511. /*
  512. * Allocate a variable extent at exactly agno/bno.
  513. * Extent's length (returned in *len) will be between minlen and maxlen,
  514. * and of the form k * prod + mod unless there's nothing that large.
  515. * Return the starting a.g. block (bno), or NULLAGBLOCK if we can't do it.
  516. */
  517. STATIC int /* error */
  518. xfs_alloc_ag_vextent_exact(
  519. xfs_alloc_arg_t *args) /* allocation argument structure */
  520. {
  521. xfs_btree_cur_t *bno_cur;/* by block-number btree cursor */
  522. xfs_btree_cur_t *cnt_cur;/* by count btree cursor */
  523. int error;
  524. xfs_agblock_t fbno; /* start block of found extent */
  525. xfs_extlen_t flen; /* length of found extent */
  526. xfs_agblock_t tbno; /* start block of trimmed extent */
  527. xfs_extlen_t tlen; /* length of trimmed extent */
  528. xfs_agblock_t tend; /* end block of trimmed extent */
  529. int i; /* success/failure of operation */
  530. ASSERT(args->alignment == 1);
  531. /*
  532. * Allocate/initialize a cursor for the by-number freespace btree.
  533. */
  534. bno_cur = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
  535. args->agno, XFS_BTNUM_BNO);
  536. /*
  537. * Lookup bno and minlen in the btree (minlen is irrelevant, really).
  538. * Look for the closest free block <= bno, it must contain bno
  539. * if any free block does.
  540. */
  541. error = xfs_alloc_lookup_le(bno_cur, args->agbno, args->minlen, &i);
  542. if (error)
  543. goto error0;
  544. if (!i)
  545. goto not_found;
  546. /*
  547. * Grab the freespace record.
  548. */
  549. error = xfs_alloc_get_rec(bno_cur, &fbno, &flen, &i);
  550. if (error)
  551. goto error0;
  552. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  553. ASSERT(fbno <= args->agbno);
  554. /*
  555. * Check for overlapping busy extents.
  556. */
  557. xfs_alloc_busy_trim(args, fbno, flen, &tbno, &tlen);
  558. /*
  559. * Give up if the start of the extent is busy, or the freespace isn't
  560. * long enough for the minimum request.
  561. */
  562. if (tbno > args->agbno)
  563. goto not_found;
  564. if (tlen < args->minlen)
  565. goto not_found;
  566. tend = tbno + tlen;
  567. if (tend < args->agbno + args->minlen)
  568. goto not_found;
  569. /*
  570. * End of extent will be smaller of the freespace end and the
  571. * maximal requested end.
  572. *
  573. * Fix the length according to mod and prod if given.
  574. */
  575. args->len = XFS_AGBLOCK_MIN(tend, args->agbno + args->maxlen)
  576. - args->agbno;
  577. xfs_alloc_fix_len(args);
  578. if (!xfs_alloc_fix_minleft(args))
  579. goto not_found;
  580. ASSERT(args->agbno + args->len <= tend);
  581. /*
  582. * We are allocating agbno for args->len
  583. * Allocate/initialize a cursor for the by-size btree.
  584. */
  585. cnt_cur = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
  586. args->agno, XFS_BTNUM_CNT);
  587. ASSERT(args->agbno + args->len <=
  588. be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_length));
  589. error = xfs_alloc_fixup_trees(cnt_cur, bno_cur, fbno, flen, args->agbno,
  590. args->len, XFSA_FIXUP_BNO_OK);
  591. if (error) {
  592. xfs_btree_del_cursor(cnt_cur, XFS_BTREE_ERROR);
  593. goto error0;
  594. }
  595. xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
  596. xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
  597. args->wasfromfl = 0;
  598. trace_xfs_alloc_exact_done(args);
  599. return 0;
  600. not_found:
  601. /* Didn't find it, return null. */
  602. xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
  603. args->agbno = NULLAGBLOCK;
  604. trace_xfs_alloc_exact_notfound(args);
  605. return 0;
  606. error0:
  607. xfs_btree_del_cursor(bno_cur, XFS_BTREE_ERROR);
  608. trace_xfs_alloc_exact_error(args);
  609. return error;
  610. }
  611. /*
  612. * Search the btree in a given direction via the search cursor and compare
  613. * the records found against the good extent we've already found.
  614. */
  615. STATIC int
  616. xfs_alloc_find_best_extent(
  617. struct xfs_alloc_arg *args, /* allocation argument structure */
  618. struct xfs_btree_cur **gcur, /* good cursor */
  619. struct xfs_btree_cur **scur, /* searching cursor */
  620. xfs_agblock_t gdiff, /* difference for search comparison */
  621. xfs_agblock_t *sbno, /* extent found by search */
  622. xfs_extlen_t *slen, /* extent length */
  623. xfs_agblock_t *sbnoa, /* aligned extent found by search */
  624. xfs_extlen_t *slena, /* aligned extent length */
  625. int dir) /* 0 = search right, 1 = search left */
  626. {
  627. xfs_agblock_t new;
  628. xfs_agblock_t sdiff;
  629. int error;
  630. int i;
  631. /* The good extent is perfect, no need to search. */
  632. if (!gdiff)
  633. goto out_use_good;
  634. /*
  635. * Look until we find a better one, run out of space or run off the end.
  636. */
  637. do {
  638. error = xfs_alloc_get_rec(*scur, sbno, slen, &i);
  639. if (error)
  640. goto error0;
  641. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  642. xfs_alloc_compute_aligned(args, *sbno, *slen, sbnoa, slena);
  643. /*
  644. * The good extent is closer than this one.
  645. */
  646. if (!dir) {
  647. if (*sbnoa >= args->agbno + gdiff)
  648. goto out_use_good;
  649. } else {
  650. if (*sbnoa <= args->agbno - gdiff)
  651. goto out_use_good;
  652. }
  653. /*
  654. * Same distance, compare length and pick the best.
  655. */
  656. if (*slena >= args->minlen) {
  657. args->len = XFS_EXTLEN_MIN(*slena, args->maxlen);
  658. xfs_alloc_fix_len(args);
  659. sdiff = xfs_alloc_compute_diff(args->agbno, args->len,
  660. args->alignment, *sbnoa,
  661. *slena, &new);
  662. /*
  663. * Choose closer size and invalidate other cursor.
  664. */
  665. if (sdiff < gdiff)
  666. goto out_use_search;
  667. goto out_use_good;
  668. }
  669. if (!dir)
  670. error = xfs_btree_increment(*scur, 0, &i);
  671. else
  672. error = xfs_btree_decrement(*scur, 0, &i);
  673. if (error)
  674. goto error0;
  675. } while (i);
  676. out_use_good:
  677. xfs_btree_del_cursor(*scur, XFS_BTREE_NOERROR);
  678. *scur = NULL;
  679. return 0;
  680. out_use_search:
  681. xfs_btree_del_cursor(*gcur, XFS_BTREE_NOERROR);
  682. *gcur = NULL;
  683. return 0;
  684. error0:
  685. /* caller invalidates cursors */
  686. return error;
  687. }
  688. /*
  689. * Allocate a variable extent near bno in the allocation group agno.
  690. * Extent's length (returned in len) will be between minlen and maxlen,
  691. * and of the form k * prod + mod unless there's nothing that large.
  692. * Return the starting a.g. block, or NULLAGBLOCK if we can't do it.
  693. */
  694. STATIC int /* error */
  695. xfs_alloc_ag_vextent_near(
  696. xfs_alloc_arg_t *args) /* allocation argument structure */
  697. {
  698. xfs_btree_cur_t *bno_cur_gt; /* cursor for bno btree, right side */
  699. xfs_btree_cur_t *bno_cur_lt; /* cursor for bno btree, left side */
  700. xfs_btree_cur_t *cnt_cur; /* cursor for count btree */
  701. xfs_agblock_t gtbno; /* start bno of right side entry */
  702. xfs_agblock_t gtbnoa; /* aligned ... */
  703. xfs_extlen_t gtdiff; /* difference to right side entry */
  704. xfs_extlen_t gtlen; /* length of right side entry */
  705. xfs_extlen_t gtlena; /* aligned ... */
  706. xfs_agblock_t gtnew; /* useful start bno of right side */
  707. int error; /* error code */
  708. int i; /* result code, temporary */
  709. int j; /* result code, temporary */
  710. xfs_agblock_t ltbno; /* start bno of left side entry */
  711. xfs_agblock_t ltbnoa; /* aligned ... */
  712. xfs_extlen_t ltdiff; /* difference to left side entry */
  713. xfs_extlen_t ltlen; /* length of left side entry */
  714. xfs_extlen_t ltlena; /* aligned ... */
  715. xfs_agblock_t ltnew; /* useful start bno of left side */
  716. xfs_extlen_t rlen; /* length of returned extent */
  717. int forced = 0;
  718. #if defined(DEBUG) && defined(__KERNEL__)
  719. /*
  720. * Randomly don't execute the first algorithm.
  721. */
  722. int dofirst; /* set to do first algorithm */
  723. dofirst = random32() & 1;
  724. #endif
  725. restart:
  726. bno_cur_lt = NULL;
  727. bno_cur_gt = NULL;
  728. ltlen = 0;
  729. gtlena = 0;
  730. ltlena = 0;
  731. /*
  732. * Get a cursor for the by-size btree.
  733. */
  734. cnt_cur = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
  735. args->agno, XFS_BTNUM_CNT);
  736. /*
  737. * See if there are any free extents as big as maxlen.
  738. */
  739. if ((error = xfs_alloc_lookup_ge(cnt_cur, 0, args->maxlen, &i)))
  740. goto error0;
  741. /*
  742. * If none, then pick up the last entry in the tree unless the
  743. * tree is empty.
  744. */
  745. if (!i) {
  746. if ((error = xfs_alloc_ag_vextent_small(args, cnt_cur, &ltbno,
  747. &ltlen, &i)))
  748. goto error0;
  749. if (i == 0 || ltlen == 0) {
  750. xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
  751. trace_xfs_alloc_near_noentry(args);
  752. return 0;
  753. }
  754. ASSERT(i == 1);
  755. }
  756. args->wasfromfl = 0;
  757. /*
  758. * First algorithm.
  759. * If the requested extent is large wrt the freespaces available
  760. * in this a.g., then the cursor will be pointing to a btree entry
  761. * near the right edge of the tree. If it's in the last btree leaf
  762. * block, then we just examine all the entries in that block
  763. * that are big enough, and pick the best one.
  764. * This is written as a while loop so we can break out of it,
  765. * but we never loop back to the top.
  766. */
  767. while (xfs_btree_islastblock(cnt_cur, 0)) {
  768. xfs_extlen_t bdiff;
  769. int besti=0;
  770. xfs_extlen_t blen=0;
  771. xfs_agblock_t bnew=0;
  772. #if defined(DEBUG) && defined(__KERNEL__)
  773. if (!dofirst)
  774. break;
  775. #endif
  776. /*
  777. * Start from the entry that lookup found, sequence through
  778. * all larger free blocks. If we're actually pointing at a
  779. * record smaller than maxlen, go to the start of this block,
  780. * and skip all those smaller than minlen.
  781. */
  782. if (ltlen || args->alignment > 1) {
  783. cnt_cur->bc_ptrs[0] = 1;
  784. do {
  785. if ((error = xfs_alloc_get_rec(cnt_cur, &ltbno,
  786. &ltlen, &i)))
  787. goto error0;
  788. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  789. if (ltlen >= args->minlen)
  790. break;
  791. if ((error = xfs_btree_increment(cnt_cur, 0, &i)))
  792. goto error0;
  793. } while (i);
  794. ASSERT(ltlen >= args->minlen);
  795. if (!i)
  796. break;
  797. }
  798. i = cnt_cur->bc_ptrs[0];
  799. for (j = 1, blen = 0, bdiff = 0;
  800. !error && j && (blen < args->maxlen || bdiff > 0);
  801. error = xfs_btree_increment(cnt_cur, 0, &j)) {
  802. /*
  803. * For each entry, decide if it's better than
  804. * the previous best entry.
  805. */
  806. if ((error = xfs_alloc_get_rec(cnt_cur, &ltbno, &ltlen, &i)))
  807. goto error0;
  808. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  809. xfs_alloc_compute_aligned(args, ltbno, ltlen,
  810. &ltbnoa, &ltlena);
  811. if (ltlena < args->minlen)
  812. continue;
  813. args->len = XFS_EXTLEN_MIN(ltlena, args->maxlen);
  814. xfs_alloc_fix_len(args);
  815. ASSERT(args->len >= args->minlen);
  816. if (args->len < blen)
  817. continue;
  818. ltdiff = xfs_alloc_compute_diff(args->agbno, args->len,
  819. args->alignment, ltbnoa, ltlena, &ltnew);
  820. if (ltnew != NULLAGBLOCK &&
  821. (args->len > blen || ltdiff < bdiff)) {
  822. bdiff = ltdiff;
  823. bnew = ltnew;
  824. blen = args->len;
  825. besti = cnt_cur->bc_ptrs[0];
  826. }
  827. }
  828. /*
  829. * It didn't work. We COULD be in a case where
  830. * there's a good record somewhere, so try again.
  831. */
  832. if (blen == 0)
  833. break;
  834. /*
  835. * Point at the best entry, and retrieve it again.
  836. */
  837. cnt_cur->bc_ptrs[0] = besti;
  838. if ((error = xfs_alloc_get_rec(cnt_cur, &ltbno, &ltlen, &i)))
  839. goto error0;
  840. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  841. ASSERT(ltbno + ltlen <= be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_length));
  842. args->len = blen;
  843. if (!xfs_alloc_fix_minleft(args)) {
  844. xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
  845. trace_xfs_alloc_near_nominleft(args);
  846. return 0;
  847. }
  848. blen = args->len;
  849. /*
  850. * We are allocating starting at bnew for blen blocks.
  851. */
  852. args->agbno = bnew;
  853. ASSERT(bnew >= ltbno);
  854. ASSERT(bnew + blen <= ltbno + ltlen);
  855. /*
  856. * Set up a cursor for the by-bno tree.
  857. */
  858. bno_cur_lt = xfs_allocbt_init_cursor(args->mp, args->tp,
  859. args->agbp, args->agno, XFS_BTNUM_BNO);
  860. /*
  861. * Fix up the btree entries.
  862. */
  863. if ((error = xfs_alloc_fixup_trees(cnt_cur, bno_cur_lt, ltbno,
  864. ltlen, bnew, blen, XFSA_FIXUP_CNT_OK)))
  865. goto error0;
  866. xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
  867. xfs_btree_del_cursor(bno_cur_lt, XFS_BTREE_NOERROR);
  868. trace_xfs_alloc_near_first(args);
  869. return 0;
  870. }
  871. /*
  872. * Second algorithm.
  873. * Search in the by-bno tree to the left and to the right
  874. * simultaneously, until in each case we find a space big enough,
  875. * or run into the edge of the tree. When we run into the edge,
  876. * we deallocate that cursor.
  877. * If both searches succeed, we compare the two spaces and pick
  878. * the better one.
  879. * With alignment, it's possible for both to fail; the upper
  880. * level algorithm that picks allocation groups for allocations
  881. * is not supposed to do this.
  882. */
  883. /*
  884. * Allocate and initialize the cursor for the leftward search.
  885. */
  886. bno_cur_lt = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
  887. args->agno, XFS_BTNUM_BNO);
  888. /*
  889. * Lookup <= bno to find the leftward search's starting point.
  890. */
  891. if ((error = xfs_alloc_lookup_le(bno_cur_lt, args->agbno, args->maxlen, &i)))
  892. goto error0;
  893. if (!i) {
  894. /*
  895. * Didn't find anything; use this cursor for the rightward
  896. * search.
  897. */
  898. bno_cur_gt = bno_cur_lt;
  899. bno_cur_lt = NULL;
  900. }
  901. /*
  902. * Found something. Duplicate the cursor for the rightward search.
  903. */
  904. else if ((error = xfs_btree_dup_cursor(bno_cur_lt, &bno_cur_gt)))
  905. goto error0;
  906. /*
  907. * Increment the cursor, so we will point at the entry just right
  908. * of the leftward entry if any, or to the leftmost entry.
  909. */
  910. if ((error = xfs_btree_increment(bno_cur_gt, 0, &i)))
  911. goto error0;
  912. if (!i) {
  913. /*
  914. * It failed, there are no rightward entries.
  915. */
  916. xfs_btree_del_cursor(bno_cur_gt, XFS_BTREE_NOERROR);
  917. bno_cur_gt = NULL;
  918. }
  919. /*
  920. * Loop going left with the leftward cursor, right with the
  921. * rightward cursor, until either both directions give up or
  922. * we find an entry at least as big as minlen.
  923. */
  924. do {
  925. if (bno_cur_lt) {
  926. if ((error = xfs_alloc_get_rec(bno_cur_lt, &ltbno, &ltlen, &i)))
  927. goto error0;
  928. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  929. xfs_alloc_compute_aligned(args, ltbno, ltlen,
  930. &ltbnoa, &ltlena);
  931. if (ltlena >= args->minlen)
  932. break;
  933. if ((error = xfs_btree_decrement(bno_cur_lt, 0, &i)))
  934. goto error0;
  935. if (!i) {
  936. xfs_btree_del_cursor(bno_cur_lt,
  937. XFS_BTREE_NOERROR);
  938. bno_cur_lt = NULL;
  939. }
  940. }
  941. if (bno_cur_gt) {
  942. if ((error = xfs_alloc_get_rec(bno_cur_gt, &gtbno, &gtlen, &i)))
  943. goto error0;
  944. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  945. xfs_alloc_compute_aligned(args, gtbno, gtlen,
  946. &gtbnoa, &gtlena);
  947. if (gtlena >= args->minlen)
  948. break;
  949. if ((error = xfs_btree_increment(bno_cur_gt, 0, &i)))
  950. goto error0;
  951. if (!i) {
  952. xfs_btree_del_cursor(bno_cur_gt,
  953. XFS_BTREE_NOERROR);
  954. bno_cur_gt = NULL;
  955. }
  956. }
  957. } while (bno_cur_lt || bno_cur_gt);
  958. /*
  959. * Got both cursors still active, need to find better entry.
  960. */
  961. if (bno_cur_lt && bno_cur_gt) {
  962. if (ltlena >= args->minlen) {
  963. /*
  964. * Left side is good, look for a right side entry.
  965. */
  966. args->len = XFS_EXTLEN_MIN(ltlena, args->maxlen);
  967. xfs_alloc_fix_len(args);
  968. ltdiff = xfs_alloc_compute_diff(args->agbno, args->len,
  969. args->alignment, ltbnoa, ltlena, &ltnew);
  970. error = xfs_alloc_find_best_extent(args,
  971. &bno_cur_lt, &bno_cur_gt,
  972. ltdiff, &gtbno, &gtlen,
  973. &gtbnoa, &gtlena,
  974. 0 /* search right */);
  975. } else {
  976. ASSERT(gtlena >= args->minlen);
  977. /*
  978. * Right side is good, look for a left side entry.
  979. */
  980. args->len = XFS_EXTLEN_MIN(gtlena, args->maxlen);
  981. xfs_alloc_fix_len(args);
  982. gtdiff = xfs_alloc_compute_diff(args->agbno, args->len,
  983. args->alignment, gtbnoa, gtlena, &gtnew);
  984. error = xfs_alloc_find_best_extent(args,
  985. &bno_cur_gt, &bno_cur_lt,
  986. gtdiff, &ltbno, &ltlen,
  987. &ltbnoa, &ltlena,
  988. 1 /* search left */);
  989. }
  990. if (error)
  991. goto error0;
  992. }
  993. /*
  994. * If we couldn't get anything, give up.
  995. */
  996. if (bno_cur_lt == NULL && bno_cur_gt == NULL) {
  997. if (!forced++) {
  998. trace_xfs_alloc_near_busy(args);
  999. xfs_log_force(args->mp, XFS_LOG_SYNC);
  1000. goto restart;
  1001. }
  1002. trace_xfs_alloc_size_neither(args);
  1003. args->agbno = NULLAGBLOCK;
  1004. return 0;
  1005. }
  1006. /*
  1007. * At this point we have selected a freespace entry, either to the
  1008. * left or to the right. If it's on the right, copy all the
  1009. * useful variables to the "left" set so we only have one
  1010. * copy of this code.
  1011. */
  1012. if (bno_cur_gt) {
  1013. bno_cur_lt = bno_cur_gt;
  1014. bno_cur_gt = NULL;
  1015. ltbno = gtbno;
  1016. ltbnoa = gtbnoa;
  1017. ltlen = gtlen;
  1018. ltlena = gtlena;
  1019. j = 1;
  1020. } else
  1021. j = 0;
  1022. /*
  1023. * Fix up the length and compute the useful address.
  1024. */
  1025. args->len = XFS_EXTLEN_MIN(ltlena, args->maxlen);
  1026. xfs_alloc_fix_len(args);
  1027. if (!xfs_alloc_fix_minleft(args)) {
  1028. trace_xfs_alloc_near_nominleft(args);
  1029. xfs_btree_del_cursor(bno_cur_lt, XFS_BTREE_NOERROR);
  1030. xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
  1031. return 0;
  1032. }
  1033. rlen = args->len;
  1034. (void)xfs_alloc_compute_diff(args->agbno, rlen, args->alignment,
  1035. ltbnoa, ltlena, &ltnew);
  1036. ASSERT(ltnew >= ltbno);
  1037. ASSERT(ltnew + rlen <= ltbnoa + ltlena);
  1038. ASSERT(ltnew + rlen <= be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_length));
  1039. args->agbno = ltnew;
  1040. if ((error = xfs_alloc_fixup_trees(cnt_cur, bno_cur_lt, ltbno, ltlen,
  1041. ltnew, rlen, XFSA_FIXUP_BNO_OK)))
  1042. goto error0;
  1043. if (j)
  1044. trace_xfs_alloc_near_greater(args);
  1045. else
  1046. trace_xfs_alloc_near_lesser(args);
  1047. xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
  1048. xfs_btree_del_cursor(bno_cur_lt, XFS_BTREE_NOERROR);
  1049. return 0;
  1050. error0:
  1051. trace_xfs_alloc_near_error(args);
  1052. if (cnt_cur != NULL)
  1053. xfs_btree_del_cursor(cnt_cur, XFS_BTREE_ERROR);
  1054. if (bno_cur_lt != NULL)
  1055. xfs_btree_del_cursor(bno_cur_lt, XFS_BTREE_ERROR);
  1056. if (bno_cur_gt != NULL)
  1057. xfs_btree_del_cursor(bno_cur_gt, XFS_BTREE_ERROR);
  1058. return error;
  1059. }
  1060. /*
  1061. * Allocate a variable extent anywhere in the allocation group agno.
  1062. * Extent's length (returned in len) will be between minlen and maxlen,
  1063. * and of the form k * prod + mod unless there's nothing that large.
  1064. * Return the starting a.g. block, or NULLAGBLOCK if we can't do it.
  1065. */
  1066. STATIC int /* error */
  1067. xfs_alloc_ag_vextent_size(
  1068. xfs_alloc_arg_t *args) /* allocation argument structure */
  1069. {
  1070. xfs_btree_cur_t *bno_cur; /* cursor for bno btree */
  1071. xfs_btree_cur_t *cnt_cur; /* cursor for cnt btree */
  1072. int error; /* error result */
  1073. xfs_agblock_t fbno; /* start of found freespace */
  1074. xfs_extlen_t flen; /* length of found freespace */
  1075. int i; /* temp status variable */
  1076. xfs_agblock_t rbno; /* returned block number */
  1077. xfs_extlen_t rlen; /* length of returned extent */
  1078. int forced = 0;
  1079. restart:
  1080. /*
  1081. * Allocate and initialize a cursor for the by-size btree.
  1082. */
  1083. cnt_cur = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
  1084. args->agno, XFS_BTNUM_CNT);
  1085. bno_cur = NULL;
  1086. /*
  1087. * Look for an entry >= maxlen+alignment-1 blocks.
  1088. */
  1089. if ((error = xfs_alloc_lookup_ge(cnt_cur, 0,
  1090. args->maxlen + args->alignment - 1, &i)))
  1091. goto error0;
  1092. /*
  1093. * If none or we have busy extents that we cannot allocate from, then
  1094. * we have to settle for a smaller extent. In the case that there are
  1095. * no large extents, this will return the last entry in the tree unless
  1096. * the tree is empty. In the case that there are only busy large
  1097. * extents, this will return the largest small extent unless there
  1098. * are no smaller extents available.
  1099. */
  1100. if (!i || forced > 1) {
  1101. error = xfs_alloc_ag_vextent_small(args, cnt_cur,
  1102. &fbno, &flen, &i);
  1103. if (error)
  1104. goto error0;
  1105. if (i == 0 || flen == 0) {
  1106. xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
  1107. trace_xfs_alloc_size_noentry(args);
  1108. return 0;
  1109. }
  1110. ASSERT(i == 1);
  1111. xfs_alloc_compute_aligned(args, fbno, flen, &rbno, &rlen);
  1112. } else {
  1113. /*
  1114. * Search for a non-busy extent that is large enough.
  1115. * If we are at low space, don't check, or if we fall of
  1116. * the end of the btree, turn off the busy check and
  1117. * restart.
  1118. */
  1119. for (;;) {
  1120. error = xfs_alloc_get_rec(cnt_cur, &fbno, &flen, &i);
  1121. if (error)
  1122. goto error0;
  1123. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  1124. xfs_alloc_compute_aligned(args, fbno, flen,
  1125. &rbno, &rlen);
  1126. if (rlen >= args->maxlen)
  1127. break;
  1128. error = xfs_btree_increment(cnt_cur, 0, &i);
  1129. if (error)
  1130. goto error0;
  1131. if (i == 0) {
  1132. /*
  1133. * Our only valid extents must have been busy.
  1134. * Make it unbusy by forcing the log out and
  1135. * retrying. If we've been here before, forcing
  1136. * the log isn't making the extents available,
  1137. * which means they have probably been freed in
  1138. * this transaction. In that case, we have to
  1139. * give up on them and we'll attempt a minlen
  1140. * allocation the next time around.
  1141. */
  1142. xfs_btree_del_cursor(cnt_cur,
  1143. XFS_BTREE_NOERROR);
  1144. trace_xfs_alloc_size_busy(args);
  1145. if (!forced++)
  1146. xfs_log_force(args->mp, XFS_LOG_SYNC);
  1147. goto restart;
  1148. }
  1149. }
  1150. }
  1151. /*
  1152. * In the first case above, we got the last entry in the
  1153. * by-size btree. Now we check to see if the space hits maxlen
  1154. * once aligned; if not, we search left for something better.
  1155. * This can't happen in the second case above.
  1156. */
  1157. rlen = XFS_EXTLEN_MIN(args->maxlen, rlen);
  1158. XFS_WANT_CORRUPTED_GOTO(rlen == 0 ||
  1159. (rlen <= flen && rbno + rlen <= fbno + flen), error0);
  1160. if (rlen < args->maxlen) {
  1161. xfs_agblock_t bestfbno;
  1162. xfs_extlen_t bestflen;
  1163. xfs_agblock_t bestrbno;
  1164. xfs_extlen_t bestrlen;
  1165. bestrlen = rlen;
  1166. bestrbno = rbno;
  1167. bestflen = flen;
  1168. bestfbno = fbno;
  1169. for (;;) {
  1170. if ((error = xfs_btree_decrement(cnt_cur, 0, &i)))
  1171. goto error0;
  1172. if (i == 0)
  1173. break;
  1174. if ((error = xfs_alloc_get_rec(cnt_cur, &fbno, &flen,
  1175. &i)))
  1176. goto error0;
  1177. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  1178. if (flen < bestrlen)
  1179. break;
  1180. xfs_alloc_compute_aligned(args, fbno, flen,
  1181. &rbno, &rlen);
  1182. rlen = XFS_EXTLEN_MIN(args->maxlen, rlen);
  1183. XFS_WANT_CORRUPTED_GOTO(rlen == 0 ||
  1184. (rlen <= flen && rbno + rlen <= fbno + flen),
  1185. error0);
  1186. if (rlen > bestrlen) {
  1187. bestrlen = rlen;
  1188. bestrbno = rbno;
  1189. bestflen = flen;
  1190. bestfbno = fbno;
  1191. if (rlen == args->maxlen)
  1192. break;
  1193. }
  1194. }
  1195. if ((error = xfs_alloc_lookup_eq(cnt_cur, bestfbno, bestflen,
  1196. &i)))
  1197. goto error0;
  1198. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  1199. rlen = bestrlen;
  1200. rbno = bestrbno;
  1201. flen = bestflen;
  1202. fbno = bestfbno;
  1203. }
  1204. args->wasfromfl = 0;
  1205. /*
  1206. * Fix up the length.
  1207. */
  1208. args->len = rlen;
  1209. if (rlen < args->minlen) {
  1210. if (!forced++) {
  1211. xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
  1212. trace_xfs_alloc_size_busy(args);
  1213. xfs_log_force(args->mp, XFS_LOG_SYNC);
  1214. goto restart;
  1215. }
  1216. goto out_nominleft;
  1217. }
  1218. xfs_alloc_fix_len(args);
  1219. if (!xfs_alloc_fix_minleft(args))
  1220. goto out_nominleft;
  1221. rlen = args->len;
  1222. XFS_WANT_CORRUPTED_GOTO(rlen <= flen, error0);
  1223. /*
  1224. * Allocate and initialize a cursor for the by-block tree.
  1225. */
  1226. bno_cur = xfs_allocbt_init_cursor(args->mp, args->tp, args->agbp,
  1227. args->agno, XFS_BTNUM_BNO);
  1228. if ((error = xfs_alloc_fixup_trees(cnt_cur, bno_cur, fbno, flen,
  1229. rbno, rlen, XFSA_FIXUP_CNT_OK)))
  1230. goto error0;
  1231. xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
  1232. xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
  1233. cnt_cur = bno_cur = NULL;
  1234. args->len = rlen;
  1235. args->agbno = rbno;
  1236. XFS_WANT_CORRUPTED_GOTO(
  1237. args->agbno + args->len <=
  1238. be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_length),
  1239. error0);
  1240. trace_xfs_alloc_size_done(args);
  1241. return 0;
  1242. error0:
  1243. trace_xfs_alloc_size_error(args);
  1244. if (cnt_cur)
  1245. xfs_btree_del_cursor(cnt_cur, XFS_BTREE_ERROR);
  1246. if (bno_cur)
  1247. xfs_btree_del_cursor(bno_cur, XFS_BTREE_ERROR);
  1248. return error;
  1249. out_nominleft:
  1250. xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
  1251. trace_xfs_alloc_size_nominleft(args);
  1252. args->agbno = NULLAGBLOCK;
  1253. return 0;
  1254. }
  1255. /*
  1256. * Deal with the case where only small freespaces remain.
  1257. * Either return the contents of the last freespace record,
  1258. * or allocate space from the freelist if there is nothing in the tree.
  1259. */
  1260. STATIC int /* error */
  1261. xfs_alloc_ag_vextent_small(
  1262. xfs_alloc_arg_t *args, /* allocation argument structure */
  1263. xfs_btree_cur_t *ccur, /* by-size cursor */
  1264. xfs_agblock_t *fbnop, /* result block number */
  1265. xfs_extlen_t *flenp, /* result length */
  1266. int *stat) /* status: 0-freelist, 1-normal/none */
  1267. {
  1268. int error;
  1269. xfs_agblock_t fbno;
  1270. xfs_extlen_t flen;
  1271. int i;
  1272. if ((error = xfs_btree_decrement(ccur, 0, &i)))
  1273. goto error0;
  1274. if (i) {
  1275. if ((error = xfs_alloc_get_rec(ccur, &fbno, &flen, &i)))
  1276. goto error0;
  1277. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  1278. }
  1279. /*
  1280. * Nothing in the btree, try the freelist. Make sure
  1281. * to respect minleft even when pulling from the
  1282. * freelist.
  1283. */
  1284. else if (args->minlen == 1 && args->alignment == 1 && !args->isfl &&
  1285. (be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_flcount)
  1286. > args->minleft)) {
  1287. error = xfs_alloc_get_freelist(args->tp, args->agbp, &fbno, 0);
  1288. if (error)
  1289. goto error0;
  1290. if (fbno != NULLAGBLOCK) {
  1291. xfs_alloc_busy_reuse(args->mp, args->agno, fbno, 1,
  1292. args->userdata);
  1293. if (args->userdata) {
  1294. xfs_buf_t *bp;
  1295. bp = xfs_btree_get_bufs(args->mp, args->tp,
  1296. args->agno, fbno, 0);
  1297. xfs_trans_binval(args->tp, bp);
  1298. }
  1299. args->len = 1;
  1300. args->agbno = fbno;
  1301. XFS_WANT_CORRUPTED_GOTO(
  1302. args->agbno + args->len <=
  1303. be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_length),
  1304. error0);
  1305. args->wasfromfl = 1;
  1306. trace_xfs_alloc_small_freelist(args);
  1307. *stat = 0;
  1308. return 0;
  1309. }
  1310. /*
  1311. * Nothing in the freelist.
  1312. */
  1313. else
  1314. flen = 0;
  1315. }
  1316. /*
  1317. * Can't allocate from the freelist for some reason.
  1318. */
  1319. else {
  1320. fbno = NULLAGBLOCK;
  1321. flen = 0;
  1322. }
  1323. /*
  1324. * Can't do the allocation, give up.
  1325. */
  1326. if (flen < args->minlen) {
  1327. args->agbno = NULLAGBLOCK;
  1328. trace_xfs_alloc_small_notenough(args);
  1329. flen = 0;
  1330. }
  1331. *fbnop = fbno;
  1332. *flenp = flen;
  1333. *stat = 1;
  1334. trace_xfs_alloc_small_done(args);
  1335. return 0;
  1336. error0:
  1337. trace_xfs_alloc_small_error(args);
  1338. return error;
  1339. }
  1340. /*
  1341. * Free the extent starting at agno/bno for length.
  1342. */
  1343. STATIC int /* error */
  1344. xfs_free_ag_extent(
  1345. xfs_trans_t *tp, /* transaction pointer */
  1346. xfs_buf_t *agbp, /* buffer for a.g. freelist header */
  1347. xfs_agnumber_t agno, /* allocation group number */
  1348. xfs_agblock_t bno, /* starting block number */
  1349. xfs_extlen_t len, /* length of extent */
  1350. int isfl) /* set if is freelist blocks - no sb acctg */
  1351. {
  1352. xfs_btree_cur_t *bno_cur; /* cursor for by-block btree */
  1353. xfs_btree_cur_t *cnt_cur; /* cursor for by-size btree */
  1354. int error; /* error return value */
  1355. xfs_agblock_t gtbno; /* start of right neighbor block */
  1356. xfs_extlen_t gtlen; /* length of right neighbor block */
  1357. int haveleft; /* have a left neighbor block */
  1358. int haveright; /* have a right neighbor block */
  1359. int i; /* temp, result code */
  1360. xfs_agblock_t ltbno; /* start of left neighbor block */
  1361. xfs_extlen_t ltlen; /* length of left neighbor block */
  1362. xfs_mount_t *mp; /* mount point struct for filesystem */
  1363. xfs_agblock_t nbno; /* new starting block of freespace */
  1364. xfs_extlen_t nlen; /* new length of freespace */
  1365. xfs_perag_t *pag; /* per allocation group data */
  1366. mp = tp->t_mountp;
  1367. /*
  1368. * Allocate and initialize a cursor for the by-block btree.
  1369. */
  1370. bno_cur = xfs_allocbt_init_cursor(mp, tp, agbp, agno, XFS_BTNUM_BNO);
  1371. cnt_cur = NULL;
  1372. /*
  1373. * Look for a neighboring block on the left (lower block numbers)
  1374. * that is contiguous with this space.
  1375. */
  1376. if ((error = xfs_alloc_lookup_le(bno_cur, bno, len, &haveleft)))
  1377. goto error0;
  1378. if (haveleft) {
  1379. /*
  1380. * There is a block to our left.
  1381. */
  1382. if ((error = xfs_alloc_get_rec(bno_cur, &ltbno, &ltlen, &i)))
  1383. goto error0;
  1384. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  1385. /*
  1386. * It's not contiguous, though.
  1387. */
  1388. if (ltbno + ltlen < bno)
  1389. haveleft = 0;
  1390. else {
  1391. /*
  1392. * If this failure happens the request to free this
  1393. * space was invalid, it's (partly) already free.
  1394. * Very bad.
  1395. */
  1396. XFS_WANT_CORRUPTED_GOTO(ltbno + ltlen <= bno, error0);
  1397. }
  1398. }
  1399. /*
  1400. * Look for a neighboring block on the right (higher block numbers)
  1401. * that is contiguous with this space.
  1402. */
  1403. if ((error = xfs_btree_increment(bno_cur, 0, &haveright)))
  1404. goto error0;
  1405. if (haveright) {
  1406. /*
  1407. * There is a block to our right.
  1408. */
  1409. if ((error = xfs_alloc_get_rec(bno_cur, &gtbno, &gtlen, &i)))
  1410. goto error0;
  1411. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  1412. /*
  1413. * It's not contiguous, though.
  1414. */
  1415. if (bno + len < gtbno)
  1416. haveright = 0;
  1417. else {
  1418. /*
  1419. * If this failure happens the request to free this
  1420. * space was invalid, it's (partly) already free.
  1421. * Very bad.
  1422. */
  1423. XFS_WANT_CORRUPTED_GOTO(gtbno >= bno + len, error0);
  1424. }
  1425. }
  1426. /*
  1427. * Now allocate and initialize a cursor for the by-size tree.
  1428. */
  1429. cnt_cur = xfs_allocbt_init_cursor(mp, tp, agbp, agno, XFS_BTNUM_CNT);
  1430. /*
  1431. * Have both left and right contiguous neighbors.
  1432. * Merge all three into a single free block.
  1433. */
  1434. if (haveleft && haveright) {
  1435. /*
  1436. * Delete the old by-size entry on the left.
  1437. */
  1438. if ((error = xfs_alloc_lookup_eq(cnt_cur, ltbno, ltlen, &i)))
  1439. goto error0;
  1440. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  1441. if ((error = xfs_btree_delete(cnt_cur, &i)))
  1442. goto error0;
  1443. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  1444. /*
  1445. * Delete the old by-size entry on the right.
  1446. */
  1447. if ((error = xfs_alloc_lookup_eq(cnt_cur, gtbno, gtlen, &i)))
  1448. goto error0;
  1449. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  1450. if ((error = xfs_btree_delete(cnt_cur, &i)))
  1451. goto error0;
  1452. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  1453. /*
  1454. * Delete the old by-block entry for the right block.
  1455. */
  1456. if ((error = xfs_btree_delete(bno_cur, &i)))
  1457. goto error0;
  1458. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  1459. /*
  1460. * Move the by-block cursor back to the left neighbor.
  1461. */
  1462. if ((error = xfs_btree_decrement(bno_cur, 0, &i)))
  1463. goto error0;
  1464. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  1465. #ifdef DEBUG
  1466. /*
  1467. * Check that this is the right record: delete didn't
  1468. * mangle the cursor.
  1469. */
  1470. {
  1471. xfs_agblock_t xxbno;
  1472. xfs_extlen_t xxlen;
  1473. if ((error = xfs_alloc_get_rec(bno_cur, &xxbno, &xxlen,
  1474. &i)))
  1475. goto error0;
  1476. XFS_WANT_CORRUPTED_GOTO(
  1477. i == 1 && xxbno == ltbno && xxlen == ltlen,
  1478. error0);
  1479. }
  1480. #endif
  1481. /*
  1482. * Update remaining by-block entry to the new, joined block.
  1483. */
  1484. nbno = ltbno;
  1485. nlen = len + ltlen + gtlen;
  1486. if ((error = xfs_alloc_update(bno_cur, nbno, nlen)))
  1487. goto error0;
  1488. }
  1489. /*
  1490. * Have only a left contiguous neighbor.
  1491. * Merge it together with the new freespace.
  1492. */
  1493. else if (haveleft) {
  1494. /*
  1495. * Delete the old by-size entry on the left.
  1496. */
  1497. if ((error = xfs_alloc_lookup_eq(cnt_cur, ltbno, ltlen, &i)))
  1498. goto error0;
  1499. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  1500. if ((error = xfs_btree_delete(cnt_cur, &i)))
  1501. goto error0;
  1502. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  1503. /*
  1504. * Back up the by-block cursor to the left neighbor, and
  1505. * update its length.
  1506. */
  1507. if ((error = xfs_btree_decrement(bno_cur, 0, &i)))
  1508. goto error0;
  1509. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  1510. nbno = ltbno;
  1511. nlen = len + ltlen;
  1512. if ((error = xfs_alloc_update(bno_cur, nbno, nlen)))
  1513. goto error0;
  1514. }
  1515. /*
  1516. * Have only a right contiguous neighbor.
  1517. * Merge it together with the new freespace.
  1518. */
  1519. else if (haveright) {
  1520. /*
  1521. * Delete the old by-size entry on the right.
  1522. */
  1523. if ((error = xfs_alloc_lookup_eq(cnt_cur, gtbno, gtlen, &i)))
  1524. goto error0;
  1525. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  1526. if ((error = xfs_btree_delete(cnt_cur, &i)))
  1527. goto error0;
  1528. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  1529. /*
  1530. * Update the starting block and length of the right
  1531. * neighbor in the by-block tree.
  1532. */
  1533. nbno = bno;
  1534. nlen = len + gtlen;
  1535. if ((error = xfs_alloc_update(bno_cur, nbno, nlen)))
  1536. goto error0;
  1537. }
  1538. /*
  1539. * No contiguous neighbors.
  1540. * Insert the new freespace into the by-block tree.
  1541. */
  1542. else {
  1543. nbno = bno;
  1544. nlen = len;
  1545. if ((error = xfs_btree_insert(bno_cur, &i)))
  1546. goto error0;
  1547. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  1548. }
  1549. xfs_btree_del_cursor(bno_cur, XFS_BTREE_NOERROR);
  1550. bno_cur = NULL;
  1551. /*
  1552. * In all cases we need to insert the new freespace in the by-size tree.
  1553. */
  1554. if ((error = xfs_alloc_lookup_eq(cnt_cur, nbno, nlen, &i)))
  1555. goto error0;
  1556. XFS_WANT_CORRUPTED_GOTO(i == 0, error0);
  1557. if ((error = xfs_btree_insert(cnt_cur, &i)))
  1558. goto error0;
  1559. XFS_WANT_CORRUPTED_GOTO(i == 1, error0);
  1560. xfs_btree_del_cursor(cnt_cur, XFS_BTREE_NOERROR);
  1561. cnt_cur = NULL;
  1562. /*
  1563. * Update the freespace totals in the ag and superblock.
  1564. */
  1565. pag = xfs_perag_get(mp, agno);
  1566. error = xfs_alloc_update_counters(tp, pag, agbp, len);
  1567. xfs_perag_put(pag);
  1568. if (error)
  1569. goto error0;
  1570. if (!isfl)
  1571. xfs_trans_mod_sb(tp, XFS_TRANS_SB_FDBLOCKS, (long)len);
  1572. XFS_STATS_INC(xs_freex);
  1573. XFS_STATS_ADD(xs_freeb, len);
  1574. trace_xfs_free_extent(mp, agno, bno, len, isfl, haveleft, haveright);
  1575. return 0;
  1576. error0:
  1577. trace_xfs_free_extent(mp, agno, bno, len, isfl, -1, -1);
  1578. if (bno_cur)
  1579. xfs_btree_del_cursor(bno_cur, XFS_BTREE_ERROR);
  1580. if (cnt_cur)
  1581. xfs_btree_del_cursor(cnt_cur, XFS_BTREE_ERROR);
  1582. return error;
  1583. }
  1584. /*
  1585. * Visible (exported) allocation/free functions.
  1586. * Some of these are used just by xfs_alloc_btree.c and this file.
  1587. */
  1588. /*
  1589. * Compute and fill in value of m_ag_maxlevels.
  1590. */
  1591. void
  1592. xfs_alloc_compute_maxlevels(
  1593. xfs_mount_t *mp) /* file system mount structure */
  1594. {
  1595. int level;
  1596. uint maxblocks;
  1597. uint maxleafents;
  1598. int minleafrecs;
  1599. int minnoderecs;
  1600. maxleafents = (mp->m_sb.sb_agblocks + 1) / 2;
  1601. minleafrecs = mp->m_alloc_mnr[0];
  1602. minnoderecs = mp->m_alloc_mnr[1];
  1603. maxblocks = (maxleafents + minleafrecs - 1) / minleafrecs;
  1604. for (level = 1; maxblocks > 1; level++)
  1605. maxblocks = (maxblocks + minnoderecs - 1) / minnoderecs;
  1606. mp->m_ag_maxlevels = level;
  1607. }
  1608. /*
  1609. * Find the length of the longest extent in an AG.
  1610. */
  1611. xfs_extlen_t
  1612. xfs_alloc_longest_free_extent(
  1613. struct xfs_mount *mp,
  1614. struct xfs_perag *pag)
  1615. {
  1616. xfs_extlen_t need, delta = 0;
  1617. need = XFS_MIN_FREELIST_PAG(pag, mp);
  1618. if (need > pag->pagf_flcount)
  1619. delta = need - pag->pagf_flcount;
  1620. if (pag->pagf_longest > delta)
  1621. return pag->pagf_longest - delta;
  1622. return pag->pagf_flcount > 0 || pag->pagf_longest > 0;
  1623. }
  1624. /*
  1625. * Decide whether to use this allocation group for this allocation.
  1626. * If so, fix up the btree freelist's size.
  1627. */
  1628. STATIC int /* error */
  1629. xfs_alloc_fix_freelist(
  1630. xfs_alloc_arg_t *args, /* allocation argument structure */
  1631. int flags) /* XFS_ALLOC_FLAG_... */
  1632. {
  1633. xfs_buf_t *agbp; /* agf buffer pointer */
  1634. xfs_agf_t *agf; /* a.g. freespace structure pointer */
  1635. xfs_buf_t *agflbp;/* agfl buffer pointer */
  1636. xfs_agblock_t bno; /* freelist block */
  1637. xfs_extlen_t delta; /* new blocks needed in freelist */
  1638. int error; /* error result code */
  1639. xfs_extlen_t longest;/* longest extent in allocation group */
  1640. xfs_mount_t *mp; /* file system mount point structure */
  1641. xfs_extlen_t need; /* total blocks needed in freelist */
  1642. xfs_perag_t *pag; /* per-ag information structure */
  1643. xfs_alloc_arg_t targs; /* local allocation arguments */
  1644. xfs_trans_t *tp; /* transaction pointer */
  1645. mp = args->mp;
  1646. pag = args->pag;
  1647. tp = args->tp;
  1648. if (!pag->pagf_init) {
  1649. if ((error = xfs_alloc_read_agf(mp, tp, args->agno, flags,
  1650. &agbp)))
  1651. return error;
  1652. if (!pag->pagf_init) {
  1653. ASSERT(flags & XFS_ALLOC_FLAG_TRYLOCK);
  1654. ASSERT(!(flags & XFS_ALLOC_FLAG_FREEING));
  1655. args->agbp = NULL;
  1656. return 0;
  1657. }
  1658. } else
  1659. agbp = NULL;
  1660. /*
  1661. * If this is a metadata preferred pag and we are user data
  1662. * then try somewhere else if we are not being asked to
  1663. * try harder at this point
  1664. */
  1665. if (pag->pagf_metadata && args->userdata &&
  1666. (flags & XFS_ALLOC_FLAG_TRYLOCK)) {
  1667. ASSERT(!(flags & XFS_ALLOC_FLAG_FREEING));
  1668. args->agbp = NULL;
  1669. return 0;
  1670. }
  1671. if (!(flags & XFS_ALLOC_FLAG_FREEING)) {
  1672. /*
  1673. * If it looks like there isn't a long enough extent, or enough
  1674. * total blocks, reject it.
  1675. */
  1676. need = XFS_MIN_FREELIST_PAG(pag, mp);
  1677. longest = xfs_alloc_longest_free_extent(mp, pag);
  1678. if ((args->minlen + args->alignment + args->minalignslop - 1) >
  1679. longest ||
  1680. ((int)(pag->pagf_freeblks + pag->pagf_flcount -
  1681. need - args->total) < (int)args->minleft)) {
  1682. if (agbp)
  1683. xfs_trans_brelse(tp, agbp);
  1684. args->agbp = NULL;
  1685. return 0;
  1686. }
  1687. }
  1688. /*
  1689. * Get the a.g. freespace buffer.
  1690. * Can fail if we're not blocking on locks, and it's held.
  1691. */
  1692. if (agbp == NULL) {
  1693. if ((error = xfs_alloc_read_agf(mp, tp, args->agno, flags,
  1694. &agbp)))
  1695. return error;
  1696. if (agbp == NULL) {
  1697. ASSERT(flags & XFS_ALLOC_FLAG_TRYLOCK);
  1698. ASSERT(!(flags & XFS_ALLOC_FLAG_FREEING));
  1699. args->agbp = NULL;
  1700. return 0;
  1701. }
  1702. }
  1703. /*
  1704. * Figure out how many blocks we should have in the freelist.
  1705. */
  1706. agf = XFS_BUF_TO_AGF(agbp);
  1707. need = XFS_MIN_FREELIST(agf, mp);
  1708. /*
  1709. * If there isn't enough total or single-extent, reject it.
  1710. */
  1711. if (!(flags & XFS_ALLOC_FLAG_FREEING)) {
  1712. delta = need > be32_to_cpu(agf->agf_flcount) ?
  1713. (need - be32_to_cpu(agf->agf_flcount)) : 0;
  1714. longest = be32_to_cpu(agf->agf_longest);
  1715. longest = (longest > delta) ? (longest - delta) :
  1716. (be32_to_cpu(agf->agf_flcount) > 0 || longest > 0);
  1717. if ((args->minlen + args->alignment + args->minalignslop - 1) >
  1718. longest ||
  1719. ((int)(be32_to_cpu(agf->agf_freeblks) +
  1720. be32_to_cpu(agf->agf_flcount) - need - args->total) <
  1721. (int)args->minleft)) {
  1722. xfs_trans_brelse(tp, agbp);
  1723. args->agbp = NULL;
  1724. return 0;
  1725. }
  1726. }
  1727. /*
  1728. * Make the freelist shorter if it's too long.
  1729. */
  1730. while (be32_to_cpu(agf->agf_flcount) > need) {
  1731. xfs_buf_t *bp;
  1732. error = xfs_alloc_get_freelist(tp, agbp, &bno, 0);
  1733. if (error)
  1734. return error;
  1735. if ((error = xfs_free_ag_extent(tp, agbp, args->agno, bno, 1, 1)))
  1736. return error;
  1737. bp = xfs_btree_get_bufs(mp, tp, args->agno, bno, 0);
  1738. xfs_trans_binval(tp, bp);
  1739. }
  1740. /*
  1741. * Initialize the args structure.
  1742. */
  1743. targs.tp = tp;
  1744. targs.mp = mp;
  1745. targs.agbp = agbp;
  1746. targs.agno = args->agno;
  1747. targs.mod = targs.minleft = targs.wasdel = targs.userdata =
  1748. targs.minalignslop = 0;
  1749. targs.alignment = targs.minlen = targs.prod = targs.isfl = 1;
  1750. targs.type = XFS_ALLOCTYPE_THIS_AG;
  1751. targs.pag = pag;
  1752. if ((error = xfs_alloc_read_agfl(mp, tp, targs.agno, &agflbp)))
  1753. return error;
  1754. /*
  1755. * Make the freelist longer if it's too short.
  1756. */
  1757. while (be32_to_cpu(agf->agf_flcount) < need) {
  1758. targs.agbno = 0;
  1759. targs.maxlen = need - be32_to_cpu(agf->agf_flcount);
  1760. /*
  1761. * Allocate as many blocks as possible at once.
  1762. */
  1763. if ((error = xfs_alloc_ag_vextent(&targs))) {
  1764. xfs_trans_brelse(tp, agflbp);
  1765. return error;
  1766. }
  1767. /*
  1768. * Stop if we run out. Won't happen if callers are obeying
  1769. * the restrictions correctly. Can happen for free calls
  1770. * on a completely full ag.
  1771. */
  1772. if (targs.agbno == NULLAGBLOCK) {
  1773. if (flags & XFS_ALLOC_FLAG_FREEING)
  1774. break;
  1775. xfs_trans_brelse(tp, agflbp);
  1776. args->agbp = NULL;
  1777. return 0;
  1778. }
  1779. /*
  1780. * Put each allocated block on the list.
  1781. */
  1782. for (bno = targs.agbno; bno < targs.agbno + targs.len; bno++) {
  1783. error = xfs_alloc_put_freelist(tp, agbp,
  1784. agflbp, bno, 0);
  1785. if (error)
  1786. return error;
  1787. }
  1788. }
  1789. xfs_trans_brelse(tp, agflbp);
  1790. args->agbp = agbp;
  1791. return 0;
  1792. }
  1793. /*
  1794. * Get a block from the freelist.
  1795. * Returns with the buffer for the block gotten.
  1796. */
  1797. int /* error */
  1798. xfs_alloc_get_freelist(
  1799. xfs_trans_t *tp, /* transaction pointer */
  1800. xfs_buf_t *agbp, /* buffer containing the agf structure */
  1801. xfs_agblock_t *bnop, /* block address retrieved from freelist */
  1802. int btreeblk) /* destination is a AGF btree */
  1803. {
  1804. xfs_agf_t *agf; /* a.g. freespace structure */
  1805. xfs_agfl_t *agfl; /* a.g. freelist structure */
  1806. xfs_buf_t *agflbp;/* buffer for a.g. freelist structure */
  1807. xfs_agblock_t bno; /* block number returned */
  1808. int error;
  1809. int logflags;
  1810. xfs_mount_t *mp; /* mount structure */
  1811. xfs_perag_t *pag; /* per allocation group data */
  1812. agf = XFS_BUF_TO_AGF(agbp);
  1813. /*
  1814. * Freelist is empty, give up.
  1815. */
  1816. if (!agf->agf_flcount) {
  1817. *bnop = NULLAGBLOCK;
  1818. return 0;
  1819. }
  1820. /*
  1821. * Read the array of free blocks.
  1822. */
  1823. mp = tp->t_mountp;
  1824. if ((error = xfs_alloc_read_agfl(mp, tp,
  1825. be32_to_cpu(agf->agf_seqno), &agflbp)))
  1826. return error;
  1827. agfl = XFS_BUF_TO_AGFL(agflbp);
  1828. /*
  1829. * Get the block number and update the data structures.
  1830. */
  1831. bno = be32_to_cpu(agfl->agfl_bno[be32_to_cpu(agf->agf_flfirst)]);
  1832. be32_add_cpu(&agf->agf_flfirst, 1);
  1833. xfs_trans_brelse(tp, agflbp);
  1834. if (be32_to_cpu(agf->agf_flfirst) == XFS_AGFL_SIZE(mp))
  1835. agf->agf_flfirst = 0;
  1836. pag = xfs_perag_get(mp, be32_to_cpu(agf->agf_seqno));
  1837. be32_add_cpu(&agf->agf_flcount, -1);
  1838. xfs_trans_agflist_delta(tp, -1);
  1839. pag->pagf_flcount--;
  1840. xfs_perag_put(pag);
  1841. logflags = XFS_AGF_FLFIRST | XFS_AGF_FLCOUNT;
  1842. if (btreeblk) {
  1843. be32_add_cpu(&agf->agf_btreeblks, 1);
  1844. pag->pagf_btreeblks++;
  1845. logflags |= XFS_AGF_BTREEBLKS;
  1846. }
  1847. xfs_alloc_log_agf(tp, agbp, logflags);
  1848. *bnop = bno;
  1849. return 0;
  1850. }
  1851. /*
  1852. * Log the given fields from the agf structure.
  1853. */
  1854. void
  1855. xfs_alloc_log_agf(
  1856. xfs_trans_t *tp, /* transaction pointer */
  1857. xfs_buf_t *bp, /* buffer for a.g. freelist header */
  1858. int fields) /* mask of fields to be logged (XFS_AGF_...) */
  1859. {
  1860. int first; /* first byte offset */
  1861. int last; /* last byte offset */
  1862. static const short offsets[] = {
  1863. offsetof(xfs_agf_t, agf_magicnum),
  1864. offsetof(xfs_agf_t, agf_versionnum),
  1865. offsetof(xfs_agf_t, agf_seqno),
  1866. offsetof(xfs_agf_t, agf_length),
  1867. offsetof(xfs_agf_t, agf_roots[0]),
  1868. offsetof(xfs_agf_t, agf_levels[0]),
  1869. offsetof(xfs_agf_t, agf_flfirst),
  1870. offsetof(xfs_agf_t, agf_fllast),
  1871. offsetof(xfs_agf_t, agf_flcount),
  1872. offsetof(xfs_agf_t, agf_freeblks),
  1873. offsetof(xfs_agf_t, agf_longest),
  1874. offsetof(xfs_agf_t, agf_btreeblks),
  1875. sizeof(xfs_agf_t)
  1876. };
  1877. trace_xfs_agf(tp->t_mountp, XFS_BUF_TO_AGF(bp), fields, _RET_IP_);
  1878. xfs_btree_offsets(fields, offsets, XFS_AGF_NUM_BITS, &first, &last);
  1879. xfs_trans_log_buf(tp, bp, (uint)first, (uint)last);
  1880. }
  1881. /*
  1882. * Interface for inode allocation to force the pag data to be initialized.
  1883. */
  1884. int /* error */
  1885. xfs_alloc_pagf_init(
  1886. xfs_mount_t *mp, /* file system mount structure */
  1887. xfs_trans_t *tp, /* transaction pointer */
  1888. xfs_agnumber_t agno, /* allocation group number */
  1889. int flags) /* XFS_ALLOC_FLAGS_... */
  1890. {
  1891. xfs_buf_t *bp;
  1892. int error;
  1893. if ((error = xfs_alloc_read_agf(mp, tp, agno, flags, &bp)))
  1894. return error;
  1895. if (bp)
  1896. xfs_trans_brelse(tp, bp);
  1897. return 0;
  1898. }
  1899. /*
  1900. * Put the block on the freelist for the allocation group.
  1901. */
  1902. int /* error */
  1903. xfs_alloc_put_freelist(
  1904. xfs_trans_t *tp, /* transaction pointer */
  1905. xfs_buf_t *agbp, /* buffer for a.g. freelist header */
  1906. xfs_buf_t *agflbp,/* buffer for a.g. free block array */
  1907. xfs_agblock_t bno, /* block being freed */
  1908. int btreeblk) /* block came from a AGF btree */
  1909. {
  1910. xfs_agf_t *agf; /* a.g. freespace structure */
  1911. xfs_agfl_t *agfl; /* a.g. free block array */
  1912. __be32 *blockp;/* pointer to array entry */
  1913. int error;
  1914. int logflags;
  1915. xfs_mount_t *mp; /* mount structure */
  1916. xfs_perag_t *pag; /* per allocation group data */
  1917. agf = XFS_BUF_TO_AGF(agbp);
  1918. mp = tp->t_mountp;
  1919. if (!agflbp && (error = xfs_alloc_read_agfl(mp, tp,
  1920. be32_to_cpu(agf->agf_seqno), &agflbp)))
  1921. return error;
  1922. agfl = XFS_BUF_TO_AGFL(agflbp);
  1923. be32_add_cpu(&agf->agf_fllast, 1);
  1924. if (be32_to_cpu(agf->agf_fllast) == XFS_AGFL_SIZE(mp))
  1925. agf->agf_fllast = 0;
  1926. pag = xfs_perag_get(mp, be32_to_cpu(agf->agf_seqno));
  1927. be32_add_cpu(&agf->agf_flcount, 1);
  1928. xfs_trans_agflist_delta(tp, 1);
  1929. pag->pagf_flcount++;
  1930. logflags = XFS_AGF_FLLAST | XFS_AGF_FLCOUNT;
  1931. if (btreeblk) {
  1932. be32_add_cpu(&agf->agf_btreeblks, -1);
  1933. pag->pagf_btreeblks--;
  1934. logflags |= XFS_AGF_BTREEBLKS;
  1935. }
  1936. xfs_perag_put(pag);
  1937. xfs_alloc_log_agf(tp, agbp, logflags);
  1938. ASSERT(be32_to_cpu(agf->agf_flcount) <= XFS_AGFL_SIZE(mp));
  1939. blockp = &agfl->agfl_bno[be32_to_cpu(agf->agf_fllast)];
  1940. *blockp = cpu_to_be32(bno);
  1941. xfs_alloc_log_agf(tp, agbp, logflags);
  1942. xfs_trans_log_buf(tp, agflbp,
  1943. (int)((xfs_caddr_t)blockp - (xfs_caddr_t)agfl),
  1944. (int)((xfs_caddr_t)blockp - (xfs_caddr_t)agfl +
  1945. sizeof(xfs_agblock_t) - 1));
  1946. return 0;
  1947. }
  1948. /*
  1949. * Read in the allocation group header (free/alloc section).
  1950. */
  1951. int /* error */
  1952. xfs_read_agf(
  1953. struct xfs_mount *mp, /* mount point structure */
  1954. struct xfs_trans *tp, /* transaction pointer */
  1955. xfs_agnumber_t agno, /* allocation group number */
  1956. int flags, /* XFS_BUF_ */
  1957. struct xfs_buf **bpp) /* buffer for the ag freelist header */
  1958. {
  1959. struct xfs_agf *agf; /* ag freelist header */
  1960. int agf_ok; /* set if agf is consistent */
  1961. int error;
  1962. ASSERT(agno != NULLAGNUMBER);
  1963. error = xfs_trans_read_buf(
  1964. mp, tp, mp->m_ddev_targp,
  1965. XFS_AG_DADDR(mp, agno, XFS_AGF_DADDR(mp)),
  1966. XFS_FSS_TO_BB(mp, 1), flags, bpp);
  1967. if (error)
  1968. return error;
  1969. if (!*bpp)
  1970. return 0;
  1971. ASSERT(!(*bpp)->b_error);
  1972. agf = XFS_BUF_TO_AGF(*bpp);
  1973. /*
  1974. * Validate the magic number of the agf block.
  1975. */
  1976. agf_ok =
  1977. agf->agf_magicnum == cpu_to_be32(XFS_AGF_MAGIC) &&
  1978. XFS_AGF_GOOD_VERSION(be32_to_cpu(agf->agf_versionnum)) &&
  1979. be32_to_cpu(agf->agf_freeblks) <= be32_to_cpu(agf->agf_length) &&
  1980. be32_to_cpu(agf->agf_flfirst) < XFS_AGFL_SIZE(mp) &&
  1981. be32_to_cpu(agf->agf_fllast) < XFS_AGFL_SIZE(mp) &&
  1982. be32_to_cpu(agf->agf_flcount) <= XFS_AGFL_SIZE(mp) &&
  1983. be32_to_cpu(agf->agf_seqno) == agno;
  1984. if (xfs_sb_version_haslazysbcount(&mp->m_sb))
  1985. agf_ok = agf_ok && be32_to_cpu(agf->agf_btreeblks) <=
  1986. be32_to_cpu(agf->agf_length);
  1987. if (unlikely(XFS_TEST_ERROR(!agf_ok, mp, XFS_ERRTAG_ALLOC_READ_AGF,
  1988. XFS_RANDOM_ALLOC_READ_AGF))) {
  1989. XFS_CORRUPTION_ERROR("xfs_alloc_read_agf",
  1990. XFS_ERRLEVEL_LOW, mp, agf);
  1991. xfs_trans_brelse(tp, *bpp);
  1992. return XFS_ERROR(EFSCORRUPTED);
  1993. }
  1994. xfs_buf_set_ref(*bpp, XFS_AGF_REF);
  1995. return 0;
  1996. }
  1997. /*
  1998. * Read in the allocation group header (free/alloc section).
  1999. */
  2000. int /* error */
  2001. xfs_alloc_read_agf(
  2002. struct xfs_mount *mp, /* mount point structure */
  2003. struct xfs_trans *tp, /* transaction pointer */
  2004. xfs_agnumber_t agno, /* allocation group number */
  2005. int flags, /* XFS_ALLOC_FLAG_... */
  2006. struct xfs_buf **bpp) /* buffer for the ag freelist header */
  2007. {
  2008. struct xfs_agf *agf; /* ag freelist header */
  2009. struct xfs_perag *pag; /* per allocation group data */
  2010. int error;
  2011. ASSERT(agno != NULLAGNUMBER);
  2012. error = xfs_read_agf(mp, tp, agno,
  2013. (flags & XFS_ALLOC_FLAG_TRYLOCK) ? XBF_TRYLOCK : 0,
  2014. bpp);
  2015. if (error)
  2016. return error;
  2017. if (!*bpp)
  2018. return 0;
  2019. ASSERT(!(*bpp)->b_error);
  2020. agf = XFS_BUF_TO_AGF(*bpp);
  2021. pag = xfs_perag_get(mp, agno);
  2022. if (!pag->pagf_init) {
  2023. pag->pagf_freeblks = be32_to_cpu(agf->agf_freeblks);
  2024. pag->pagf_btreeblks = be32_to_cpu(agf->agf_btreeblks);
  2025. pag->pagf_flcount = be32_to_cpu(agf->agf_flcount);
  2026. pag->pagf_longest = be32_to_cpu(agf->agf_longest);
  2027. pag->pagf_levels[XFS_BTNUM_BNOi] =
  2028. be32_to_cpu(agf->agf_levels[XFS_BTNUM_BNOi]);
  2029. pag->pagf_levels[XFS_BTNUM_CNTi] =
  2030. be32_to_cpu(agf->agf_levels[XFS_BTNUM_CNTi]);
  2031. spin_lock_init(&pag->pagb_lock);
  2032. pag->pagb_count = 0;
  2033. pag->pagb_tree = RB_ROOT;
  2034. pag->pagf_init = 1;
  2035. }
  2036. #ifdef DEBUG
  2037. else if (!XFS_FORCED_SHUTDOWN(mp)) {
  2038. ASSERT(pag->pagf_freeblks == be32_to_cpu(agf->agf_freeblks));
  2039. ASSERT(pag->pagf_btreeblks == be32_to_cpu(agf->agf_btreeblks));
  2040. ASSERT(pag->pagf_flcount == be32_to_cpu(agf->agf_flcount));
  2041. ASSERT(pag->pagf_longest == be32_to_cpu(agf->agf_longest));
  2042. ASSERT(pag->pagf_levels[XFS_BTNUM_BNOi] ==
  2043. be32_to_cpu(agf->agf_levels[XFS_BTNUM_BNOi]));
  2044. ASSERT(pag->pagf_levels[XFS_BTNUM_CNTi] ==
  2045. be32_to_cpu(agf->agf_levels[XFS_BTNUM_CNTi]));
  2046. }
  2047. #endif
  2048. xfs_perag_put(pag);
  2049. return 0;
  2050. }
  2051. /*
  2052. * Allocate an extent (variable-size).
  2053. * Depending on the allocation type, we either look in a single allocation
  2054. * group or loop over the allocation groups to find the result.
  2055. */
  2056. int /* error */
  2057. __xfs_alloc_vextent(
  2058. xfs_alloc_arg_t *args) /* allocation argument structure */
  2059. {
  2060. xfs_agblock_t agsize; /* allocation group size */
  2061. int error;
  2062. int flags; /* XFS_ALLOC_FLAG_... locking flags */
  2063. xfs_extlen_t minleft;/* minimum left value, temp copy */
  2064. xfs_mount_t *mp; /* mount structure pointer */
  2065. xfs_agnumber_t sagno; /* starting allocation group number */
  2066. xfs_alloctype_t type; /* input allocation type */
  2067. int bump_rotor = 0;
  2068. int no_min = 0;
  2069. xfs_agnumber_t rotorstep = xfs_rotorstep; /* inode32 agf stepper */
  2070. mp = args->mp;
  2071. type = args->otype = args->type;
  2072. args->agbno = NULLAGBLOCK;
  2073. /*
  2074. * Just fix this up, for the case where the last a.g. is shorter
  2075. * (or there's only one a.g.) and the caller couldn't easily figure
  2076. * that out (xfs_bmap_alloc).
  2077. */
  2078. agsize = mp->m_sb.sb_agblocks;
  2079. if (args->maxlen > agsize)
  2080. args->maxlen = agsize;
  2081. if (args->alignment == 0)
  2082. args->alignment = 1;
  2083. ASSERT(XFS_FSB_TO_AGNO(mp, args->fsbno) < mp->m_sb.sb_agcount);
  2084. ASSERT(XFS_FSB_TO_AGBNO(mp, args->fsbno) < agsize);
  2085. ASSERT(args->minlen <= args->maxlen);
  2086. ASSERT(args->minlen <= agsize);
  2087. ASSERT(args->mod < args->prod);
  2088. if (XFS_FSB_TO_AGNO(mp, args->fsbno) >= mp->m_sb.sb_agcount ||
  2089. XFS_FSB_TO_AGBNO(mp, args->fsbno) >= agsize ||
  2090. args->minlen > args->maxlen || args->minlen > agsize ||
  2091. args->mod >= args->prod) {
  2092. args->fsbno = NULLFSBLOCK;
  2093. trace_xfs_alloc_vextent_badargs(args);
  2094. return 0;
  2095. }
  2096. minleft = args->minleft;
  2097. switch (type) {
  2098. case XFS_ALLOCTYPE_THIS_AG:
  2099. case XFS_ALLOCTYPE_NEAR_BNO:
  2100. case XFS_ALLOCTYPE_THIS_BNO:
  2101. /*
  2102. * These three force us into a single a.g.
  2103. */
  2104. args->agno = XFS_FSB_TO_AGNO(mp, args->fsbno);
  2105. args->pag = xfs_perag_get(mp, args->agno);
  2106. args->minleft = 0;
  2107. error = xfs_alloc_fix_freelist(args, 0);
  2108. args->minleft = minleft;
  2109. if (error) {
  2110. trace_xfs_alloc_vextent_nofix(args);
  2111. goto error0;
  2112. }
  2113. if (!args->agbp) {
  2114. trace_xfs_alloc_vextent_noagbp(args);
  2115. break;
  2116. }
  2117. args->agbno = XFS_FSB_TO_AGBNO(mp, args->fsbno);
  2118. if ((error = xfs_alloc_ag_vextent(args)))
  2119. goto error0;
  2120. break;
  2121. case XFS_ALLOCTYPE_START_BNO:
  2122. /*
  2123. * Try near allocation first, then anywhere-in-ag after
  2124. * the first a.g. fails.
  2125. */
  2126. if ((args->userdata == XFS_ALLOC_INITIAL_USER_DATA) &&
  2127. (mp->m_flags & XFS_MOUNT_32BITINODES)) {
  2128. args->fsbno = XFS_AGB_TO_FSB(mp,
  2129. ((mp->m_agfrotor / rotorstep) %
  2130. mp->m_sb.sb_agcount), 0);
  2131. bump_rotor = 1;
  2132. }
  2133. args->agbno = XFS_FSB_TO_AGBNO(mp, args->fsbno);
  2134. args->type = XFS_ALLOCTYPE_NEAR_BNO;
  2135. /* FALLTHROUGH */
  2136. case XFS_ALLOCTYPE_ANY_AG:
  2137. case XFS_ALLOCTYPE_START_AG:
  2138. case XFS_ALLOCTYPE_FIRST_AG:
  2139. /*
  2140. * Rotate through the allocation groups looking for a winner.
  2141. */
  2142. if (type == XFS_ALLOCTYPE_ANY_AG) {
  2143. /*
  2144. * Start with the last place we left off.
  2145. */
  2146. args->agno = sagno = (mp->m_agfrotor / rotorstep) %
  2147. mp->m_sb.sb_agcount;
  2148. args->type = XFS_ALLOCTYPE_THIS_AG;
  2149. flags = XFS_ALLOC_FLAG_TRYLOCK;
  2150. } else if (type == XFS_ALLOCTYPE_FIRST_AG) {
  2151. /*
  2152. * Start with allocation group given by bno.
  2153. */
  2154. args->agno = XFS_FSB_TO_AGNO(mp, args->fsbno);
  2155. args->type = XFS_ALLOCTYPE_THIS_AG;
  2156. sagno = 0;
  2157. flags = 0;
  2158. } else {
  2159. if (type == XFS_ALLOCTYPE_START_AG)
  2160. args->type = XFS_ALLOCTYPE_THIS_AG;
  2161. /*
  2162. * Start with the given allocation group.
  2163. */
  2164. args->agno = sagno = XFS_FSB_TO_AGNO(mp, args->fsbno);
  2165. flags = XFS_ALLOC_FLAG_TRYLOCK;
  2166. }
  2167. /*
  2168. * Loop over allocation groups twice; first time with
  2169. * trylock set, second time without.
  2170. */
  2171. for (;;) {
  2172. args->pag = xfs_perag_get(mp, args->agno);
  2173. if (no_min) args->minleft = 0;
  2174. error = xfs_alloc_fix_freelist(args, flags);
  2175. args->minleft = minleft;
  2176. if (error) {
  2177. trace_xfs_alloc_vextent_nofix(args);
  2178. goto error0;
  2179. }
  2180. /*
  2181. * If we get a buffer back then the allocation will fly.
  2182. */
  2183. if (args->agbp) {
  2184. if ((error = xfs_alloc_ag_vextent(args)))
  2185. goto error0;
  2186. break;
  2187. }
  2188. trace_xfs_alloc_vextent_loopfailed(args);
  2189. /*
  2190. * Didn't work, figure out the next iteration.
  2191. */
  2192. if (args->agno == sagno &&
  2193. type == XFS_ALLOCTYPE_START_BNO)
  2194. args->type = XFS_ALLOCTYPE_THIS_AG;
  2195. /*
  2196. * For the first allocation, we can try any AG to get
  2197. * space. However, if we already have allocated a
  2198. * block, we don't want to try AGs whose number is below
  2199. * sagno. Otherwise, we may end up with out-of-order
  2200. * locking of AGF, which might cause deadlock.
  2201. */
  2202. if (++(args->agno) == mp->m_sb.sb_agcount) {
  2203. if (args->firstblock != NULLFSBLOCK)
  2204. args->agno = sagno;
  2205. else
  2206. args->agno = 0;
  2207. }
  2208. /*
  2209. * Reached the starting a.g., must either be done
  2210. * or switch to non-trylock mode.
  2211. */
  2212. if (args->agno == sagno) {
  2213. if (no_min == 1) {
  2214. args->agbno = NULLAGBLOCK;
  2215. trace_xfs_alloc_vextent_allfailed(args);
  2216. break;
  2217. }
  2218. if (flags == 0) {
  2219. no_min = 1;
  2220. } else {
  2221. flags = 0;
  2222. if (type == XFS_ALLOCTYPE_START_BNO) {
  2223. args->agbno = XFS_FSB_TO_AGBNO(mp,
  2224. args->fsbno);
  2225. args->type = XFS_ALLOCTYPE_NEAR_BNO;
  2226. }
  2227. }
  2228. }
  2229. xfs_perag_put(args->pag);
  2230. }
  2231. if (bump_rotor || (type == XFS_ALLOCTYPE_ANY_AG)) {
  2232. if (args->agno == sagno)
  2233. mp->m_agfrotor = (mp->m_agfrotor + 1) %
  2234. (mp->m_sb.sb_agcount * rotorstep);
  2235. else
  2236. mp->m_agfrotor = (args->agno * rotorstep + 1) %
  2237. (mp->m_sb.sb_agcount * rotorstep);
  2238. }
  2239. break;
  2240. default:
  2241. ASSERT(0);
  2242. /* NOTREACHED */
  2243. }
  2244. if (args->agbno == NULLAGBLOCK)
  2245. args->fsbno = NULLFSBLOCK;
  2246. else {
  2247. args->fsbno = XFS_AGB_TO_FSB(mp, args->agno, args->agbno);
  2248. #ifdef DEBUG
  2249. ASSERT(args->len >= args->minlen);
  2250. ASSERT(args->len <= args->maxlen);
  2251. ASSERT(args->agbno % args->alignment == 0);
  2252. XFS_AG_CHECK_DADDR(mp, XFS_FSB_TO_DADDR(mp, args->fsbno),
  2253. args->len);
  2254. #endif
  2255. }
  2256. xfs_perag_put(args->pag);
  2257. return 0;
  2258. error0:
  2259. xfs_perag_put(args->pag);
  2260. return error;
  2261. }
  2262. static void
  2263. xfs_alloc_vextent_worker(
  2264. struct work_struct *work)
  2265. {
  2266. struct xfs_alloc_arg *args = container_of(work,
  2267. struct xfs_alloc_arg, work);
  2268. unsigned long pflags;
  2269. /* we are in a transaction context here */
  2270. current_set_flags_nested(&pflags, PF_FSTRANS);
  2271. args->result = __xfs_alloc_vextent(args);
  2272. complete(args->done);
  2273. current_restore_flags_nested(&pflags, PF_FSTRANS);
  2274. }
  2275. int /* error */
  2276. xfs_alloc_vextent(
  2277. xfs_alloc_arg_t *args) /* allocation argument structure */
  2278. {
  2279. DECLARE_COMPLETION_ONSTACK(done);
  2280. args->done = &done;
  2281. INIT_WORK(&args->work, xfs_alloc_vextent_worker);
  2282. queue_work(xfs_alloc_wq, &args->work);
  2283. wait_for_completion(&done);
  2284. return args->result;
  2285. }
  2286. /*
  2287. * Free an extent.
  2288. * Just break up the extent address and hand off to xfs_free_ag_extent
  2289. * after fixing up the freelist.
  2290. */
  2291. int /* error */
  2292. xfs_free_extent(
  2293. xfs_trans_t *tp, /* transaction pointer */
  2294. xfs_fsblock_t bno, /* starting block number of extent */
  2295. xfs_extlen_t len) /* length of extent */
  2296. {
  2297. xfs_alloc_arg_t args;
  2298. int error;
  2299. ASSERT(len != 0);
  2300. memset(&args, 0, sizeof(xfs_alloc_arg_t));
  2301. args.tp = tp;
  2302. args.mp = tp->t_mountp;
  2303. /*
  2304. * validate that the block number is legal - the enables us to detect
  2305. * and handle a silent filesystem corruption rather than crashing.
  2306. */
  2307. args.agno = XFS_FSB_TO_AGNO(args.mp, bno);
  2308. if (args.agno >= args.mp->m_sb.sb_agcount)
  2309. return EFSCORRUPTED;
  2310. args.agbno = XFS_FSB_TO_AGBNO(args.mp, bno);
  2311. if (args.agbno >= args.mp->m_sb.sb_agblocks)
  2312. return EFSCORRUPTED;
  2313. args.pag = xfs_perag_get(args.mp, args.agno);
  2314. ASSERT(args.pag);
  2315. error = xfs_alloc_fix_freelist(&args, XFS_ALLOC_FLAG_FREEING);
  2316. if (error)
  2317. goto error0;
  2318. /* validate the extent size is legal now we have the agf locked */
  2319. if (args.agbno + len >
  2320. be32_to_cpu(XFS_BUF_TO_AGF(args.agbp)->agf_length)) {
  2321. error = EFSCORRUPTED;
  2322. goto error0;
  2323. }
  2324. error = xfs_free_ag_extent(tp, args.agbp, args.agno, args.agbno, len, 0);
  2325. if (!error)
  2326. xfs_alloc_busy_insert(tp, args.agno, args.agbno, len, 0);
  2327. error0:
  2328. xfs_perag_put(args.pag);
  2329. return error;
  2330. }
  2331. void
  2332. xfs_alloc_busy_insert(
  2333. struct xfs_trans *tp,
  2334. xfs_agnumber_t agno,
  2335. xfs_agblock_t bno,
  2336. xfs_extlen_t len,
  2337. unsigned int flags)
  2338. {
  2339. struct xfs_busy_extent *new;
  2340. struct xfs_busy_extent *busyp;
  2341. struct xfs_perag *pag;
  2342. struct rb_node **rbp;
  2343. struct rb_node *parent = NULL;
  2344. new = kmem_zalloc(sizeof(struct xfs_busy_extent), KM_MAYFAIL);
  2345. if (!new) {
  2346. /*
  2347. * No Memory! Since it is now not possible to track the free
  2348. * block, make this a synchronous transaction to insure that
  2349. * the block is not reused before this transaction commits.
  2350. */
  2351. trace_xfs_alloc_busy_enomem(tp->t_mountp, agno, bno, len);
  2352. xfs_trans_set_sync(tp);
  2353. return;
  2354. }
  2355. new->agno = agno;
  2356. new->bno = bno;
  2357. new->length = len;
  2358. INIT_LIST_HEAD(&new->list);
  2359. new->flags = flags;
  2360. /* trace before insert to be able to see failed inserts */
  2361. trace_xfs_alloc_busy(tp->t_mountp, agno, bno, len);
  2362. pag = xfs_perag_get(tp->t_mountp, new->agno);
  2363. spin_lock(&pag->pagb_lock);
  2364. rbp = &pag->pagb_tree.rb_node;
  2365. while (*rbp) {
  2366. parent = *rbp;
  2367. busyp = rb_entry(parent, struct xfs_busy_extent, rb_node);
  2368. if (new->bno < busyp->bno) {
  2369. rbp = &(*rbp)->rb_left;
  2370. ASSERT(new->bno + new->length <= busyp->bno);
  2371. } else if (new->bno > busyp->bno) {
  2372. rbp = &(*rbp)->rb_right;
  2373. ASSERT(bno >= busyp->bno + busyp->length);
  2374. } else {
  2375. ASSERT(0);
  2376. }
  2377. }
  2378. rb_link_node(&new->rb_node, parent, rbp);
  2379. rb_insert_color(&new->rb_node, &pag->pagb_tree);
  2380. list_add(&new->list, &tp->t_busy);
  2381. spin_unlock(&pag->pagb_lock);
  2382. xfs_perag_put(pag);
  2383. }
  2384. /*
  2385. * Search for a busy extent within the range of the extent we are about to
  2386. * allocate. You need to be holding the busy extent tree lock when calling
  2387. * xfs_alloc_busy_search(). This function returns 0 for no overlapping busy
  2388. * extent, -1 for an overlapping but not exact busy extent, and 1 for an exact
  2389. * match. This is done so that a non-zero return indicates an overlap that
  2390. * will require a synchronous transaction, but it can still be
  2391. * used to distinguish between a partial or exact match.
  2392. */
  2393. int
  2394. xfs_alloc_busy_search(
  2395. struct xfs_mount *mp,
  2396. xfs_agnumber_t agno,
  2397. xfs_agblock_t bno,
  2398. xfs_extlen_t len)
  2399. {
  2400. struct xfs_perag *pag;
  2401. struct rb_node *rbp;
  2402. struct xfs_busy_extent *busyp;
  2403. int match = 0;
  2404. pag = xfs_perag_get(mp, agno);
  2405. spin_lock(&pag->pagb_lock);
  2406. rbp = pag->pagb_tree.rb_node;
  2407. /* find closest start bno overlap */
  2408. while (rbp) {
  2409. busyp = rb_entry(rbp, struct xfs_busy_extent, rb_node);
  2410. if (bno < busyp->bno) {
  2411. /* may overlap, but exact start block is lower */
  2412. if (bno + len > busyp->bno)
  2413. match = -1;
  2414. rbp = rbp->rb_left;
  2415. } else if (bno > busyp->bno) {
  2416. /* may overlap, but exact start block is higher */
  2417. if (bno < busyp->bno + busyp->length)
  2418. match = -1;
  2419. rbp = rbp->rb_right;
  2420. } else {
  2421. /* bno matches busyp, length determines exact match */
  2422. match = (busyp->length == len) ? 1 : -1;
  2423. break;
  2424. }
  2425. }
  2426. spin_unlock(&pag->pagb_lock);
  2427. xfs_perag_put(pag);
  2428. return match;
  2429. }
  2430. /*
  2431. * The found free extent [fbno, fend] overlaps part or all of the given busy
  2432. * extent. If the overlap covers the beginning, the end, or all of the busy
  2433. * extent, the overlapping portion can be made unbusy and used for the
  2434. * allocation. We can't split a busy extent because we can't modify a
  2435. * transaction/CIL context busy list, but we can update an entries block
  2436. * number or length.
  2437. *
  2438. * Returns true if the extent can safely be reused, or false if the search
  2439. * needs to be restarted.
  2440. */
  2441. STATIC bool
  2442. xfs_alloc_busy_update_extent(
  2443. struct xfs_mount *mp,
  2444. struct xfs_perag *pag,
  2445. struct xfs_busy_extent *busyp,
  2446. xfs_agblock_t fbno,
  2447. xfs_extlen_t flen,
  2448. bool userdata)
  2449. {
  2450. xfs_agblock_t fend = fbno + flen;
  2451. xfs_agblock_t bbno = busyp->bno;
  2452. xfs_agblock_t bend = bbno + busyp->length;
  2453. /*
  2454. * This extent is currently being discarded. Give the thread
  2455. * performing the discard a chance to mark the extent unbusy
  2456. * and retry.
  2457. */
  2458. if (busyp->flags & XFS_ALLOC_BUSY_DISCARDED) {
  2459. spin_unlock(&pag->pagb_lock);
  2460. delay(1);
  2461. spin_lock(&pag->pagb_lock);
  2462. return false;
  2463. }
  2464. /*
  2465. * If there is a busy extent overlapping a user allocation, we have
  2466. * no choice but to force the log and retry the search.
  2467. *
  2468. * Fortunately this does not happen during normal operation, but
  2469. * only if the filesystem is very low on space and has to dip into
  2470. * the AGFL for normal allocations.
  2471. */
  2472. if (userdata)
  2473. goto out_force_log;
  2474. if (bbno < fbno && bend > fend) {
  2475. /*
  2476. * Case 1:
  2477. * bbno bend
  2478. * +BBBBBBBBBBBBBBBBB+
  2479. * +---------+
  2480. * fbno fend
  2481. */
  2482. /*
  2483. * We would have to split the busy extent to be able to track
  2484. * it correct, which we cannot do because we would have to
  2485. * modify the list of busy extents attached to the transaction
  2486. * or CIL context, which is immutable.
  2487. *
  2488. * Force out the log to clear the busy extent and retry the
  2489. * search.
  2490. */
  2491. goto out_force_log;
  2492. } else if (bbno >= fbno && bend <= fend) {
  2493. /*
  2494. * Case 2:
  2495. * bbno bend
  2496. * +BBBBBBBBBBBBBBBBB+
  2497. * +-----------------+
  2498. * fbno fend
  2499. *
  2500. * Case 3:
  2501. * bbno bend
  2502. * +BBBBBBBBBBBBBBBBB+
  2503. * +--------------------------+
  2504. * fbno fend
  2505. *
  2506. * Case 4:
  2507. * bbno bend
  2508. * +BBBBBBBBBBBBBBBBB+
  2509. * +--------------------------+
  2510. * fbno fend
  2511. *
  2512. * Case 5:
  2513. * bbno bend
  2514. * +BBBBBBBBBBBBBBBBB+
  2515. * +-----------------------------------+
  2516. * fbno fend
  2517. *
  2518. */
  2519. /*
  2520. * The busy extent is fully covered by the extent we are
  2521. * allocating, and can simply be removed from the rbtree.
  2522. * However we cannot remove it from the immutable list
  2523. * tracking busy extents in the transaction or CIL context,
  2524. * so set the length to zero to mark it invalid.
  2525. *
  2526. * We also need to restart the busy extent search from the
  2527. * tree root, because erasing the node can rearrange the
  2528. * tree topology.
  2529. */
  2530. rb_erase(&busyp->rb_node, &pag->pagb_tree);
  2531. busyp->length = 0;
  2532. return false;
  2533. } else if (fend < bend) {
  2534. /*
  2535. * Case 6:
  2536. * bbno bend
  2537. * +BBBBBBBBBBBBBBBBB+
  2538. * +---------+
  2539. * fbno fend
  2540. *
  2541. * Case 7:
  2542. * bbno bend
  2543. * +BBBBBBBBBBBBBBBBB+
  2544. * +------------------+
  2545. * fbno fend
  2546. *
  2547. */
  2548. busyp->bno = fend;
  2549. } else if (bbno < fbno) {
  2550. /*
  2551. * Case 8:
  2552. * bbno bend
  2553. * +BBBBBBBBBBBBBBBBB+
  2554. * +-------------+
  2555. * fbno fend
  2556. *
  2557. * Case 9:
  2558. * bbno bend
  2559. * +BBBBBBBBBBBBBBBBB+
  2560. * +----------------------+
  2561. * fbno fend
  2562. */
  2563. busyp->length = fbno - busyp->bno;
  2564. } else {
  2565. ASSERT(0);
  2566. }
  2567. trace_xfs_alloc_busy_reuse(mp, pag->pag_agno, fbno, flen);
  2568. return true;
  2569. out_force_log:
  2570. spin_unlock(&pag->pagb_lock);
  2571. xfs_log_force(mp, XFS_LOG_SYNC);
  2572. trace_xfs_alloc_busy_force(mp, pag->pag_agno, fbno, flen);
  2573. spin_lock(&pag->pagb_lock);
  2574. return false;
  2575. }
  2576. /*
  2577. * For a given extent [fbno, flen], make sure we can reuse it safely.
  2578. */
  2579. void
  2580. xfs_alloc_busy_reuse(
  2581. struct xfs_mount *mp,
  2582. xfs_agnumber_t agno,
  2583. xfs_agblock_t fbno,
  2584. xfs_extlen_t flen,
  2585. bool userdata)
  2586. {
  2587. struct xfs_perag *pag;
  2588. struct rb_node *rbp;
  2589. ASSERT(flen > 0);
  2590. pag = xfs_perag_get(mp, agno);
  2591. spin_lock(&pag->pagb_lock);
  2592. restart:
  2593. rbp = pag->pagb_tree.rb_node;
  2594. while (rbp) {
  2595. struct xfs_busy_extent *busyp =
  2596. rb_entry(rbp, struct xfs_busy_extent, rb_node);
  2597. xfs_agblock_t bbno = busyp->bno;
  2598. xfs_agblock_t bend = bbno + busyp->length;
  2599. if (fbno + flen <= bbno) {
  2600. rbp = rbp->rb_left;
  2601. continue;
  2602. } else if (fbno >= bend) {
  2603. rbp = rbp->rb_right;
  2604. continue;
  2605. }
  2606. if (!xfs_alloc_busy_update_extent(mp, pag, busyp, fbno, flen,
  2607. userdata))
  2608. goto restart;
  2609. }
  2610. spin_unlock(&pag->pagb_lock);
  2611. xfs_perag_put(pag);
  2612. }
  2613. /*
  2614. * For a given extent [fbno, flen], search the busy extent list to find a
  2615. * subset of the extent that is not busy. If *rlen is smaller than
  2616. * args->minlen no suitable extent could be found, and the higher level
  2617. * code needs to force out the log and retry the allocation.
  2618. */
  2619. STATIC void
  2620. xfs_alloc_busy_trim(
  2621. struct xfs_alloc_arg *args,
  2622. xfs_agblock_t bno,
  2623. xfs_extlen_t len,
  2624. xfs_agblock_t *rbno,
  2625. xfs_extlen_t *rlen)
  2626. {
  2627. xfs_agblock_t fbno;
  2628. xfs_extlen_t flen;
  2629. struct rb_node *rbp;
  2630. ASSERT(len > 0);
  2631. spin_lock(&args->pag->pagb_lock);
  2632. restart:
  2633. fbno = bno;
  2634. flen = len;
  2635. rbp = args->pag->pagb_tree.rb_node;
  2636. while (rbp && flen >= args->minlen) {
  2637. struct xfs_busy_extent *busyp =
  2638. rb_entry(rbp, struct xfs_busy_extent, rb_node);
  2639. xfs_agblock_t fend = fbno + flen;
  2640. xfs_agblock_t bbno = busyp->bno;
  2641. xfs_agblock_t bend = bbno + busyp->length;
  2642. if (fend <= bbno) {
  2643. rbp = rbp->rb_left;
  2644. continue;
  2645. } else if (fbno >= bend) {
  2646. rbp = rbp->rb_right;
  2647. continue;
  2648. }
  2649. /*
  2650. * If this is a metadata allocation, try to reuse the busy
  2651. * extent instead of trimming the allocation.
  2652. */
  2653. if (!args->userdata &&
  2654. !(busyp->flags & XFS_ALLOC_BUSY_DISCARDED)) {
  2655. if (!xfs_alloc_busy_update_extent(args->mp, args->pag,
  2656. busyp, fbno, flen,
  2657. false))
  2658. goto restart;
  2659. continue;
  2660. }
  2661. if (bbno <= fbno) {
  2662. /* start overlap */
  2663. /*
  2664. * Case 1:
  2665. * bbno bend
  2666. * +BBBBBBBBBBBBBBBBB+
  2667. * +---------+
  2668. * fbno fend
  2669. *
  2670. * Case 2:
  2671. * bbno bend
  2672. * +BBBBBBBBBBBBBBBBB+
  2673. * +-------------+
  2674. * fbno fend
  2675. *
  2676. * Case 3:
  2677. * bbno bend
  2678. * +BBBBBBBBBBBBBBBBB+
  2679. * +-------------+
  2680. * fbno fend
  2681. *
  2682. * Case 4:
  2683. * bbno bend
  2684. * +BBBBBBBBBBBBBBBBB+
  2685. * +-----------------+
  2686. * fbno fend
  2687. *
  2688. * No unbusy region in extent, return failure.
  2689. */
  2690. if (fend <= bend)
  2691. goto fail;
  2692. /*
  2693. * Case 5:
  2694. * bbno bend
  2695. * +BBBBBBBBBBBBBBBBB+
  2696. * +----------------------+
  2697. * fbno fend
  2698. *
  2699. * Case 6:
  2700. * bbno bend
  2701. * +BBBBBBBBBBBBBBBBB+
  2702. * +--------------------------+
  2703. * fbno fend
  2704. *
  2705. * Needs to be trimmed to:
  2706. * +-------+
  2707. * fbno fend
  2708. */
  2709. fbno = bend;
  2710. } else if (bend >= fend) {
  2711. /* end overlap */
  2712. /*
  2713. * Case 7:
  2714. * bbno bend
  2715. * +BBBBBBBBBBBBBBBBB+
  2716. * +------------------+
  2717. * fbno fend
  2718. *
  2719. * Case 8:
  2720. * bbno bend
  2721. * +BBBBBBBBBBBBBBBBB+
  2722. * +--------------------------+
  2723. * fbno fend
  2724. *
  2725. * Needs to be trimmed to:
  2726. * +-------+
  2727. * fbno fend
  2728. */
  2729. fend = bbno;
  2730. } else {
  2731. /* middle overlap */
  2732. /*
  2733. * Case 9:
  2734. * bbno bend
  2735. * +BBBBBBBBBBBBBBBBB+
  2736. * +-----------------------------------+
  2737. * fbno fend
  2738. *
  2739. * Can be trimmed to:
  2740. * +-------+ OR +-------+
  2741. * fbno fend fbno fend
  2742. *
  2743. * Backward allocation leads to significant
  2744. * fragmentation of directories, which degrades
  2745. * directory performance, therefore we always want to
  2746. * choose the option that produces forward allocation
  2747. * patterns.
  2748. * Preferring the lower bno extent will make the next
  2749. * request use "fend" as the start of the next
  2750. * allocation; if the segment is no longer busy at
  2751. * that point, we'll get a contiguous allocation, but
  2752. * even if it is still busy, we will get a forward
  2753. * allocation.
  2754. * We try to avoid choosing the segment at "bend",
  2755. * because that can lead to the next allocation
  2756. * taking the segment at "fbno", which would be a
  2757. * backward allocation. We only use the segment at
  2758. * "fbno" if it is much larger than the current
  2759. * requested size, because in that case there's a
  2760. * good chance subsequent allocations will be
  2761. * contiguous.
  2762. */
  2763. if (bbno - fbno >= args->maxlen) {
  2764. /* left candidate fits perfect */
  2765. fend = bbno;
  2766. } else if (fend - bend >= args->maxlen * 4) {
  2767. /* right candidate has enough free space */
  2768. fbno = bend;
  2769. } else if (bbno - fbno >= args->minlen) {
  2770. /* left candidate fits minimum requirement */
  2771. fend = bbno;
  2772. } else {
  2773. goto fail;
  2774. }
  2775. }
  2776. flen = fend - fbno;
  2777. }
  2778. spin_unlock(&args->pag->pagb_lock);
  2779. if (fbno != bno || flen != len) {
  2780. trace_xfs_alloc_busy_trim(args->mp, args->agno, bno, len,
  2781. fbno, flen);
  2782. }
  2783. *rbno = fbno;
  2784. *rlen = flen;
  2785. return;
  2786. fail:
  2787. /*
  2788. * Return a zero extent length as failure indications. All callers
  2789. * re-check if the trimmed extent satisfies the minlen requirement.
  2790. */
  2791. spin_unlock(&args->pag->pagb_lock);
  2792. trace_xfs_alloc_busy_trim(args->mp, args->agno, bno, len, fbno, 0);
  2793. *rbno = fbno;
  2794. *rlen = 0;
  2795. }
  2796. static void
  2797. xfs_alloc_busy_clear_one(
  2798. struct xfs_mount *mp,
  2799. struct xfs_perag *pag,
  2800. struct xfs_busy_extent *busyp)
  2801. {
  2802. if (busyp->length) {
  2803. trace_xfs_alloc_busy_clear(mp, busyp->agno, busyp->bno,
  2804. busyp->length);
  2805. rb_erase(&busyp->rb_node, &pag->pagb_tree);
  2806. }
  2807. list_del_init(&busyp->list);
  2808. kmem_free(busyp);
  2809. }
  2810. /*
  2811. * Remove all extents on the passed in list from the busy extents tree.
  2812. * If do_discard is set skip extents that need to be discarded, and mark
  2813. * these as undergoing a discard operation instead.
  2814. */
  2815. void
  2816. xfs_alloc_busy_clear(
  2817. struct xfs_mount *mp,
  2818. struct list_head *list,
  2819. bool do_discard)
  2820. {
  2821. struct xfs_busy_extent *busyp, *n;
  2822. struct xfs_perag *pag = NULL;
  2823. xfs_agnumber_t agno = NULLAGNUMBER;
  2824. list_for_each_entry_safe(busyp, n, list, list) {
  2825. if (busyp->agno != agno) {
  2826. if (pag) {
  2827. spin_unlock(&pag->pagb_lock);
  2828. xfs_perag_put(pag);
  2829. }
  2830. pag = xfs_perag_get(mp, busyp->agno);
  2831. spin_lock(&pag->pagb_lock);
  2832. agno = busyp->agno;
  2833. }
  2834. if (do_discard && busyp->length &&
  2835. !(busyp->flags & XFS_ALLOC_BUSY_SKIP_DISCARD))
  2836. busyp->flags = XFS_ALLOC_BUSY_DISCARDED;
  2837. else
  2838. xfs_alloc_busy_clear_one(mp, pag, busyp);
  2839. }
  2840. if (pag) {
  2841. spin_unlock(&pag->pagb_lock);
  2842. xfs_perag_put(pag);
  2843. }
  2844. }
  2845. /*
  2846. * Callback for list_sort to sort busy extents by the AG they reside in.
  2847. */
  2848. int
  2849. xfs_busy_extent_ag_cmp(
  2850. void *priv,
  2851. struct list_head *a,
  2852. struct list_head *b)
  2853. {
  2854. return container_of(a, struct xfs_busy_extent, list)->agno -
  2855. container_of(b, struct xfs_busy_extent, list)->agno;
  2856. }