free-space-cache.c 107 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994199519961997199819992000200120022003200420052006200720082009201020112012201320142015201620172018201920202021202220232024202520262027202820292030203120322033203420352036203720382039204020412042204320442045204620472048204920502051205220532054205520562057205820592060206120622063206420652066206720682069207020712072207320742075207620772078207920802081208220832084208520862087208820892090209120922093209420952096209720982099210021012102210321042105210621072108210921102111211221132114211521162117211821192120212121222123212421252126212721282129213021312132213321342135213621372138213921402141214221432144214521462147214821492150215121522153215421552156215721582159216021612162216321642165216621672168216921702171217221732174217521762177217821792180218121822183218421852186218721882189219021912192219321942195219621972198219922002201220222032204220522062207220822092210221122122213221422152216221722182219222022212222222322242225222622272228222922302231223222332234223522362237223822392240224122422243224422452246224722482249225022512252225322542255225622572258225922602261226222632264226522662267226822692270227122722273227422752276227722782279228022812282228322842285228622872288228922902291229222932294229522962297229822992300230123022303230423052306230723082309231023112312231323142315231623172318231923202321232223232324232523262327232823292330233123322333233423352336233723382339234023412342234323442345234623472348234923502351235223532354235523562357235823592360236123622363236423652366236723682369237023712372237323742375237623772378237923802381238223832384238523862387238823892390239123922393239423952396239723982399240024012402240324042405240624072408240924102411241224132414241524162417241824192420242124222423242424252426242724282429243024312432243324342435243624372438243924402441244224432444244524462447244824492450245124522453245424552456245724582459246024612462246324642465246624672468246924702471247224732474247524762477247824792480248124822483248424852486248724882489249024912492249324942495249624972498249925002501250225032504250525062507250825092510251125122513251425152516251725182519252025212522252325242525252625272528252925302531253225332534253525362537253825392540254125422543254425452546254725482549255025512552255325542555255625572558255925602561256225632564256525662567256825692570257125722573257425752576257725782579258025812582258325842585258625872588258925902591259225932594259525962597259825992600260126022603260426052606260726082609261026112612261326142615261626172618261926202621262226232624262526262627262826292630263126322633263426352636263726382639264026412642264326442645264626472648264926502651265226532654265526562657265826592660266126622663266426652666266726682669267026712672267326742675267626772678267926802681268226832684268526862687268826892690269126922693269426952696269726982699270027012702270327042705270627072708270927102711271227132714271527162717271827192720272127222723272427252726272727282729273027312732273327342735273627372738273927402741274227432744274527462747274827492750275127522753275427552756275727582759276027612762276327642765276627672768276927702771277227732774277527762777277827792780278127822783278427852786278727882789279027912792279327942795279627972798279928002801280228032804280528062807280828092810281128122813281428152816281728182819282028212822282328242825282628272828282928302831283228332834283528362837283828392840284128422843284428452846284728482849285028512852285328542855285628572858285928602861286228632864286528662867286828692870287128722873287428752876287728782879288028812882288328842885288628872888288928902891289228932894289528962897289828992900290129022903290429052906290729082909291029112912291329142915291629172918291929202921292229232924292529262927292829292930293129322933293429352936293729382939294029412942294329442945294629472948294929502951295229532954295529562957295829592960296129622963296429652966296729682969297029712972297329742975297629772978297929802981298229832984298529862987298829892990299129922993299429952996299729982999300030013002300330043005300630073008300930103011301230133014301530163017301830193020302130223023302430253026302730283029303030313032303330343035303630373038303930403041304230433044304530463047304830493050305130523053305430553056305730583059306030613062306330643065306630673068306930703071307230733074307530763077307830793080308130823083308430853086308730883089309030913092309330943095309630973098309931003101310231033104310531063107310831093110311131123113311431153116311731183119312031213122312331243125312631273128312931303131313231333134313531363137313831393140314131423143314431453146314731483149315031513152315331543155315631573158315931603161316231633164316531663167316831693170317131723173317431753176317731783179318031813182318331843185318631873188318931903191319231933194319531963197319831993200320132023203320432053206320732083209321032113212321332143215321632173218321932203221322232233224322532263227322832293230323132323233323432353236323732383239324032413242324332443245324632473248324932503251325232533254325532563257325832593260326132623263326432653266326732683269327032713272327332743275327632773278327932803281328232833284328532863287328832893290329132923293329432953296329732983299330033013302330333043305330633073308330933103311331233133314331533163317331833193320332133223323332433253326332733283329333033313332333333343335333633373338333933403341334233433344334533463347334833493350335133523353335433553356335733583359336033613362336333643365336633673368336933703371337233733374337533763377337833793380338133823383338433853386338733883389339033913392339333943395339633973398339934003401340234033404340534063407340834093410341134123413341434153416341734183419342034213422342334243425342634273428342934303431343234333434343534363437343834393440344134423443344434453446344734483449345034513452345334543455345634573458345934603461346234633464346534663467346834693470347134723473347434753476347734783479348034813482348334843485348634873488348934903491349234933494349534963497349834993500350135023503350435053506350735083509351035113512351335143515351635173518351935203521352235233524352535263527352835293530353135323533353435353536353735383539354035413542354335443545354635473548354935503551355235533554355535563557355835593560356135623563356435653566356735683569357035713572357335743575357635773578357935803581358235833584358535863587358835893590359135923593359435953596359735983599360036013602360336043605360636073608360936103611361236133614361536163617361836193620362136223623362436253626362736283629363036313632363336343635363636373638363936403641364236433644364536463647364836493650365136523653365436553656365736583659366036613662366336643665366636673668366936703671367236733674367536763677367836793680368136823683368436853686368736883689369036913692369336943695369636973698369937003701370237033704370537063707370837093710371137123713371437153716371737183719372037213722372337243725372637273728372937303731373237333734373537363737373837393740374137423743374437453746374737483749375037513752375337543755375637573758375937603761376237633764376537663767376837693770377137723773377437753776377737783779378037813782378337843785378637873788378937903791379237933794379537963797379837993800380138023803380438053806380738083809381038113812381338143815381638173818381938203821382238233824382538263827382838293830383138323833383438353836383738383839384038413842384338443845384638473848384938503851385238533854385538563857385838593860386138623863386438653866386738683869387038713872387338743875387638773878387938803881388238833884388538863887388838893890389138923893389438953896389738983899390039013902390339043905390639073908390939103911391239133914391539163917391839193920392139223923392439253926392739283929393039313932393339343935393639373938393939403941394239433944394539463947394839493950395139523953395439553956395739583959396039613962396339643965396639673968396939703971397239733974397539763977397839793980398139823983398439853986398739883989399039913992399339943995399639973998399940004001400240034004400540064007400840094010401140124013401440154016401740184019402040214022402340244025402640274028402940304031403240334034403540364037403840394040404140424043404440454046404740484049405040514052405340544055405640574058405940604061406240634064406540664067406840694070407140724073407440754076407740784079408040814082408340844085408640874088408940904091409240934094409540964097409840994100410141024103410441054106410741084109411041114112411341144115411641174118411941204121412241234124412541264127412841294130413141324133413441354136413741384139414041414142414341444145414641474148414941504151415241534154415541564157
  1. // SPDX-License-Identifier: GPL-2.0
  2. /*
  3. * Copyright (C) 2008 Red Hat. All rights reserved.
  4. */
  5. #include <linux/pagemap.h>
  6. #include <linux/sched.h>
  7. #include <linux/sched/signal.h>
  8. #include <linux/slab.h>
  9. #include <linux/math64.h>
  10. #include <linux/ratelimit.h>
  11. #include <linux/error-injection.h>
  12. #include <linux/sched/mm.h>
  13. #include "ctree.h"
  14. #include "free-space-cache.h"
  15. #include "transaction.h"
  16. #include "disk-io.h"
  17. #include "extent_io.h"
  18. #include "inode-map.h"
  19. #include "volumes.h"
  20. #include "space-info.h"
  21. #include "delalloc-space.h"
  22. #include "block-group.h"
  23. #include "discard.h"
  24. #define BITS_PER_BITMAP (PAGE_SIZE * 8UL)
  25. #define MAX_CACHE_BYTES_PER_GIG SZ_64K
  26. #define FORCE_EXTENT_THRESHOLD SZ_1M
  27. struct btrfs_trim_range {
  28. u64 start;
  29. u64 bytes;
  30. struct list_head list;
  31. };
  32. static int count_bitmap_extents(struct btrfs_free_space_ctl *ctl,
  33. struct btrfs_free_space *bitmap_info);
  34. static int link_free_space(struct btrfs_free_space_ctl *ctl,
  35. struct btrfs_free_space *info);
  36. static void unlink_free_space(struct btrfs_free_space_ctl *ctl,
  37. struct btrfs_free_space *info);
  38. static int btrfs_wait_cache_io_root(struct btrfs_root *root,
  39. struct btrfs_trans_handle *trans,
  40. struct btrfs_io_ctl *io_ctl,
  41. struct btrfs_path *path);
  42. static struct inode *__lookup_free_space_inode(struct btrfs_root *root,
  43. struct btrfs_path *path,
  44. u64 offset)
  45. {
  46. struct btrfs_fs_info *fs_info = root->fs_info;
  47. struct btrfs_key key;
  48. struct btrfs_key location;
  49. struct btrfs_disk_key disk_key;
  50. struct btrfs_free_space_header *header;
  51. struct extent_buffer *leaf;
  52. struct inode *inode = NULL;
  53. unsigned nofs_flag;
  54. int ret;
  55. key.objectid = BTRFS_FREE_SPACE_OBJECTID;
  56. key.offset = offset;
  57. key.type = 0;
  58. ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
  59. if (ret < 0)
  60. return ERR_PTR(ret);
  61. if (ret > 0) {
  62. btrfs_release_path(path);
  63. return ERR_PTR(-ENOENT);
  64. }
  65. leaf = path->nodes[0];
  66. header = btrfs_item_ptr(leaf, path->slots[0],
  67. struct btrfs_free_space_header);
  68. btrfs_free_space_key(leaf, header, &disk_key);
  69. btrfs_disk_key_to_cpu(&location, &disk_key);
  70. btrfs_release_path(path);
  71. /*
  72. * We are often under a trans handle at this point, so we need to make
  73. * sure NOFS is set to keep us from deadlocking.
  74. */
  75. nofs_flag = memalloc_nofs_save();
  76. inode = btrfs_iget_path(fs_info->sb, location.objectid, root, path);
  77. btrfs_release_path(path);
  78. memalloc_nofs_restore(nofs_flag);
  79. if (IS_ERR(inode))
  80. return inode;
  81. mapping_set_gfp_mask(inode->i_mapping,
  82. mapping_gfp_constraint(inode->i_mapping,
  83. ~(__GFP_FS | __GFP_HIGHMEM)));
  84. return inode;
  85. }
  86. struct inode *lookup_free_space_inode(struct btrfs_block_group *block_group,
  87. struct btrfs_path *path)
  88. {
  89. struct btrfs_fs_info *fs_info = block_group->fs_info;
  90. struct inode *inode = NULL;
  91. u32 flags = BTRFS_INODE_NODATASUM | BTRFS_INODE_NODATACOW;
  92. spin_lock(&block_group->lock);
  93. if (block_group->inode)
  94. inode = igrab(block_group->inode);
  95. spin_unlock(&block_group->lock);
  96. if (inode)
  97. return inode;
  98. inode = __lookup_free_space_inode(fs_info->tree_root, path,
  99. block_group->start);
  100. if (IS_ERR(inode))
  101. return inode;
  102. spin_lock(&block_group->lock);
  103. if (!((BTRFS_I(inode)->flags & flags) == flags)) {
  104. btrfs_info(fs_info, "Old style space inode found, converting.");
  105. BTRFS_I(inode)->flags |= BTRFS_INODE_NODATASUM |
  106. BTRFS_INODE_NODATACOW;
  107. block_group->disk_cache_state = BTRFS_DC_CLEAR;
  108. }
  109. if (!block_group->iref) {
  110. block_group->inode = igrab(inode);
  111. block_group->iref = 1;
  112. }
  113. spin_unlock(&block_group->lock);
  114. return inode;
  115. }
  116. static int __create_free_space_inode(struct btrfs_root *root,
  117. struct btrfs_trans_handle *trans,
  118. struct btrfs_path *path,
  119. u64 ino, u64 offset)
  120. {
  121. struct btrfs_key key;
  122. struct btrfs_disk_key disk_key;
  123. struct btrfs_free_space_header *header;
  124. struct btrfs_inode_item *inode_item;
  125. struct extent_buffer *leaf;
  126. u64 flags = BTRFS_INODE_NOCOMPRESS | BTRFS_INODE_PREALLOC;
  127. int ret;
  128. ret = btrfs_insert_empty_inode(trans, root, path, ino);
  129. if (ret)
  130. return ret;
  131. /* We inline crc's for the free disk space cache */
  132. if (ino != BTRFS_FREE_INO_OBJECTID)
  133. flags |= BTRFS_INODE_NODATASUM | BTRFS_INODE_NODATACOW;
  134. leaf = path->nodes[0];
  135. inode_item = btrfs_item_ptr(leaf, path->slots[0],
  136. struct btrfs_inode_item);
  137. btrfs_item_key(leaf, &disk_key, path->slots[0]);
  138. memzero_extent_buffer(leaf, (unsigned long)inode_item,
  139. sizeof(*inode_item));
  140. btrfs_set_inode_generation(leaf, inode_item, trans->transid);
  141. btrfs_set_inode_size(leaf, inode_item, 0);
  142. btrfs_set_inode_nbytes(leaf, inode_item, 0);
  143. btrfs_set_inode_uid(leaf, inode_item, 0);
  144. btrfs_set_inode_gid(leaf, inode_item, 0);
  145. btrfs_set_inode_mode(leaf, inode_item, S_IFREG | 0600);
  146. btrfs_set_inode_flags(leaf, inode_item, flags);
  147. btrfs_set_inode_nlink(leaf, inode_item, 1);
  148. btrfs_set_inode_transid(leaf, inode_item, trans->transid);
  149. btrfs_set_inode_block_group(leaf, inode_item, offset);
  150. btrfs_mark_buffer_dirty(leaf);
  151. btrfs_release_path(path);
  152. key.objectid = BTRFS_FREE_SPACE_OBJECTID;
  153. key.offset = offset;
  154. key.type = 0;
  155. ret = btrfs_insert_empty_item(trans, root, path, &key,
  156. sizeof(struct btrfs_free_space_header));
  157. if (ret < 0) {
  158. btrfs_release_path(path);
  159. return ret;
  160. }
  161. leaf = path->nodes[0];
  162. header = btrfs_item_ptr(leaf, path->slots[0],
  163. struct btrfs_free_space_header);
  164. memzero_extent_buffer(leaf, (unsigned long)header, sizeof(*header));
  165. btrfs_set_free_space_key(leaf, header, &disk_key);
  166. btrfs_mark_buffer_dirty(leaf);
  167. btrfs_release_path(path);
  168. return 0;
  169. }
  170. int create_free_space_inode(struct btrfs_trans_handle *trans,
  171. struct btrfs_block_group *block_group,
  172. struct btrfs_path *path)
  173. {
  174. int ret;
  175. u64 ino;
  176. ret = btrfs_find_free_objectid(trans->fs_info->tree_root, &ino);
  177. if (ret < 0)
  178. return ret;
  179. return __create_free_space_inode(trans->fs_info->tree_root, trans, path,
  180. ino, block_group->start);
  181. }
  182. int btrfs_check_trunc_cache_free_space(struct btrfs_fs_info *fs_info,
  183. struct btrfs_block_rsv *rsv)
  184. {
  185. u64 needed_bytes;
  186. int ret;
  187. /* 1 for slack space, 1 for updating the inode */
  188. needed_bytes = btrfs_calc_insert_metadata_size(fs_info, 1) +
  189. btrfs_calc_metadata_size(fs_info, 1);
  190. spin_lock(&rsv->lock);
  191. if (rsv->reserved < needed_bytes)
  192. ret = -ENOSPC;
  193. else
  194. ret = 0;
  195. spin_unlock(&rsv->lock);
  196. return ret;
  197. }
  198. int btrfs_truncate_free_space_cache(struct btrfs_trans_handle *trans,
  199. struct btrfs_block_group *block_group,
  200. struct inode *inode)
  201. {
  202. struct btrfs_root *root = BTRFS_I(inode)->root;
  203. int ret = 0;
  204. bool locked = false;
  205. if (block_group) {
  206. struct btrfs_path *path = btrfs_alloc_path();
  207. if (!path) {
  208. ret = -ENOMEM;
  209. goto fail;
  210. }
  211. locked = true;
  212. mutex_lock(&trans->transaction->cache_write_mutex);
  213. if (!list_empty(&block_group->io_list)) {
  214. list_del_init(&block_group->io_list);
  215. btrfs_wait_cache_io(trans, block_group, path);
  216. btrfs_put_block_group(block_group);
  217. }
  218. /*
  219. * now that we've truncated the cache away, its no longer
  220. * setup or written
  221. */
  222. spin_lock(&block_group->lock);
  223. block_group->disk_cache_state = BTRFS_DC_CLEAR;
  224. spin_unlock(&block_group->lock);
  225. btrfs_free_path(path);
  226. }
  227. btrfs_i_size_write(BTRFS_I(inode), 0);
  228. truncate_pagecache(inode, 0);
  229. /*
  230. * We skip the throttling logic for free space cache inodes, so we don't
  231. * need to check for -EAGAIN.
  232. */
  233. ret = btrfs_truncate_inode_items(trans, root, inode,
  234. 0, BTRFS_EXTENT_DATA_KEY);
  235. if (ret)
  236. goto fail;
  237. ret = btrfs_update_inode(trans, root, inode);
  238. fail:
  239. if (locked)
  240. mutex_unlock(&trans->transaction->cache_write_mutex);
  241. if (ret)
  242. btrfs_abort_transaction(trans, ret);
  243. return ret;
  244. }
  245. static void readahead_cache(struct inode *inode)
  246. {
  247. struct file_ra_state *ra;
  248. unsigned long last_index;
  249. ra = kzalloc(sizeof(*ra), GFP_NOFS);
  250. if (!ra)
  251. return;
  252. file_ra_state_init(ra, inode->i_mapping);
  253. last_index = (i_size_read(inode) - 1) >> PAGE_SHIFT;
  254. page_cache_sync_readahead(inode->i_mapping, ra, NULL, 0, last_index);
  255. kfree(ra);
  256. }
  257. static int io_ctl_init(struct btrfs_io_ctl *io_ctl, struct inode *inode,
  258. int write)
  259. {
  260. int num_pages;
  261. int check_crcs = 0;
  262. num_pages = DIV_ROUND_UP(i_size_read(inode), PAGE_SIZE);
  263. if (btrfs_ino(BTRFS_I(inode)) != BTRFS_FREE_INO_OBJECTID)
  264. check_crcs = 1;
  265. /* Make sure we can fit our crcs and generation into the first page */
  266. if (write && check_crcs &&
  267. (num_pages * sizeof(u32) + sizeof(u64)) > PAGE_SIZE)
  268. return -ENOSPC;
  269. memset(io_ctl, 0, sizeof(struct btrfs_io_ctl));
  270. io_ctl->pages = kcalloc(num_pages, sizeof(struct page *), GFP_NOFS);
  271. if (!io_ctl->pages)
  272. return -ENOMEM;
  273. io_ctl->num_pages = num_pages;
  274. io_ctl->fs_info = btrfs_sb(inode->i_sb);
  275. io_ctl->check_crcs = check_crcs;
  276. io_ctl->inode = inode;
  277. return 0;
  278. }
  279. ALLOW_ERROR_INJECTION(io_ctl_init, ERRNO);
  280. static void io_ctl_free(struct btrfs_io_ctl *io_ctl)
  281. {
  282. kfree(io_ctl->pages);
  283. io_ctl->pages = NULL;
  284. }
  285. static void io_ctl_unmap_page(struct btrfs_io_ctl *io_ctl)
  286. {
  287. if (io_ctl->cur) {
  288. io_ctl->cur = NULL;
  289. io_ctl->orig = NULL;
  290. }
  291. }
  292. static void io_ctl_map_page(struct btrfs_io_ctl *io_ctl, int clear)
  293. {
  294. ASSERT(io_ctl->index < io_ctl->num_pages);
  295. io_ctl->page = io_ctl->pages[io_ctl->index++];
  296. io_ctl->cur = page_address(io_ctl->page);
  297. io_ctl->orig = io_ctl->cur;
  298. io_ctl->size = PAGE_SIZE;
  299. if (clear)
  300. clear_page(io_ctl->cur);
  301. }
  302. static void io_ctl_drop_pages(struct btrfs_io_ctl *io_ctl)
  303. {
  304. int i;
  305. io_ctl_unmap_page(io_ctl);
  306. for (i = 0; i < io_ctl->num_pages; i++) {
  307. if (io_ctl->pages[i]) {
  308. ClearPageChecked(io_ctl->pages[i]);
  309. unlock_page(io_ctl->pages[i]);
  310. put_page(io_ctl->pages[i]);
  311. }
  312. }
  313. }
  314. static int io_ctl_prepare_pages(struct btrfs_io_ctl *io_ctl, bool uptodate)
  315. {
  316. struct page *page;
  317. struct inode *inode = io_ctl->inode;
  318. gfp_t mask = btrfs_alloc_write_mask(inode->i_mapping);
  319. int i;
  320. for (i = 0; i < io_ctl->num_pages; i++) {
  321. page = find_or_create_page(inode->i_mapping, i, mask);
  322. if (!page) {
  323. io_ctl_drop_pages(io_ctl);
  324. return -ENOMEM;
  325. }
  326. io_ctl->pages[i] = page;
  327. if (uptodate && !PageUptodate(page)) {
  328. btrfs_readpage(NULL, page);
  329. lock_page(page);
  330. if (page->mapping != inode->i_mapping) {
  331. btrfs_err(BTRFS_I(inode)->root->fs_info,
  332. "free space cache page truncated");
  333. io_ctl_drop_pages(io_ctl);
  334. return -EIO;
  335. }
  336. if (!PageUptodate(page)) {
  337. btrfs_err(BTRFS_I(inode)->root->fs_info,
  338. "error reading free space cache");
  339. io_ctl_drop_pages(io_ctl);
  340. return -EIO;
  341. }
  342. }
  343. }
  344. for (i = 0; i < io_ctl->num_pages; i++) {
  345. clear_page_dirty_for_io(io_ctl->pages[i]);
  346. set_page_extent_mapped(io_ctl->pages[i]);
  347. }
  348. return 0;
  349. }
  350. static void io_ctl_set_generation(struct btrfs_io_ctl *io_ctl, u64 generation)
  351. {
  352. io_ctl_map_page(io_ctl, 1);
  353. /*
  354. * Skip the csum areas. If we don't check crcs then we just have a
  355. * 64bit chunk at the front of the first page.
  356. */
  357. if (io_ctl->check_crcs) {
  358. io_ctl->cur += (sizeof(u32) * io_ctl->num_pages);
  359. io_ctl->size -= sizeof(u64) + (sizeof(u32) * io_ctl->num_pages);
  360. } else {
  361. io_ctl->cur += sizeof(u64);
  362. io_ctl->size -= sizeof(u64) * 2;
  363. }
  364. put_unaligned_le64(generation, io_ctl->cur);
  365. io_ctl->cur += sizeof(u64);
  366. }
  367. static int io_ctl_check_generation(struct btrfs_io_ctl *io_ctl, u64 generation)
  368. {
  369. u64 cache_gen;
  370. /*
  371. * Skip the crc area. If we don't check crcs then we just have a 64bit
  372. * chunk at the front of the first page.
  373. */
  374. if (io_ctl->check_crcs) {
  375. io_ctl->cur += sizeof(u32) * io_ctl->num_pages;
  376. io_ctl->size -= sizeof(u64) +
  377. (sizeof(u32) * io_ctl->num_pages);
  378. } else {
  379. io_ctl->cur += sizeof(u64);
  380. io_ctl->size -= sizeof(u64) * 2;
  381. }
  382. cache_gen = get_unaligned_le64(io_ctl->cur);
  383. if (cache_gen != generation) {
  384. btrfs_err_rl(io_ctl->fs_info,
  385. "space cache generation (%llu) does not match inode (%llu)",
  386. cache_gen, generation);
  387. io_ctl_unmap_page(io_ctl);
  388. return -EIO;
  389. }
  390. io_ctl->cur += sizeof(u64);
  391. return 0;
  392. }
  393. static void io_ctl_set_crc(struct btrfs_io_ctl *io_ctl, int index)
  394. {
  395. u32 *tmp;
  396. u32 crc = ~(u32)0;
  397. unsigned offset = 0;
  398. if (!io_ctl->check_crcs) {
  399. io_ctl_unmap_page(io_ctl);
  400. return;
  401. }
  402. if (index == 0)
  403. offset = sizeof(u32) * io_ctl->num_pages;
  404. crc = btrfs_crc32c(crc, io_ctl->orig + offset, PAGE_SIZE - offset);
  405. btrfs_crc32c_final(crc, (u8 *)&crc);
  406. io_ctl_unmap_page(io_ctl);
  407. tmp = page_address(io_ctl->pages[0]);
  408. tmp += index;
  409. *tmp = crc;
  410. }
  411. static int io_ctl_check_crc(struct btrfs_io_ctl *io_ctl, int index)
  412. {
  413. u32 *tmp, val;
  414. u32 crc = ~(u32)0;
  415. unsigned offset = 0;
  416. if (!io_ctl->check_crcs) {
  417. io_ctl_map_page(io_ctl, 0);
  418. return 0;
  419. }
  420. if (index == 0)
  421. offset = sizeof(u32) * io_ctl->num_pages;
  422. tmp = page_address(io_ctl->pages[0]);
  423. tmp += index;
  424. val = *tmp;
  425. io_ctl_map_page(io_ctl, 0);
  426. crc = btrfs_crc32c(crc, io_ctl->orig + offset, PAGE_SIZE - offset);
  427. btrfs_crc32c_final(crc, (u8 *)&crc);
  428. if (val != crc) {
  429. btrfs_err_rl(io_ctl->fs_info,
  430. "csum mismatch on free space cache");
  431. io_ctl_unmap_page(io_ctl);
  432. return -EIO;
  433. }
  434. return 0;
  435. }
  436. static int io_ctl_add_entry(struct btrfs_io_ctl *io_ctl, u64 offset, u64 bytes,
  437. void *bitmap)
  438. {
  439. struct btrfs_free_space_entry *entry;
  440. if (!io_ctl->cur)
  441. return -ENOSPC;
  442. entry = io_ctl->cur;
  443. put_unaligned_le64(offset, &entry->offset);
  444. put_unaligned_le64(bytes, &entry->bytes);
  445. entry->type = (bitmap) ? BTRFS_FREE_SPACE_BITMAP :
  446. BTRFS_FREE_SPACE_EXTENT;
  447. io_ctl->cur += sizeof(struct btrfs_free_space_entry);
  448. io_ctl->size -= sizeof(struct btrfs_free_space_entry);
  449. if (io_ctl->size >= sizeof(struct btrfs_free_space_entry))
  450. return 0;
  451. io_ctl_set_crc(io_ctl, io_ctl->index - 1);
  452. /* No more pages to map */
  453. if (io_ctl->index >= io_ctl->num_pages)
  454. return 0;
  455. /* map the next page */
  456. io_ctl_map_page(io_ctl, 1);
  457. return 0;
  458. }
  459. static int io_ctl_add_bitmap(struct btrfs_io_ctl *io_ctl, void *bitmap)
  460. {
  461. if (!io_ctl->cur)
  462. return -ENOSPC;
  463. /*
  464. * If we aren't at the start of the current page, unmap this one and
  465. * map the next one if there is any left.
  466. */
  467. if (io_ctl->cur != io_ctl->orig) {
  468. io_ctl_set_crc(io_ctl, io_ctl->index - 1);
  469. if (io_ctl->index >= io_ctl->num_pages)
  470. return -ENOSPC;
  471. io_ctl_map_page(io_ctl, 0);
  472. }
  473. copy_page(io_ctl->cur, bitmap);
  474. io_ctl_set_crc(io_ctl, io_ctl->index - 1);
  475. if (io_ctl->index < io_ctl->num_pages)
  476. io_ctl_map_page(io_ctl, 0);
  477. return 0;
  478. }
  479. static void io_ctl_zero_remaining_pages(struct btrfs_io_ctl *io_ctl)
  480. {
  481. /*
  482. * If we're not on the boundary we know we've modified the page and we
  483. * need to crc the page.
  484. */
  485. if (io_ctl->cur != io_ctl->orig)
  486. io_ctl_set_crc(io_ctl, io_ctl->index - 1);
  487. else
  488. io_ctl_unmap_page(io_ctl);
  489. while (io_ctl->index < io_ctl->num_pages) {
  490. io_ctl_map_page(io_ctl, 1);
  491. io_ctl_set_crc(io_ctl, io_ctl->index - 1);
  492. }
  493. }
  494. static int io_ctl_read_entry(struct btrfs_io_ctl *io_ctl,
  495. struct btrfs_free_space *entry, u8 *type)
  496. {
  497. struct btrfs_free_space_entry *e;
  498. int ret;
  499. if (!io_ctl->cur) {
  500. ret = io_ctl_check_crc(io_ctl, io_ctl->index);
  501. if (ret)
  502. return ret;
  503. }
  504. e = io_ctl->cur;
  505. entry->offset = get_unaligned_le64(&e->offset);
  506. entry->bytes = get_unaligned_le64(&e->bytes);
  507. *type = e->type;
  508. io_ctl->cur += sizeof(struct btrfs_free_space_entry);
  509. io_ctl->size -= sizeof(struct btrfs_free_space_entry);
  510. if (io_ctl->size >= sizeof(struct btrfs_free_space_entry))
  511. return 0;
  512. io_ctl_unmap_page(io_ctl);
  513. return 0;
  514. }
  515. static int io_ctl_read_bitmap(struct btrfs_io_ctl *io_ctl,
  516. struct btrfs_free_space *entry)
  517. {
  518. int ret;
  519. ret = io_ctl_check_crc(io_ctl, io_ctl->index);
  520. if (ret)
  521. return ret;
  522. copy_page(entry->bitmap, io_ctl->cur);
  523. io_ctl_unmap_page(io_ctl);
  524. return 0;
  525. }
  526. /*
  527. * Since we attach pinned extents after the fact we can have contiguous sections
  528. * of free space that are split up in entries. This poses a problem with the
  529. * tree logging stuff since it could have allocated across what appears to be 2
  530. * entries since we would have merged the entries when adding the pinned extents
  531. * back to the free space cache. So run through the space cache that we just
  532. * loaded and merge contiguous entries. This will make the log replay stuff not
  533. * blow up and it will make for nicer allocator behavior.
  534. */
  535. static void merge_space_tree(struct btrfs_free_space_ctl *ctl)
  536. {
  537. struct btrfs_free_space *e, *prev = NULL;
  538. struct rb_node *n;
  539. again:
  540. spin_lock(&ctl->tree_lock);
  541. for (n = rb_first(&ctl->free_space_offset); n; n = rb_next(n)) {
  542. e = rb_entry(n, struct btrfs_free_space, offset_index);
  543. if (!prev)
  544. goto next;
  545. if (e->bitmap || prev->bitmap)
  546. goto next;
  547. if (prev->offset + prev->bytes == e->offset) {
  548. unlink_free_space(ctl, prev);
  549. unlink_free_space(ctl, e);
  550. prev->bytes += e->bytes;
  551. kmem_cache_free(btrfs_free_space_cachep, e);
  552. link_free_space(ctl, prev);
  553. prev = NULL;
  554. spin_unlock(&ctl->tree_lock);
  555. goto again;
  556. }
  557. next:
  558. prev = e;
  559. }
  560. spin_unlock(&ctl->tree_lock);
  561. }
  562. static int __load_free_space_cache(struct btrfs_root *root, struct inode *inode,
  563. struct btrfs_free_space_ctl *ctl,
  564. struct btrfs_path *path, u64 offset)
  565. {
  566. struct btrfs_fs_info *fs_info = root->fs_info;
  567. struct btrfs_free_space_header *header;
  568. struct extent_buffer *leaf;
  569. struct btrfs_io_ctl io_ctl;
  570. struct btrfs_key key;
  571. struct btrfs_free_space *e, *n;
  572. LIST_HEAD(bitmaps);
  573. u64 num_entries;
  574. u64 num_bitmaps;
  575. u64 generation;
  576. u8 type;
  577. int ret = 0;
  578. /* Nothing in the space cache, goodbye */
  579. if (!i_size_read(inode))
  580. return 0;
  581. key.objectid = BTRFS_FREE_SPACE_OBJECTID;
  582. key.offset = offset;
  583. key.type = 0;
  584. ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
  585. if (ret < 0)
  586. return 0;
  587. else if (ret > 0) {
  588. btrfs_release_path(path);
  589. return 0;
  590. }
  591. ret = -1;
  592. leaf = path->nodes[0];
  593. header = btrfs_item_ptr(leaf, path->slots[0],
  594. struct btrfs_free_space_header);
  595. num_entries = btrfs_free_space_entries(leaf, header);
  596. num_bitmaps = btrfs_free_space_bitmaps(leaf, header);
  597. generation = btrfs_free_space_generation(leaf, header);
  598. btrfs_release_path(path);
  599. if (!BTRFS_I(inode)->generation) {
  600. btrfs_info(fs_info,
  601. "the free space cache file (%llu) is invalid, skip it",
  602. offset);
  603. return 0;
  604. }
  605. if (BTRFS_I(inode)->generation != generation) {
  606. btrfs_err(fs_info,
  607. "free space inode generation (%llu) did not match free space cache generation (%llu)",
  608. BTRFS_I(inode)->generation, generation);
  609. return 0;
  610. }
  611. if (!num_entries)
  612. return 0;
  613. ret = io_ctl_init(&io_ctl, inode, 0);
  614. if (ret)
  615. return ret;
  616. readahead_cache(inode);
  617. ret = io_ctl_prepare_pages(&io_ctl, true);
  618. if (ret)
  619. goto out;
  620. ret = io_ctl_check_crc(&io_ctl, 0);
  621. if (ret)
  622. goto free_cache;
  623. ret = io_ctl_check_generation(&io_ctl, generation);
  624. if (ret)
  625. goto free_cache;
  626. while (num_entries) {
  627. e = kmem_cache_zalloc(btrfs_free_space_cachep,
  628. GFP_NOFS);
  629. if (!e) {
  630. ret = -ENOMEM;
  631. goto free_cache;
  632. }
  633. ret = io_ctl_read_entry(&io_ctl, e, &type);
  634. if (ret) {
  635. kmem_cache_free(btrfs_free_space_cachep, e);
  636. goto free_cache;
  637. }
  638. /*
  639. * Sync discard ensures that the free space cache is always
  640. * trimmed. So when reading this in, the state should reflect
  641. * that. We also do this for async as a stop gap for lack of
  642. * persistence.
  643. */
  644. if (btrfs_test_opt(fs_info, DISCARD_SYNC) ||
  645. btrfs_test_opt(fs_info, DISCARD_ASYNC))
  646. e->trim_state = BTRFS_TRIM_STATE_TRIMMED;
  647. if (!e->bytes) {
  648. ret = -1;
  649. kmem_cache_free(btrfs_free_space_cachep, e);
  650. goto free_cache;
  651. }
  652. if (type == BTRFS_FREE_SPACE_EXTENT) {
  653. spin_lock(&ctl->tree_lock);
  654. ret = link_free_space(ctl, e);
  655. spin_unlock(&ctl->tree_lock);
  656. if (ret) {
  657. btrfs_err(fs_info,
  658. "Duplicate entries in free space cache, dumping");
  659. kmem_cache_free(btrfs_free_space_cachep, e);
  660. goto free_cache;
  661. }
  662. } else {
  663. ASSERT(num_bitmaps);
  664. num_bitmaps--;
  665. e->bitmap = kmem_cache_zalloc(
  666. btrfs_free_space_bitmap_cachep, GFP_NOFS);
  667. if (!e->bitmap) {
  668. ret = -ENOMEM;
  669. kmem_cache_free(
  670. btrfs_free_space_cachep, e);
  671. goto free_cache;
  672. }
  673. spin_lock(&ctl->tree_lock);
  674. ret = link_free_space(ctl, e);
  675. ctl->total_bitmaps++;
  676. ctl->op->recalc_thresholds(ctl);
  677. spin_unlock(&ctl->tree_lock);
  678. if (ret) {
  679. btrfs_err(fs_info,
  680. "Duplicate entries in free space cache, dumping");
  681. kmem_cache_free(btrfs_free_space_cachep, e);
  682. goto free_cache;
  683. }
  684. list_add_tail(&e->list, &bitmaps);
  685. }
  686. num_entries--;
  687. }
  688. io_ctl_unmap_page(&io_ctl);
  689. /*
  690. * We add the bitmaps at the end of the entries in order that
  691. * the bitmap entries are added to the cache.
  692. */
  693. list_for_each_entry_safe(e, n, &bitmaps, list) {
  694. list_del_init(&e->list);
  695. ret = io_ctl_read_bitmap(&io_ctl, e);
  696. if (ret)
  697. goto free_cache;
  698. e->bitmap_extents = count_bitmap_extents(ctl, e);
  699. if (!btrfs_free_space_trimmed(e)) {
  700. ctl->discardable_extents[BTRFS_STAT_CURR] +=
  701. e->bitmap_extents;
  702. ctl->discardable_bytes[BTRFS_STAT_CURR] += e->bytes;
  703. }
  704. }
  705. io_ctl_drop_pages(&io_ctl);
  706. merge_space_tree(ctl);
  707. ret = 1;
  708. out:
  709. btrfs_discard_update_discardable(ctl->private, ctl);
  710. io_ctl_free(&io_ctl);
  711. return ret;
  712. free_cache:
  713. io_ctl_drop_pages(&io_ctl);
  714. __btrfs_remove_free_space_cache(ctl);
  715. goto out;
  716. }
  717. int load_free_space_cache(struct btrfs_block_group *block_group)
  718. {
  719. struct btrfs_fs_info *fs_info = block_group->fs_info;
  720. struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
  721. struct inode *inode;
  722. struct btrfs_path *path;
  723. int ret = 0;
  724. bool matched;
  725. u64 used = block_group->used;
  726. /*
  727. * If this block group has been marked to be cleared for one reason or
  728. * another then we can't trust the on disk cache, so just return.
  729. */
  730. spin_lock(&block_group->lock);
  731. if (block_group->disk_cache_state != BTRFS_DC_WRITTEN) {
  732. spin_unlock(&block_group->lock);
  733. return 0;
  734. }
  735. spin_unlock(&block_group->lock);
  736. path = btrfs_alloc_path();
  737. if (!path)
  738. return 0;
  739. path->search_commit_root = 1;
  740. path->skip_locking = 1;
  741. /*
  742. * We must pass a path with search_commit_root set to btrfs_iget in
  743. * order to avoid a deadlock when allocating extents for the tree root.
  744. *
  745. * When we are COWing an extent buffer from the tree root, when looking
  746. * for a free extent, at extent-tree.c:find_free_extent(), we can find
  747. * block group without its free space cache loaded. When we find one
  748. * we must load its space cache which requires reading its free space
  749. * cache's inode item from the root tree. If this inode item is located
  750. * in the same leaf that we started COWing before, then we end up in
  751. * deadlock on the extent buffer (trying to read lock it when we
  752. * previously write locked it).
  753. *
  754. * It's safe to read the inode item using the commit root because
  755. * block groups, once loaded, stay in memory forever (until they are
  756. * removed) as well as their space caches once loaded. New block groups
  757. * once created get their ->cached field set to BTRFS_CACHE_FINISHED so
  758. * we will never try to read their inode item while the fs is mounted.
  759. */
  760. inode = lookup_free_space_inode(block_group, path);
  761. if (IS_ERR(inode)) {
  762. btrfs_free_path(path);
  763. return 0;
  764. }
  765. /* We may have converted the inode and made the cache invalid. */
  766. spin_lock(&block_group->lock);
  767. if (block_group->disk_cache_state != BTRFS_DC_WRITTEN) {
  768. spin_unlock(&block_group->lock);
  769. btrfs_free_path(path);
  770. goto out;
  771. }
  772. spin_unlock(&block_group->lock);
  773. ret = __load_free_space_cache(fs_info->tree_root, inode, ctl,
  774. path, block_group->start);
  775. btrfs_free_path(path);
  776. if (ret <= 0)
  777. goto out;
  778. spin_lock(&ctl->tree_lock);
  779. matched = (ctl->free_space == (block_group->length - used -
  780. block_group->bytes_super));
  781. spin_unlock(&ctl->tree_lock);
  782. if (!matched) {
  783. __btrfs_remove_free_space_cache(ctl);
  784. btrfs_warn(fs_info,
  785. "block group %llu has wrong amount of free space",
  786. block_group->start);
  787. ret = -1;
  788. }
  789. out:
  790. if (ret < 0) {
  791. /* This cache is bogus, make sure it gets cleared */
  792. spin_lock(&block_group->lock);
  793. block_group->disk_cache_state = BTRFS_DC_CLEAR;
  794. spin_unlock(&block_group->lock);
  795. ret = 0;
  796. btrfs_warn(fs_info,
  797. "failed to load free space cache for block group %llu, rebuilding it now",
  798. block_group->start);
  799. }
  800. iput(inode);
  801. return ret;
  802. }
  803. static noinline_for_stack
  804. int write_cache_extent_entries(struct btrfs_io_ctl *io_ctl,
  805. struct btrfs_free_space_ctl *ctl,
  806. struct btrfs_block_group *block_group,
  807. int *entries, int *bitmaps,
  808. struct list_head *bitmap_list)
  809. {
  810. int ret;
  811. struct btrfs_free_cluster *cluster = NULL;
  812. struct btrfs_free_cluster *cluster_locked = NULL;
  813. struct rb_node *node = rb_first(&ctl->free_space_offset);
  814. struct btrfs_trim_range *trim_entry;
  815. /* Get the cluster for this block_group if it exists */
  816. if (block_group && !list_empty(&block_group->cluster_list)) {
  817. cluster = list_entry(block_group->cluster_list.next,
  818. struct btrfs_free_cluster,
  819. block_group_list);
  820. }
  821. if (!node && cluster) {
  822. cluster_locked = cluster;
  823. spin_lock(&cluster_locked->lock);
  824. node = rb_first(&cluster->root);
  825. cluster = NULL;
  826. }
  827. /* Write out the extent entries */
  828. while (node) {
  829. struct btrfs_free_space *e;
  830. e = rb_entry(node, struct btrfs_free_space, offset_index);
  831. *entries += 1;
  832. ret = io_ctl_add_entry(io_ctl, e->offset, e->bytes,
  833. e->bitmap);
  834. if (ret)
  835. goto fail;
  836. if (e->bitmap) {
  837. list_add_tail(&e->list, bitmap_list);
  838. *bitmaps += 1;
  839. }
  840. node = rb_next(node);
  841. if (!node && cluster) {
  842. node = rb_first(&cluster->root);
  843. cluster_locked = cluster;
  844. spin_lock(&cluster_locked->lock);
  845. cluster = NULL;
  846. }
  847. }
  848. if (cluster_locked) {
  849. spin_unlock(&cluster_locked->lock);
  850. cluster_locked = NULL;
  851. }
  852. /*
  853. * Make sure we don't miss any range that was removed from our rbtree
  854. * because trimming is running. Otherwise after a umount+mount (or crash
  855. * after committing the transaction) we would leak free space and get
  856. * an inconsistent free space cache report from fsck.
  857. */
  858. list_for_each_entry(trim_entry, &ctl->trimming_ranges, list) {
  859. ret = io_ctl_add_entry(io_ctl, trim_entry->start,
  860. trim_entry->bytes, NULL);
  861. if (ret)
  862. goto fail;
  863. *entries += 1;
  864. }
  865. return 0;
  866. fail:
  867. if (cluster_locked)
  868. spin_unlock(&cluster_locked->lock);
  869. return -ENOSPC;
  870. }
  871. static noinline_for_stack int
  872. update_cache_item(struct btrfs_trans_handle *trans,
  873. struct btrfs_root *root,
  874. struct inode *inode,
  875. struct btrfs_path *path, u64 offset,
  876. int entries, int bitmaps)
  877. {
  878. struct btrfs_key key;
  879. struct btrfs_free_space_header *header;
  880. struct extent_buffer *leaf;
  881. int ret;
  882. key.objectid = BTRFS_FREE_SPACE_OBJECTID;
  883. key.offset = offset;
  884. key.type = 0;
  885. ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
  886. if (ret < 0) {
  887. clear_extent_bit(&BTRFS_I(inode)->io_tree, 0, inode->i_size - 1,
  888. EXTENT_DELALLOC, 0, 0, NULL);
  889. goto fail;
  890. }
  891. leaf = path->nodes[0];
  892. if (ret > 0) {
  893. struct btrfs_key found_key;
  894. ASSERT(path->slots[0]);
  895. path->slots[0]--;
  896. btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
  897. if (found_key.objectid != BTRFS_FREE_SPACE_OBJECTID ||
  898. found_key.offset != offset) {
  899. clear_extent_bit(&BTRFS_I(inode)->io_tree, 0,
  900. inode->i_size - 1, EXTENT_DELALLOC, 0,
  901. 0, NULL);
  902. btrfs_release_path(path);
  903. goto fail;
  904. }
  905. }
  906. BTRFS_I(inode)->generation = trans->transid;
  907. header = btrfs_item_ptr(leaf, path->slots[0],
  908. struct btrfs_free_space_header);
  909. btrfs_set_free_space_entries(leaf, header, entries);
  910. btrfs_set_free_space_bitmaps(leaf, header, bitmaps);
  911. btrfs_set_free_space_generation(leaf, header, trans->transid);
  912. btrfs_mark_buffer_dirty(leaf);
  913. btrfs_release_path(path);
  914. return 0;
  915. fail:
  916. return -1;
  917. }
  918. static noinline_for_stack int write_pinned_extent_entries(
  919. struct btrfs_trans_handle *trans,
  920. struct btrfs_block_group *block_group,
  921. struct btrfs_io_ctl *io_ctl,
  922. int *entries)
  923. {
  924. u64 start, extent_start, extent_end, len;
  925. struct extent_io_tree *unpin = NULL;
  926. int ret;
  927. if (!block_group)
  928. return 0;
  929. /*
  930. * We want to add any pinned extents to our free space cache
  931. * so we don't leak the space
  932. *
  933. * We shouldn't have switched the pinned extents yet so this is the
  934. * right one
  935. */
  936. unpin = &trans->transaction->pinned_extents;
  937. start = block_group->start;
  938. while (start < block_group->start + block_group->length) {
  939. ret = find_first_extent_bit(unpin, start,
  940. &extent_start, &extent_end,
  941. EXTENT_DIRTY, NULL);
  942. if (ret)
  943. return 0;
  944. /* This pinned extent is out of our range */
  945. if (extent_start >= block_group->start + block_group->length)
  946. return 0;
  947. extent_start = max(extent_start, start);
  948. extent_end = min(block_group->start + block_group->length,
  949. extent_end + 1);
  950. len = extent_end - extent_start;
  951. *entries += 1;
  952. ret = io_ctl_add_entry(io_ctl, extent_start, len, NULL);
  953. if (ret)
  954. return -ENOSPC;
  955. start = extent_end;
  956. }
  957. return 0;
  958. }
  959. static noinline_for_stack int
  960. write_bitmap_entries(struct btrfs_io_ctl *io_ctl, struct list_head *bitmap_list)
  961. {
  962. struct btrfs_free_space *entry, *next;
  963. int ret;
  964. /* Write out the bitmaps */
  965. list_for_each_entry_safe(entry, next, bitmap_list, list) {
  966. ret = io_ctl_add_bitmap(io_ctl, entry->bitmap);
  967. if (ret)
  968. return -ENOSPC;
  969. list_del_init(&entry->list);
  970. }
  971. return 0;
  972. }
  973. static int flush_dirty_cache(struct inode *inode)
  974. {
  975. int ret;
  976. ret = btrfs_wait_ordered_range(inode, 0, (u64)-1);
  977. if (ret)
  978. clear_extent_bit(&BTRFS_I(inode)->io_tree, 0, inode->i_size - 1,
  979. EXTENT_DELALLOC, 0, 0, NULL);
  980. return ret;
  981. }
  982. static void noinline_for_stack
  983. cleanup_bitmap_list(struct list_head *bitmap_list)
  984. {
  985. struct btrfs_free_space *entry, *next;
  986. list_for_each_entry_safe(entry, next, bitmap_list, list)
  987. list_del_init(&entry->list);
  988. }
  989. static void noinline_for_stack
  990. cleanup_write_cache_enospc(struct inode *inode,
  991. struct btrfs_io_ctl *io_ctl,
  992. struct extent_state **cached_state)
  993. {
  994. io_ctl_drop_pages(io_ctl);
  995. unlock_extent_cached(&BTRFS_I(inode)->io_tree, 0,
  996. i_size_read(inode) - 1, cached_state);
  997. }
  998. static int __btrfs_wait_cache_io(struct btrfs_root *root,
  999. struct btrfs_trans_handle *trans,
  1000. struct btrfs_block_group *block_group,
  1001. struct btrfs_io_ctl *io_ctl,
  1002. struct btrfs_path *path, u64 offset)
  1003. {
  1004. int ret;
  1005. struct inode *inode = io_ctl->inode;
  1006. if (!inode)
  1007. return 0;
  1008. /* Flush the dirty pages in the cache file. */
  1009. ret = flush_dirty_cache(inode);
  1010. if (ret)
  1011. goto out;
  1012. /* Update the cache item to tell everyone this cache file is valid. */
  1013. ret = update_cache_item(trans, root, inode, path, offset,
  1014. io_ctl->entries, io_ctl->bitmaps);
  1015. out:
  1016. if (ret) {
  1017. invalidate_inode_pages2(inode->i_mapping);
  1018. BTRFS_I(inode)->generation = 0;
  1019. if (block_group)
  1020. btrfs_debug(root->fs_info,
  1021. "failed to write free space cache for block group %llu error %d",
  1022. block_group->start, ret);
  1023. }
  1024. btrfs_update_inode(trans, root, inode);
  1025. if (block_group) {
  1026. /* the dirty list is protected by the dirty_bgs_lock */
  1027. spin_lock(&trans->transaction->dirty_bgs_lock);
  1028. /* the disk_cache_state is protected by the block group lock */
  1029. spin_lock(&block_group->lock);
  1030. /*
  1031. * only mark this as written if we didn't get put back on
  1032. * the dirty list while waiting for IO. Otherwise our
  1033. * cache state won't be right, and we won't get written again
  1034. */
  1035. if (!ret && list_empty(&block_group->dirty_list))
  1036. block_group->disk_cache_state = BTRFS_DC_WRITTEN;
  1037. else if (ret)
  1038. block_group->disk_cache_state = BTRFS_DC_ERROR;
  1039. spin_unlock(&block_group->lock);
  1040. spin_unlock(&trans->transaction->dirty_bgs_lock);
  1041. io_ctl->inode = NULL;
  1042. iput(inode);
  1043. }
  1044. return ret;
  1045. }
  1046. static int btrfs_wait_cache_io_root(struct btrfs_root *root,
  1047. struct btrfs_trans_handle *trans,
  1048. struct btrfs_io_ctl *io_ctl,
  1049. struct btrfs_path *path)
  1050. {
  1051. return __btrfs_wait_cache_io(root, trans, NULL, io_ctl, path, 0);
  1052. }
  1053. int btrfs_wait_cache_io(struct btrfs_trans_handle *trans,
  1054. struct btrfs_block_group *block_group,
  1055. struct btrfs_path *path)
  1056. {
  1057. return __btrfs_wait_cache_io(block_group->fs_info->tree_root, trans,
  1058. block_group, &block_group->io_ctl,
  1059. path, block_group->start);
  1060. }
  1061. /**
  1062. * __btrfs_write_out_cache - write out cached info to an inode
  1063. * @root - the root the inode belongs to
  1064. * @ctl - the free space cache we are going to write out
  1065. * @block_group - the block_group for this cache if it belongs to a block_group
  1066. * @trans - the trans handle
  1067. *
  1068. * This function writes out a free space cache struct to disk for quick recovery
  1069. * on mount. This will return 0 if it was successful in writing the cache out,
  1070. * or an errno if it was not.
  1071. */
  1072. static int __btrfs_write_out_cache(struct btrfs_root *root, struct inode *inode,
  1073. struct btrfs_free_space_ctl *ctl,
  1074. struct btrfs_block_group *block_group,
  1075. struct btrfs_io_ctl *io_ctl,
  1076. struct btrfs_trans_handle *trans)
  1077. {
  1078. struct extent_state *cached_state = NULL;
  1079. LIST_HEAD(bitmap_list);
  1080. int entries = 0;
  1081. int bitmaps = 0;
  1082. int ret;
  1083. int must_iput = 0;
  1084. if (!i_size_read(inode))
  1085. return -EIO;
  1086. WARN_ON(io_ctl->pages);
  1087. ret = io_ctl_init(io_ctl, inode, 1);
  1088. if (ret)
  1089. return ret;
  1090. if (block_group && (block_group->flags & BTRFS_BLOCK_GROUP_DATA)) {
  1091. down_write(&block_group->data_rwsem);
  1092. spin_lock(&block_group->lock);
  1093. if (block_group->delalloc_bytes) {
  1094. block_group->disk_cache_state = BTRFS_DC_WRITTEN;
  1095. spin_unlock(&block_group->lock);
  1096. up_write(&block_group->data_rwsem);
  1097. BTRFS_I(inode)->generation = 0;
  1098. ret = 0;
  1099. must_iput = 1;
  1100. goto out;
  1101. }
  1102. spin_unlock(&block_group->lock);
  1103. }
  1104. /* Lock all pages first so we can lock the extent safely. */
  1105. ret = io_ctl_prepare_pages(io_ctl, false);
  1106. if (ret)
  1107. goto out_unlock;
  1108. lock_extent_bits(&BTRFS_I(inode)->io_tree, 0, i_size_read(inode) - 1,
  1109. &cached_state);
  1110. io_ctl_set_generation(io_ctl, trans->transid);
  1111. mutex_lock(&ctl->cache_writeout_mutex);
  1112. /* Write out the extent entries in the free space cache */
  1113. spin_lock(&ctl->tree_lock);
  1114. ret = write_cache_extent_entries(io_ctl, ctl,
  1115. block_group, &entries, &bitmaps,
  1116. &bitmap_list);
  1117. if (ret)
  1118. goto out_nospc_locked;
  1119. /*
  1120. * Some spaces that are freed in the current transaction are pinned,
  1121. * they will be added into free space cache after the transaction is
  1122. * committed, we shouldn't lose them.
  1123. *
  1124. * If this changes while we are working we'll get added back to
  1125. * the dirty list and redo it. No locking needed
  1126. */
  1127. ret = write_pinned_extent_entries(trans, block_group, io_ctl, &entries);
  1128. if (ret)
  1129. goto out_nospc_locked;
  1130. /*
  1131. * At last, we write out all the bitmaps and keep cache_writeout_mutex
  1132. * locked while doing it because a concurrent trim can be manipulating
  1133. * or freeing the bitmap.
  1134. */
  1135. ret = write_bitmap_entries(io_ctl, &bitmap_list);
  1136. spin_unlock(&ctl->tree_lock);
  1137. mutex_unlock(&ctl->cache_writeout_mutex);
  1138. if (ret)
  1139. goto out_nospc;
  1140. /* Zero out the rest of the pages just to make sure */
  1141. io_ctl_zero_remaining_pages(io_ctl);
  1142. /* Everything is written out, now we dirty the pages in the file. */
  1143. ret = btrfs_dirty_pages(BTRFS_I(inode), io_ctl->pages,
  1144. io_ctl->num_pages, 0, i_size_read(inode),
  1145. &cached_state);
  1146. if (ret)
  1147. goto out_nospc;
  1148. if (block_group && (block_group->flags & BTRFS_BLOCK_GROUP_DATA))
  1149. up_write(&block_group->data_rwsem);
  1150. /*
  1151. * Release the pages and unlock the extent, we will flush
  1152. * them out later
  1153. */
  1154. io_ctl_drop_pages(io_ctl);
  1155. io_ctl_free(io_ctl);
  1156. unlock_extent_cached(&BTRFS_I(inode)->io_tree, 0,
  1157. i_size_read(inode) - 1, &cached_state);
  1158. /*
  1159. * at this point the pages are under IO and we're happy,
  1160. * The caller is responsible for waiting on them and updating
  1161. * the cache and the inode
  1162. */
  1163. io_ctl->entries = entries;
  1164. io_ctl->bitmaps = bitmaps;
  1165. ret = btrfs_fdatawrite_range(inode, 0, (u64)-1);
  1166. if (ret)
  1167. goto out;
  1168. return 0;
  1169. out_nospc_locked:
  1170. cleanup_bitmap_list(&bitmap_list);
  1171. spin_unlock(&ctl->tree_lock);
  1172. mutex_unlock(&ctl->cache_writeout_mutex);
  1173. out_nospc:
  1174. cleanup_write_cache_enospc(inode, io_ctl, &cached_state);
  1175. out_unlock:
  1176. if (block_group && (block_group->flags & BTRFS_BLOCK_GROUP_DATA))
  1177. up_write(&block_group->data_rwsem);
  1178. out:
  1179. io_ctl->inode = NULL;
  1180. io_ctl_free(io_ctl);
  1181. if (ret) {
  1182. invalidate_inode_pages2(inode->i_mapping);
  1183. BTRFS_I(inode)->generation = 0;
  1184. }
  1185. btrfs_update_inode(trans, root, inode);
  1186. if (must_iput)
  1187. iput(inode);
  1188. return ret;
  1189. }
  1190. int btrfs_write_out_cache(struct btrfs_trans_handle *trans,
  1191. struct btrfs_block_group *block_group,
  1192. struct btrfs_path *path)
  1193. {
  1194. struct btrfs_fs_info *fs_info = trans->fs_info;
  1195. struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
  1196. struct inode *inode;
  1197. int ret = 0;
  1198. spin_lock(&block_group->lock);
  1199. if (block_group->disk_cache_state < BTRFS_DC_SETUP) {
  1200. spin_unlock(&block_group->lock);
  1201. return 0;
  1202. }
  1203. spin_unlock(&block_group->lock);
  1204. inode = lookup_free_space_inode(block_group, path);
  1205. if (IS_ERR(inode))
  1206. return 0;
  1207. ret = __btrfs_write_out_cache(fs_info->tree_root, inode, ctl,
  1208. block_group, &block_group->io_ctl, trans);
  1209. if (ret) {
  1210. btrfs_debug(fs_info,
  1211. "failed to write free space cache for block group %llu error %d",
  1212. block_group->start, ret);
  1213. spin_lock(&block_group->lock);
  1214. block_group->disk_cache_state = BTRFS_DC_ERROR;
  1215. spin_unlock(&block_group->lock);
  1216. block_group->io_ctl.inode = NULL;
  1217. iput(inode);
  1218. }
  1219. /*
  1220. * if ret == 0 the caller is expected to call btrfs_wait_cache_io
  1221. * to wait for IO and put the inode
  1222. */
  1223. return ret;
  1224. }
  1225. static inline unsigned long offset_to_bit(u64 bitmap_start, u32 unit,
  1226. u64 offset)
  1227. {
  1228. ASSERT(offset >= bitmap_start);
  1229. offset -= bitmap_start;
  1230. return (unsigned long)(div_u64(offset, unit));
  1231. }
  1232. static inline unsigned long bytes_to_bits(u64 bytes, u32 unit)
  1233. {
  1234. return (unsigned long)(div_u64(bytes, unit));
  1235. }
  1236. static inline u64 offset_to_bitmap(struct btrfs_free_space_ctl *ctl,
  1237. u64 offset)
  1238. {
  1239. u64 bitmap_start;
  1240. u64 bytes_per_bitmap;
  1241. bytes_per_bitmap = BITS_PER_BITMAP * ctl->unit;
  1242. bitmap_start = offset - ctl->start;
  1243. bitmap_start = div64_u64(bitmap_start, bytes_per_bitmap);
  1244. bitmap_start *= bytes_per_bitmap;
  1245. bitmap_start += ctl->start;
  1246. return bitmap_start;
  1247. }
  1248. static int tree_insert_offset(struct rb_root *root, u64 offset,
  1249. struct rb_node *node, int bitmap)
  1250. {
  1251. struct rb_node **p = &root->rb_node;
  1252. struct rb_node *parent = NULL;
  1253. struct btrfs_free_space *info;
  1254. while (*p) {
  1255. parent = *p;
  1256. info = rb_entry(parent, struct btrfs_free_space, offset_index);
  1257. if (offset < info->offset) {
  1258. p = &(*p)->rb_left;
  1259. } else if (offset > info->offset) {
  1260. p = &(*p)->rb_right;
  1261. } else {
  1262. /*
  1263. * we could have a bitmap entry and an extent entry
  1264. * share the same offset. If this is the case, we want
  1265. * the extent entry to always be found first if we do a
  1266. * linear search through the tree, since we want to have
  1267. * the quickest allocation time, and allocating from an
  1268. * extent is faster than allocating from a bitmap. So
  1269. * if we're inserting a bitmap and we find an entry at
  1270. * this offset, we want to go right, or after this entry
  1271. * logically. If we are inserting an extent and we've
  1272. * found a bitmap, we want to go left, or before
  1273. * logically.
  1274. */
  1275. if (bitmap) {
  1276. if (info->bitmap) {
  1277. WARN_ON_ONCE(1);
  1278. return -EEXIST;
  1279. }
  1280. p = &(*p)->rb_right;
  1281. } else {
  1282. if (!info->bitmap) {
  1283. WARN_ON_ONCE(1);
  1284. return -EEXIST;
  1285. }
  1286. p = &(*p)->rb_left;
  1287. }
  1288. }
  1289. }
  1290. rb_link_node(node, parent, p);
  1291. rb_insert_color(node, root);
  1292. return 0;
  1293. }
  1294. /*
  1295. * searches the tree for the given offset.
  1296. *
  1297. * fuzzy - If this is set, then we are trying to make an allocation, and we just
  1298. * want a section that has at least bytes size and comes at or after the given
  1299. * offset.
  1300. */
  1301. static struct btrfs_free_space *
  1302. tree_search_offset(struct btrfs_free_space_ctl *ctl,
  1303. u64 offset, int bitmap_only, int fuzzy)
  1304. {
  1305. struct rb_node *n = ctl->free_space_offset.rb_node;
  1306. struct btrfs_free_space *entry, *prev = NULL;
  1307. /* find entry that is closest to the 'offset' */
  1308. while (1) {
  1309. if (!n) {
  1310. entry = NULL;
  1311. break;
  1312. }
  1313. entry = rb_entry(n, struct btrfs_free_space, offset_index);
  1314. prev = entry;
  1315. if (offset < entry->offset)
  1316. n = n->rb_left;
  1317. else if (offset > entry->offset)
  1318. n = n->rb_right;
  1319. else
  1320. break;
  1321. }
  1322. if (bitmap_only) {
  1323. if (!entry)
  1324. return NULL;
  1325. if (entry->bitmap)
  1326. return entry;
  1327. /*
  1328. * bitmap entry and extent entry may share same offset,
  1329. * in that case, bitmap entry comes after extent entry.
  1330. */
  1331. n = rb_next(n);
  1332. if (!n)
  1333. return NULL;
  1334. entry = rb_entry(n, struct btrfs_free_space, offset_index);
  1335. if (entry->offset != offset)
  1336. return NULL;
  1337. WARN_ON(!entry->bitmap);
  1338. return entry;
  1339. } else if (entry) {
  1340. if (entry->bitmap) {
  1341. /*
  1342. * if previous extent entry covers the offset,
  1343. * we should return it instead of the bitmap entry
  1344. */
  1345. n = rb_prev(&entry->offset_index);
  1346. if (n) {
  1347. prev = rb_entry(n, struct btrfs_free_space,
  1348. offset_index);
  1349. if (!prev->bitmap &&
  1350. prev->offset + prev->bytes > offset)
  1351. entry = prev;
  1352. }
  1353. }
  1354. return entry;
  1355. }
  1356. if (!prev)
  1357. return NULL;
  1358. /* find last entry before the 'offset' */
  1359. entry = prev;
  1360. if (entry->offset > offset) {
  1361. n = rb_prev(&entry->offset_index);
  1362. if (n) {
  1363. entry = rb_entry(n, struct btrfs_free_space,
  1364. offset_index);
  1365. ASSERT(entry->offset <= offset);
  1366. } else {
  1367. if (fuzzy)
  1368. return entry;
  1369. else
  1370. return NULL;
  1371. }
  1372. }
  1373. if (entry->bitmap) {
  1374. n = rb_prev(&entry->offset_index);
  1375. if (n) {
  1376. prev = rb_entry(n, struct btrfs_free_space,
  1377. offset_index);
  1378. if (!prev->bitmap &&
  1379. prev->offset + prev->bytes > offset)
  1380. return prev;
  1381. }
  1382. if (entry->offset + BITS_PER_BITMAP * ctl->unit > offset)
  1383. return entry;
  1384. } else if (entry->offset + entry->bytes > offset)
  1385. return entry;
  1386. if (!fuzzy)
  1387. return NULL;
  1388. while (1) {
  1389. if (entry->bitmap) {
  1390. if (entry->offset + BITS_PER_BITMAP *
  1391. ctl->unit > offset)
  1392. break;
  1393. } else {
  1394. if (entry->offset + entry->bytes > offset)
  1395. break;
  1396. }
  1397. n = rb_next(&entry->offset_index);
  1398. if (!n)
  1399. return NULL;
  1400. entry = rb_entry(n, struct btrfs_free_space, offset_index);
  1401. }
  1402. return entry;
  1403. }
  1404. static inline void
  1405. __unlink_free_space(struct btrfs_free_space_ctl *ctl,
  1406. struct btrfs_free_space *info)
  1407. {
  1408. rb_erase(&info->offset_index, &ctl->free_space_offset);
  1409. ctl->free_extents--;
  1410. if (!info->bitmap && !btrfs_free_space_trimmed(info)) {
  1411. ctl->discardable_extents[BTRFS_STAT_CURR]--;
  1412. ctl->discardable_bytes[BTRFS_STAT_CURR] -= info->bytes;
  1413. }
  1414. }
  1415. static void unlink_free_space(struct btrfs_free_space_ctl *ctl,
  1416. struct btrfs_free_space *info)
  1417. {
  1418. __unlink_free_space(ctl, info);
  1419. ctl->free_space -= info->bytes;
  1420. }
  1421. static int link_free_space(struct btrfs_free_space_ctl *ctl,
  1422. struct btrfs_free_space *info)
  1423. {
  1424. int ret = 0;
  1425. ASSERT(info->bytes || info->bitmap);
  1426. ret = tree_insert_offset(&ctl->free_space_offset, info->offset,
  1427. &info->offset_index, (info->bitmap != NULL));
  1428. if (ret)
  1429. return ret;
  1430. if (!info->bitmap && !btrfs_free_space_trimmed(info)) {
  1431. ctl->discardable_extents[BTRFS_STAT_CURR]++;
  1432. ctl->discardable_bytes[BTRFS_STAT_CURR] += info->bytes;
  1433. }
  1434. ctl->free_space += info->bytes;
  1435. ctl->free_extents++;
  1436. return ret;
  1437. }
  1438. static void recalculate_thresholds(struct btrfs_free_space_ctl *ctl)
  1439. {
  1440. struct btrfs_block_group *block_group = ctl->private;
  1441. u64 max_bytes;
  1442. u64 bitmap_bytes;
  1443. u64 extent_bytes;
  1444. u64 size = block_group->length;
  1445. u64 bytes_per_bg = BITS_PER_BITMAP * ctl->unit;
  1446. u64 max_bitmaps = div64_u64(size + bytes_per_bg - 1, bytes_per_bg);
  1447. max_bitmaps = max_t(u64, max_bitmaps, 1);
  1448. ASSERT(ctl->total_bitmaps <= max_bitmaps);
  1449. /*
  1450. * We are trying to keep the total amount of memory used per 1GiB of
  1451. * space to be MAX_CACHE_BYTES_PER_GIG. However, with a reclamation
  1452. * mechanism of pulling extents >= FORCE_EXTENT_THRESHOLD out of
  1453. * bitmaps, we may end up using more memory than this.
  1454. */
  1455. if (size < SZ_1G)
  1456. max_bytes = MAX_CACHE_BYTES_PER_GIG;
  1457. else
  1458. max_bytes = MAX_CACHE_BYTES_PER_GIG * div_u64(size, SZ_1G);
  1459. bitmap_bytes = ctl->total_bitmaps * ctl->unit;
  1460. /*
  1461. * we want the extent entry threshold to always be at most 1/2 the max
  1462. * bytes we can have, or whatever is less than that.
  1463. */
  1464. extent_bytes = max_bytes - bitmap_bytes;
  1465. extent_bytes = min_t(u64, extent_bytes, max_bytes >> 1);
  1466. ctl->extents_thresh =
  1467. div_u64(extent_bytes, sizeof(struct btrfs_free_space));
  1468. }
  1469. static inline void __bitmap_clear_bits(struct btrfs_free_space_ctl *ctl,
  1470. struct btrfs_free_space *info,
  1471. u64 offset, u64 bytes)
  1472. {
  1473. unsigned long start, count, end;
  1474. int extent_delta = -1;
  1475. start = offset_to_bit(info->offset, ctl->unit, offset);
  1476. count = bytes_to_bits(bytes, ctl->unit);
  1477. end = start + count;
  1478. ASSERT(end <= BITS_PER_BITMAP);
  1479. bitmap_clear(info->bitmap, start, count);
  1480. info->bytes -= bytes;
  1481. if (info->max_extent_size > ctl->unit)
  1482. info->max_extent_size = 0;
  1483. if (start && test_bit(start - 1, info->bitmap))
  1484. extent_delta++;
  1485. if (end < BITS_PER_BITMAP && test_bit(end, info->bitmap))
  1486. extent_delta++;
  1487. info->bitmap_extents += extent_delta;
  1488. if (!btrfs_free_space_trimmed(info)) {
  1489. ctl->discardable_extents[BTRFS_STAT_CURR] += extent_delta;
  1490. ctl->discardable_bytes[BTRFS_STAT_CURR] -= bytes;
  1491. }
  1492. }
  1493. static void bitmap_clear_bits(struct btrfs_free_space_ctl *ctl,
  1494. struct btrfs_free_space *info, u64 offset,
  1495. u64 bytes)
  1496. {
  1497. __bitmap_clear_bits(ctl, info, offset, bytes);
  1498. ctl->free_space -= bytes;
  1499. }
  1500. static void bitmap_set_bits(struct btrfs_free_space_ctl *ctl,
  1501. struct btrfs_free_space *info, u64 offset,
  1502. u64 bytes)
  1503. {
  1504. unsigned long start, count, end;
  1505. int extent_delta = 1;
  1506. start = offset_to_bit(info->offset, ctl->unit, offset);
  1507. count = bytes_to_bits(bytes, ctl->unit);
  1508. end = start + count;
  1509. ASSERT(end <= BITS_PER_BITMAP);
  1510. bitmap_set(info->bitmap, start, count);
  1511. info->bytes += bytes;
  1512. ctl->free_space += bytes;
  1513. if (start && test_bit(start - 1, info->bitmap))
  1514. extent_delta--;
  1515. if (end < BITS_PER_BITMAP && test_bit(end, info->bitmap))
  1516. extent_delta--;
  1517. info->bitmap_extents += extent_delta;
  1518. if (!btrfs_free_space_trimmed(info)) {
  1519. ctl->discardable_extents[BTRFS_STAT_CURR] += extent_delta;
  1520. ctl->discardable_bytes[BTRFS_STAT_CURR] += bytes;
  1521. }
  1522. }
  1523. /*
  1524. * If we can not find suitable extent, we will use bytes to record
  1525. * the size of the max extent.
  1526. */
  1527. static int search_bitmap(struct btrfs_free_space_ctl *ctl,
  1528. struct btrfs_free_space *bitmap_info, u64 *offset,
  1529. u64 *bytes, bool for_alloc)
  1530. {
  1531. unsigned long found_bits = 0;
  1532. unsigned long max_bits = 0;
  1533. unsigned long bits, i;
  1534. unsigned long next_zero;
  1535. unsigned long extent_bits;
  1536. /*
  1537. * Skip searching the bitmap if we don't have a contiguous section that
  1538. * is large enough for this allocation.
  1539. */
  1540. if (for_alloc &&
  1541. bitmap_info->max_extent_size &&
  1542. bitmap_info->max_extent_size < *bytes) {
  1543. *bytes = bitmap_info->max_extent_size;
  1544. return -1;
  1545. }
  1546. i = offset_to_bit(bitmap_info->offset, ctl->unit,
  1547. max_t(u64, *offset, bitmap_info->offset));
  1548. bits = bytes_to_bits(*bytes, ctl->unit);
  1549. for_each_set_bit_from(i, bitmap_info->bitmap, BITS_PER_BITMAP) {
  1550. if (for_alloc && bits == 1) {
  1551. found_bits = 1;
  1552. break;
  1553. }
  1554. next_zero = find_next_zero_bit(bitmap_info->bitmap,
  1555. BITS_PER_BITMAP, i);
  1556. extent_bits = next_zero - i;
  1557. if (extent_bits >= bits) {
  1558. found_bits = extent_bits;
  1559. break;
  1560. } else if (extent_bits > max_bits) {
  1561. max_bits = extent_bits;
  1562. }
  1563. i = next_zero;
  1564. }
  1565. if (found_bits) {
  1566. *offset = (u64)(i * ctl->unit) + bitmap_info->offset;
  1567. *bytes = (u64)(found_bits) * ctl->unit;
  1568. return 0;
  1569. }
  1570. *bytes = (u64)(max_bits) * ctl->unit;
  1571. bitmap_info->max_extent_size = *bytes;
  1572. return -1;
  1573. }
  1574. static inline u64 get_max_extent_size(struct btrfs_free_space *entry)
  1575. {
  1576. if (entry->bitmap)
  1577. return entry->max_extent_size;
  1578. return entry->bytes;
  1579. }
  1580. /* Cache the size of the max extent in bytes */
  1581. static struct btrfs_free_space *
  1582. find_free_space(struct btrfs_free_space_ctl *ctl, u64 *offset, u64 *bytes,
  1583. unsigned long align, u64 *max_extent_size)
  1584. {
  1585. struct btrfs_free_space *entry;
  1586. struct rb_node *node;
  1587. u64 tmp;
  1588. u64 align_off;
  1589. int ret;
  1590. if (!ctl->free_space_offset.rb_node)
  1591. goto out;
  1592. entry = tree_search_offset(ctl, offset_to_bitmap(ctl, *offset), 0, 1);
  1593. if (!entry)
  1594. goto out;
  1595. for (node = &entry->offset_index; node; node = rb_next(node)) {
  1596. entry = rb_entry(node, struct btrfs_free_space, offset_index);
  1597. if (entry->bytes < *bytes) {
  1598. *max_extent_size = max(get_max_extent_size(entry),
  1599. *max_extent_size);
  1600. continue;
  1601. }
  1602. /* make sure the space returned is big enough
  1603. * to match our requested alignment
  1604. */
  1605. if (*bytes >= align) {
  1606. tmp = entry->offset - ctl->start + align - 1;
  1607. tmp = div64_u64(tmp, align);
  1608. tmp = tmp * align + ctl->start;
  1609. align_off = tmp - entry->offset;
  1610. } else {
  1611. align_off = 0;
  1612. tmp = entry->offset;
  1613. }
  1614. if (entry->bytes < *bytes + align_off) {
  1615. *max_extent_size = max(get_max_extent_size(entry),
  1616. *max_extent_size);
  1617. continue;
  1618. }
  1619. if (entry->bitmap) {
  1620. u64 size = *bytes;
  1621. ret = search_bitmap(ctl, entry, &tmp, &size, true);
  1622. if (!ret) {
  1623. *offset = tmp;
  1624. *bytes = size;
  1625. return entry;
  1626. } else {
  1627. *max_extent_size =
  1628. max(get_max_extent_size(entry),
  1629. *max_extent_size);
  1630. }
  1631. continue;
  1632. }
  1633. *offset = tmp;
  1634. *bytes = entry->bytes - align_off;
  1635. return entry;
  1636. }
  1637. out:
  1638. return NULL;
  1639. }
  1640. static int count_bitmap_extents(struct btrfs_free_space_ctl *ctl,
  1641. struct btrfs_free_space *bitmap_info)
  1642. {
  1643. struct btrfs_block_group *block_group = ctl->private;
  1644. u64 bytes = bitmap_info->bytes;
  1645. unsigned int rs, re;
  1646. int count = 0;
  1647. if (!block_group || !bytes)
  1648. return count;
  1649. bitmap_for_each_set_region(bitmap_info->bitmap, rs, re, 0,
  1650. BITS_PER_BITMAP) {
  1651. bytes -= (rs - re) * ctl->unit;
  1652. count++;
  1653. if (!bytes)
  1654. break;
  1655. }
  1656. return count;
  1657. }
  1658. static void add_new_bitmap(struct btrfs_free_space_ctl *ctl,
  1659. struct btrfs_free_space *info, u64 offset)
  1660. {
  1661. info->offset = offset_to_bitmap(ctl, offset);
  1662. info->bytes = 0;
  1663. info->bitmap_extents = 0;
  1664. INIT_LIST_HEAD(&info->list);
  1665. link_free_space(ctl, info);
  1666. ctl->total_bitmaps++;
  1667. ctl->op->recalc_thresholds(ctl);
  1668. }
  1669. static void free_bitmap(struct btrfs_free_space_ctl *ctl,
  1670. struct btrfs_free_space *bitmap_info)
  1671. {
  1672. /*
  1673. * Normally when this is called, the bitmap is completely empty. However,
  1674. * if we are blowing up the free space cache for one reason or another
  1675. * via __btrfs_remove_free_space_cache(), then it may not be freed and
  1676. * we may leave stats on the table.
  1677. */
  1678. if (bitmap_info->bytes && !btrfs_free_space_trimmed(bitmap_info)) {
  1679. ctl->discardable_extents[BTRFS_STAT_CURR] -=
  1680. bitmap_info->bitmap_extents;
  1681. ctl->discardable_bytes[BTRFS_STAT_CURR] -= bitmap_info->bytes;
  1682. }
  1683. unlink_free_space(ctl, bitmap_info);
  1684. kmem_cache_free(btrfs_free_space_bitmap_cachep, bitmap_info->bitmap);
  1685. kmem_cache_free(btrfs_free_space_cachep, bitmap_info);
  1686. ctl->total_bitmaps--;
  1687. ctl->op->recalc_thresholds(ctl);
  1688. }
  1689. static noinline int remove_from_bitmap(struct btrfs_free_space_ctl *ctl,
  1690. struct btrfs_free_space *bitmap_info,
  1691. u64 *offset, u64 *bytes)
  1692. {
  1693. u64 end;
  1694. u64 search_start, search_bytes;
  1695. int ret;
  1696. again:
  1697. end = bitmap_info->offset + (u64)(BITS_PER_BITMAP * ctl->unit) - 1;
  1698. /*
  1699. * We need to search for bits in this bitmap. We could only cover some
  1700. * of the extent in this bitmap thanks to how we add space, so we need
  1701. * to search for as much as it as we can and clear that amount, and then
  1702. * go searching for the next bit.
  1703. */
  1704. search_start = *offset;
  1705. search_bytes = ctl->unit;
  1706. search_bytes = min(search_bytes, end - search_start + 1);
  1707. ret = search_bitmap(ctl, bitmap_info, &search_start, &search_bytes,
  1708. false);
  1709. if (ret < 0 || search_start != *offset)
  1710. return -EINVAL;
  1711. /* We may have found more bits than what we need */
  1712. search_bytes = min(search_bytes, *bytes);
  1713. /* Cannot clear past the end of the bitmap */
  1714. search_bytes = min(search_bytes, end - search_start + 1);
  1715. bitmap_clear_bits(ctl, bitmap_info, search_start, search_bytes);
  1716. *offset += search_bytes;
  1717. *bytes -= search_bytes;
  1718. if (*bytes) {
  1719. struct rb_node *next = rb_next(&bitmap_info->offset_index);
  1720. if (!bitmap_info->bytes)
  1721. free_bitmap(ctl, bitmap_info);
  1722. /*
  1723. * no entry after this bitmap, but we still have bytes to
  1724. * remove, so something has gone wrong.
  1725. */
  1726. if (!next)
  1727. return -EINVAL;
  1728. bitmap_info = rb_entry(next, struct btrfs_free_space,
  1729. offset_index);
  1730. /*
  1731. * if the next entry isn't a bitmap we need to return to let the
  1732. * extent stuff do its work.
  1733. */
  1734. if (!bitmap_info->bitmap)
  1735. return -EAGAIN;
  1736. /*
  1737. * Ok the next item is a bitmap, but it may not actually hold
  1738. * the information for the rest of this free space stuff, so
  1739. * look for it, and if we don't find it return so we can try
  1740. * everything over again.
  1741. */
  1742. search_start = *offset;
  1743. search_bytes = ctl->unit;
  1744. ret = search_bitmap(ctl, bitmap_info, &search_start,
  1745. &search_bytes, false);
  1746. if (ret < 0 || search_start != *offset)
  1747. return -EAGAIN;
  1748. goto again;
  1749. } else if (!bitmap_info->bytes)
  1750. free_bitmap(ctl, bitmap_info);
  1751. return 0;
  1752. }
  1753. static u64 add_bytes_to_bitmap(struct btrfs_free_space_ctl *ctl,
  1754. struct btrfs_free_space *info, u64 offset,
  1755. u64 bytes, enum btrfs_trim_state trim_state)
  1756. {
  1757. u64 bytes_to_set = 0;
  1758. u64 end;
  1759. /*
  1760. * This is a tradeoff to make bitmap trim state minimal. We mark the
  1761. * whole bitmap untrimmed if at any point we add untrimmed regions.
  1762. */
  1763. if (trim_state == BTRFS_TRIM_STATE_UNTRIMMED) {
  1764. if (btrfs_free_space_trimmed(info)) {
  1765. ctl->discardable_extents[BTRFS_STAT_CURR] +=
  1766. info->bitmap_extents;
  1767. ctl->discardable_bytes[BTRFS_STAT_CURR] += info->bytes;
  1768. }
  1769. info->trim_state = BTRFS_TRIM_STATE_UNTRIMMED;
  1770. }
  1771. end = info->offset + (u64)(BITS_PER_BITMAP * ctl->unit);
  1772. bytes_to_set = min(end - offset, bytes);
  1773. bitmap_set_bits(ctl, info, offset, bytes_to_set);
  1774. /*
  1775. * We set some bytes, we have no idea what the max extent size is
  1776. * anymore.
  1777. */
  1778. info->max_extent_size = 0;
  1779. return bytes_to_set;
  1780. }
  1781. static bool use_bitmap(struct btrfs_free_space_ctl *ctl,
  1782. struct btrfs_free_space *info)
  1783. {
  1784. struct btrfs_block_group *block_group = ctl->private;
  1785. struct btrfs_fs_info *fs_info = block_group->fs_info;
  1786. bool forced = false;
  1787. #ifdef CONFIG_BTRFS_DEBUG
  1788. if (btrfs_should_fragment_free_space(block_group))
  1789. forced = true;
  1790. #endif
  1791. /* This is a way to reclaim large regions from the bitmaps. */
  1792. if (!forced && info->bytes >= FORCE_EXTENT_THRESHOLD)
  1793. return false;
  1794. /*
  1795. * If we are below the extents threshold then we can add this as an
  1796. * extent, and don't have to deal with the bitmap
  1797. */
  1798. if (!forced && ctl->free_extents < ctl->extents_thresh) {
  1799. /*
  1800. * If this block group has some small extents we don't want to
  1801. * use up all of our free slots in the cache with them, we want
  1802. * to reserve them to larger extents, however if we have plenty
  1803. * of cache left then go ahead an dadd them, no sense in adding
  1804. * the overhead of a bitmap if we don't have to.
  1805. */
  1806. if (info->bytes <= fs_info->sectorsize * 8) {
  1807. if (ctl->free_extents * 3 <= ctl->extents_thresh)
  1808. return false;
  1809. } else {
  1810. return false;
  1811. }
  1812. }
  1813. /*
  1814. * The original block groups from mkfs can be really small, like 8
  1815. * megabytes, so don't bother with a bitmap for those entries. However
  1816. * some block groups can be smaller than what a bitmap would cover but
  1817. * are still large enough that they could overflow the 32k memory limit,
  1818. * so allow those block groups to still be allowed to have a bitmap
  1819. * entry.
  1820. */
  1821. if (((BITS_PER_BITMAP * ctl->unit) >> 1) > block_group->length)
  1822. return false;
  1823. return true;
  1824. }
  1825. static const struct btrfs_free_space_op free_space_op = {
  1826. .recalc_thresholds = recalculate_thresholds,
  1827. .use_bitmap = use_bitmap,
  1828. };
  1829. static int insert_into_bitmap(struct btrfs_free_space_ctl *ctl,
  1830. struct btrfs_free_space *info)
  1831. {
  1832. struct btrfs_free_space *bitmap_info;
  1833. struct btrfs_block_group *block_group = NULL;
  1834. int added = 0;
  1835. u64 bytes, offset, bytes_added;
  1836. enum btrfs_trim_state trim_state;
  1837. int ret;
  1838. bytes = info->bytes;
  1839. offset = info->offset;
  1840. trim_state = info->trim_state;
  1841. if (!ctl->op->use_bitmap(ctl, info))
  1842. return 0;
  1843. if (ctl->op == &free_space_op)
  1844. block_group = ctl->private;
  1845. again:
  1846. /*
  1847. * Since we link bitmaps right into the cluster we need to see if we
  1848. * have a cluster here, and if so and it has our bitmap we need to add
  1849. * the free space to that bitmap.
  1850. */
  1851. if (block_group && !list_empty(&block_group->cluster_list)) {
  1852. struct btrfs_free_cluster *cluster;
  1853. struct rb_node *node;
  1854. struct btrfs_free_space *entry;
  1855. cluster = list_entry(block_group->cluster_list.next,
  1856. struct btrfs_free_cluster,
  1857. block_group_list);
  1858. spin_lock(&cluster->lock);
  1859. node = rb_first(&cluster->root);
  1860. if (!node) {
  1861. spin_unlock(&cluster->lock);
  1862. goto no_cluster_bitmap;
  1863. }
  1864. entry = rb_entry(node, struct btrfs_free_space, offset_index);
  1865. if (!entry->bitmap) {
  1866. spin_unlock(&cluster->lock);
  1867. goto no_cluster_bitmap;
  1868. }
  1869. if (entry->offset == offset_to_bitmap(ctl, offset)) {
  1870. bytes_added = add_bytes_to_bitmap(ctl, entry, offset,
  1871. bytes, trim_state);
  1872. bytes -= bytes_added;
  1873. offset += bytes_added;
  1874. }
  1875. spin_unlock(&cluster->lock);
  1876. if (!bytes) {
  1877. ret = 1;
  1878. goto out;
  1879. }
  1880. }
  1881. no_cluster_bitmap:
  1882. bitmap_info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset),
  1883. 1, 0);
  1884. if (!bitmap_info) {
  1885. ASSERT(added == 0);
  1886. goto new_bitmap;
  1887. }
  1888. bytes_added = add_bytes_to_bitmap(ctl, bitmap_info, offset, bytes,
  1889. trim_state);
  1890. bytes -= bytes_added;
  1891. offset += bytes_added;
  1892. added = 0;
  1893. if (!bytes) {
  1894. ret = 1;
  1895. goto out;
  1896. } else
  1897. goto again;
  1898. new_bitmap:
  1899. if (info && info->bitmap) {
  1900. add_new_bitmap(ctl, info, offset);
  1901. added = 1;
  1902. info = NULL;
  1903. goto again;
  1904. } else {
  1905. spin_unlock(&ctl->tree_lock);
  1906. /* no pre-allocated info, allocate a new one */
  1907. if (!info) {
  1908. info = kmem_cache_zalloc(btrfs_free_space_cachep,
  1909. GFP_NOFS);
  1910. if (!info) {
  1911. spin_lock(&ctl->tree_lock);
  1912. ret = -ENOMEM;
  1913. goto out;
  1914. }
  1915. }
  1916. /* allocate the bitmap */
  1917. info->bitmap = kmem_cache_zalloc(btrfs_free_space_bitmap_cachep,
  1918. GFP_NOFS);
  1919. info->trim_state = BTRFS_TRIM_STATE_TRIMMED;
  1920. spin_lock(&ctl->tree_lock);
  1921. if (!info->bitmap) {
  1922. ret = -ENOMEM;
  1923. goto out;
  1924. }
  1925. goto again;
  1926. }
  1927. out:
  1928. if (info) {
  1929. if (info->bitmap)
  1930. kmem_cache_free(btrfs_free_space_bitmap_cachep,
  1931. info->bitmap);
  1932. kmem_cache_free(btrfs_free_space_cachep, info);
  1933. }
  1934. return ret;
  1935. }
  1936. /*
  1937. * Free space merging rules:
  1938. * 1) Merge trimmed areas together
  1939. * 2) Let untrimmed areas coalesce with trimmed areas
  1940. * 3) Always pull neighboring regions from bitmaps
  1941. *
  1942. * The above rules are for when we merge free space based on btrfs_trim_state.
  1943. * Rules 2 and 3 are subtle because they are suboptimal, but are done for the
  1944. * same reason: to promote larger extent regions which makes life easier for
  1945. * find_free_extent(). Rule 2 enables coalescing based on the common path
  1946. * being returning free space from btrfs_finish_extent_commit(). So when free
  1947. * space is trimmed, it will prevent aggregating trimmed new region and
  1948. * untrimmed regions in the rb_tree. Rule 3 is purely to obtain larger extents
  1949. * and provide find_free_extent() with the largest extents possible hoping for
  1950. * the reuse path.
  1951. */
  1952. static bool try_merge_free_space(struct btrfs_free_space_ctl *ctl,
  1953. struct btrfs_free_space *info, bool update_stat)
  1954. {
  1955. struct btrfs_free_space *left_info = NULL;
  1956. struct btrfs_free_space *right_info;
  1957. bool merged = false;
  1958. u64 offset = info->offset;
  1959. u64 bytes = info->bytes;
  1960. const bool is_trimmed = btrfs_free_space_trimmed(info);
  1961. /*
  1962. * first we want to see if there is free space adjacent to the range we
  1963. * are adding, if there is remove that struct and add a new one to
  1964. * cover the entire range
  1965. */
  1966. right_info = tree_search_offset(ctl, offset + bytes, 0, 0);
  1967. if (right_info && rb_prev(&right_info->offset_index))
  1968. left_info = rb_entry(rb_prev(&right_info->offset_index),
  1969. struct btrfs_free_space, offset_index);
  1970. else if (!right_info)
  1971. left_info = tree_search_offset(ctl, offset - 1, 0, 0);
  1972. /* See try_merge_free_space() comment. */
  1973. if (right_info && !right_info->bitmap &&
  1974. (!is_trimmed || btrfs_free_space_trimmed(right_info))) {
  1975. if (update_stat)
  1976. unlink_free_space(ctl, right_info);
  1977. else
  1978. __unlink_free_space(ctl, right_info);
  1979. info->bytes += right_info->bytes;
  1980. kmem_cache_free(btrfs_free_space_cachep, right_info);
  1981. merged = true;
  1982. }
  1983. /* See try_merge_free_space() comment. */
  1984. if (left_info && !left_info->bitmap &&
  1985. left_info->offset + left_info->bytes == offset &&
  1986. (!is_trimmed || btrfs_free_space_trimmed(left_info))) {
  1987. if (update_stat)
  1988. unlink_free_space(ctl, left_info);
  1989. else
  1990. __unlink_free_space(ctl, left_info);
  1991. info->offset = left_info->offset;
  1992. info->bytes += left_info->bytes;
  1993. kmem_cache_free(btrfs_free_space_cachep, left_info);
  1994. merged = true;
  1995. }
  1996. return merged;
  1997. }
  1998. static bool steal_from_bitmap_to_end(struct btrfs_free_space_ctl *ctl,
  1999. struct btrfs_free_space *info,
  2000. bool update_stat)
  2001. {
  2002. struct btrfs_free_space *bitmap;
  2003. unsigned long i;
  2004. unsigned long j;
  2005. const u64 end = info->offset + info->bytes;
  2006. const u64 bitmap_offset = offset_to_bitmap(ctl, end);
  2007. u64 bytes;
  2008. bitmap = tree_search_offset(ctl, bitmap_offset, 1, 0);
  2009. if (!bitmap)
  2010. return false;
  2011. i = offset_to_bit(bitmap->offset, ctl->unit, end);
  2012. j = find_next_zero_bit(bitmap->bitmap, BITS_PER_BITMAP, i);
  2013. if (j == i)
  2014. return false;
  2015. bytes = (j - i) * ctl->unit;
  2016. info->bytes += bytes;
  2017. /* See try_merge_free_space() comment. */
  2018. if (!btrfs_free_space_trimmed(bitmap))
  2019. info->trim_state = BTRFS_TRIM_STATE_UNTRIMMED;
  2020. if (update_stat)
  2021. bitmap_clear_bits(ctl, bitmap, end, bytes);
  2022. else
  2023. __bitmap_clear_bits(ctl, bitmap, end, bytes);
  2024. if (!bitmap->bytes)
  2025. free_bitmap(ctl, bitmap);
  2026. return true;
  2027. }
  2028. static bool steal_from_bitmap_to_front(struct btrfs_free_space_ctl *ctl,
  2029. struct btrfs_free_space *info,
  2030. bool update_stat)
  2031. {
  2032. struct btrfs_free_space *bitmap;
  2033. u64 bitmap_offset;
  2034. unsigned long i;
  2035. unsigned long j;
  2036. unsigned long prev_j;
  2037. u64 bytes;
  2038. bitmap_offset = offset_to_bitmap(ctl, info->offset);
  2039. /* If we're on a boundary, try the previous logical bitmap. */
  2040. if (bitmap_offset == info->offset) {
  2041. if (info->offset == 0)
  2042. return false;
  2043. bitmap_offset = offset_to_bitmap(ctl, info->offset - 1);
  2044. }
  2045. bitmap = tree_search_offset(ctl, bitmap_offset, 1, 0);
  2046. if (!bitmap)
  2047. return false;
  2048. i = offset_to_bit(bitmap->offset, ctl->unit, info->offset) - 1;
  2049. j = 0;
  2050. prev_j = (unsigned long)-1;
  2051. for_each_clear_bit_from(j, bitmap->bitmap, BITS_PER_BITMAP) {
  2052. if (j > i)
  2053. break;
  2054. prev_j = j;
  2055. }
  2056. if (prev_j == i)
  2057. return false;
  2058. if (prev_j == (unsigned long)-1)
  2059. bytes = (i + 1) * ctl->unit;
  2060. else
  2061. bytes = (i - prev_j) * ctl->unit;
  2062. info->offset -= bytes;
  2063. info->bytes += bytes;
  2064. /* See try_merge_free_space() comment. */
  2065. if (!btrfs_free_space_trimmed(bitmap))
  2066. info->trim_state = BTRFS_TRIM_STATE_UNTRIMMED;
  2067. if (update_stat)
  2068. bitmap_clear_bits(ctl, bitmap, info->offset, bytes);
  2069. else
  2070. __bitmap_clear_bits(ctl, bitmap, info->offset, bytes);
  2071. if (!bitmap->bytes)
  2072. free_bitmap(ctl, bitmap);
  2073. return true;
  2074. }
  2075. /*
  2076. * We prefer always to allocate from extent entries, both for clustered and
  2077. * non-clustered allocation requests. So when attempting to add a new extent
  2078. * entry, try to see if there's adjacent free space in bitmap entries, and if
  2079. * there is, migrate that space from the bitmaps to the extent.
  2080. * Like this we get better chances of satisfying space allocation requests
  2081. * because we attempt to satisfy them based on a single cache entry, and never
  2082. * on 2 or more entries - even if the entries represent a contiguous free space
  2083. * region (e.g. 1 extent entry + 1 bitmap entry starting where the extent entry
  2084. * ends).
  2085. */
  2086. static void steal_from_bitmap(struct btrfs_free_space_ctl *ctl,
  2087. struct btrfs_free_space *info,
  2088. bool update_stat)
  2089. {
  2090. /*
  2091. * Only work with disconnected entries, as we can change their offset,
  2092. * and must be extent entries.
  2093. */
  2094. ASSERT(!info->bitmap);
  2095. ASSERT(RB_EMPTY_NODE(&info->offset_index));
  2096. if (ctl->total_bitmaps > 0) {
  2097. bool stole_end;
  2098. bool stole_front = false;
  2099. stole_end = steal_from_bitmap_to_end(ctl, info, update_stat);
  2100. if (ctl->total_bitmaps > 0)
  2101. stole_front = steal_from_bitmap_to_front(ctl, info,
  2102. update_stat);
  2103. if (stole_end || stole_front)
  2104. try_merge_free_space(ctl, info, update_stat);
  2105. }
  2106. }
  2107. int __btrfs_add_free_space(struct btrfs_fs_info *fs_info,
  2108. struct btrfs_free_space_ctl *ctl,
  2109. u64 offset, u64 bytes,
  2110. enum btrfs_trim_state trim_state)
  2111. {
  2112. struct btrfs_block_group *block_group = ctl->private;
  2113. struct btrfs_free_space *info;
  2114. int ret = 0;
  2115. u64 filter_bytes = bytes;
  2116. info = kmem_cache_zalloc(btrfs_free_space_cachep, GFP_NOFS);
  2117. if (!info)
  2118. return -ENOMEM;
  2119. info->offset = offset;
  2120. info->bytes = bytes;
  2121. info->trim_state = trim_state;
  2122. RB_CLEAR_NODE(&info->offset_index);
  2123. spin_lock(&ctl->tree_lock);
  2124. if (try_merge_free_space(ctl, info, true))
  2125. goto link;
  2126. /*
  2127. * There was no extent directly to the left or right of this new
  2128. * extent then we know we're going to have to allocate a new extent, so
  2129. * before we do that see if we need to drop this into a bitmap
  2130. */
  2131. ret = insert_into_bitmap(ctl, info);
  2132. if (ret < 0) {
  2133. goto out;
  2134. } else if (ret) {
  2135. ret = 0;
  2136. goto out;
  2137. }
  2138. link:
  2139. /*
  2140. * Only steal free space from adjacent bitmaps if we're sure we're not
  2141. * going to add the new free space to existing bitmap entries - because
  2142. * that would mean unnecessary work that would be reverted. Therefore
  2143. * attempt to steal space from bitmaps if we're adding an extent entry.
  2144. */
  2145. steal_from_bitmap(ctl, info, true);
  2146. filter_bytes = max(filter_bytes, info->bytes);
  2147. ret = link_free_space(ctl, info);
  2148. if (ret)
  2149. kmem_cache_free(btrfs_free_space_cachep, info);
  2150. out:
  2151. btrfs_discard_update_discardable(block_group, ctl);
  2152. spin_unlock(&ctl->tree_lock);
  2153. if (ret) {
  2154. btrfs_crit(fs_info, "unable to add free space :%d", ret);
  2155. ASSERT(ret != -EEXIST);
  2156. }
  2157. if (trim_state != BTRFS_TRIM_STATE_TRIMMED) {
  2158. btrfs_discard_check_filter(block_group, filter_bytes);
  2159. btrfs_discard_queue_work(&fs_info->discard_ctl, block_group);
  2160. }
  2161. return ret;
  2162. }
  2163. int btrfs_add_free_space(struct btrfs_block_group *block_group,
  2164. u64 bytenr, u64 size)
  2165. {
  2166. enum btrfs_trim_state trim_state = BTRFS_TRIM_STATE_UNTRIMMED;
  2167. if (btrfs_test_opt(block_group->fs_info, DISCARD_SYNC))
  2168. trim_state = BTRFS_TRIM_STATE_TRIMMED;
  2169. return __btrfs_add_free_space(block_group->fs_info,
  2170. block_group->free_space_ctl,
  2171. bytenr, size, trim_state);
  2172. }
  2173. /*
  2174. * This is a subtle distinction because when adding free space back in general,
  2175. * we want it to be added as untrimmed for async. But in the case where we add
  2176. * it on loading of a block group, we want to consider it trimmed.
  2177. */
  2178. int btrfs_add_free_space_async_trimmed(struct btrfs_block_group *block_group,
  2179. u64 bytenr, u64 size)
  2180. {
  2181. enum btrfs_trim_state trim_state = BTRFS_TRIM_STATE_UNTRIMMED;
  2182. if (btrfs_test_opt(block_group->fs_info, DISCARD_SYNC) ||
  2183. btrfs_test_opt(block_group->fs_info, DISCARD_ASYNC))
  2184. trim_state = BTRFS_TRIM_STATE_TRIMMED;
  2185. return __btrfs_add_free_space(block_group->fs_info,
  2186. block_group->free_space_ctl,
  2187. bytenr, size, trim_state);
  2188. }
  2189. int btrfs_remove_free_space(struct btrfs_block_group *block_group,
  2190. u64 offset, u64 bytes)
  2191. {
  2192. struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
  2193. struct btrfs_free_space *info;
  2194. int ret;
  2195. bool re_search = false;
  2196. spin_lock(&ctl->tree_lock);
  2197. again:
  2198. ret = 0;
  2199. if (!bytes)
  2200. goto out_lock;
  2201. info = tree_search_offset(ctl, offset, 0, 0);
  2202. if (!info) {
  2203. /*
  2204. * oops didn't find an extent that matched the space we wanted
  2205. * to remove, look for a bitmap instead
  2206. */
  2207. info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset),
  2208. 1, 0);
  2209. if (!info) {
  2210. /*
  2211. * If we found a partial bit of our free space in a
  2212. * bitmap but then couldn't find the other part this may
  2213. * be a problem, so WARN about it.
  2214. */
  2215. WARN_ON(re_search);
  2216. goto out_lock;
  2217. }
  2218. }
  2219. re_search = false;
  2220. if (!info->bitmap) {
  2221. unlink_free_space(ctl, info);
  2222. if (offset == info->offset) {
  2223. u64 to_free = min(bytes, info->bytes);
  2224. info->bytes -= to_free;
  2225. info->offset += to_free;
  2226. if (info->bytes) {
  2227. ret = link_free_space(ctl, info);
  2228. WARN_ON(ret);
  2229. } else {
  2230. kmem_cache_free(btrfs_free_space_cachep, info);
  2231. }
  2232. offset += to_free;
  2233. bytes -= to_free;
  2234. goto again;
  2235. } else {
  2236. u64 old_end = info->bytes + info->offset;
  2237. info->bytes = offset - info->offset;
  2238. ret = link_free_space(ctl, info);
  2239. WARN_ON(ret);
  2240. if (ret)
  2241. goto out_lock;
  2242. /* Not enough bytes in this entry to satisfy us */
  2243. if (old_end < offset + bytes) {
  2244. bytes -= old_end - offset;
  2245. offset = old_end;
  2246. goto again;
  2247. } else if (old_end == offset + bytes) {
  2248. /* all done */
  2249. goto out_lock;
  2250. }
  2251. spin_unlock(&ctl->tree_lock);
  2252. ret = __btrfs_add_free_space(block_group->fs_info, ctl,
  2253. offset + bytes,
  2254. old_end - (offset + bytes),
  2255. info->trim_state);
  2256. WARN_ON(ret);
  2257. goto out;
  2258. }
  2259. }
  2260. ret = remove_from_bitmap(ctl, info, &offset, &bytes);
  2261. if (ret == -EAGAIN) {
  2262. re_search = true;
  2263. goto again;
  2264. }
  2265. out_lock:
  2266. btrfs_discard_update_discardable(block_group, ctl);
  2267. spin_unlock(&ctl->tree_lock);
  2268. out:
  2269. return ret;
  2270. }
  2271. void btrfs_dump_free_space(struct btrfs_block_group *block_group,
  2272. u64 bytes)
  2273. {
  2274. struct btrfs_fs_info *fs_info = block_group->fs_info;
  2275. struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
  2276. struct btrfs_free_space *info;
  2277. struct rb_node *n;
  2278. int count = 0;
  2279. spin_lock(&ctl->tree_lock);
  2280. for (n = rb_first(&ctl->free_space_offset); n; n = rb_next(n)) {
  2281. info = rb_entry(n, struct btrfs_free_space, offset_index);
  2282. if (info->bytes >= bytes && !block_group->ro)
  2283. count++;
  2284. btrfs_crit(fs_info, "entry offset %llu, bytes %llu, bitmap %s",
  2285. info->offset, info->bytes,
  2286. (info->bitmap) ? "yes" : "no");
  2287. }
  2288. spin_unlock(&ctl->tree_lock);
  2289. btrfs_info(fs_info, "block group has cluster?: %s",
  2290. list_empty(&block_group->cluster_list) ? "no" : "yes");
  2291. btrfs_info(fs_info,
  2292. "%d blocks of free space at or bigger than bytes is", count);
  2293. }
  2294. void btrfs_init_free_space_ctl(struct btrfs_block_group *block_group)
  2295. {
  2296. struct btrfs_fs_info *fs_info = block_group->fs_info;
  2297. struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
  2298. spin_lock_init(&ctl->tree_lock);
  2299. ctl->unit = fs_info->sectorsize;
  2300. ctl->start = block_group->start;
  2301. ctl->private = block_group;
  2302. ctl->op = &free_space_op;
  2303. INIT_LIST_HEAD(&ctl->trimming_ranges);
  2304. mutex_init(&ctl->cache_writeout_mutex);
  2305. /*
  2306. * we only want to have 32k of ram per block group for keeping
  2307. * track of free space, and if we pass 1/2 of that we want to
  2308. * start converting things over to using bitmaps
  2309. */
  2310. ctl->extents_thresh = (SZ_32K / 2) / sizeof(struct btrfs_free_space);
  2311. }
  2312. /*
  2313. * for a given cluster, put all of its extents back into the free
  2314. * space cache. If the block group passed doesn't match the block group
  2315. * pointed to by the cluster, someone else raced in and freed the
  2316. * cluster already. In that case, we just return without changing anything
  2317. */
  2318. static void __btrfs_return_cluster_to_free_space(
  2319. struct btrfs_block_group *block_group,
  2320. struct btrfs_free_cluster *cluster)
  2321. {
  2322. struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
  2323. struct btrfs_free_space *entry;
  2324. struct rb_node *node;
  2325. spin_lock(&cluster->lock);
  2326. if (cluster->block_group != block_group) {
  2327. spin_unlock(&cluster->lock);
  2328. return;
  2329. }
  2330. cluster->block_group = NULL;
  2331. cluster->window_start = 0;
  2332. list_del_init(&cluster->block_group_list);
  2333. node = rb_first(&cluster->root);
  2334. while (node) {
  2335. bool bitmap;
  2336. entry = rb_entry(node, struct btrfs_free_space, offset_index);
  2337. node = rb_next(&entry->offset_index);
  2338. rb_erase(&entry->offset_index, &cluster->root);
  2339. RB_CLEAR_NODE(&entry->offset_index);
  2340. bitmap = (entry->bitmap != NULL);
  2341. if (!bitmap) {
  2342. /* Merging treats extents as if they were new */
  2343. if (!btrfs_free_space_trimmed(entry)) {
  2344. ctl->discardable_extents[BTRFS_STAT_CURR]--;
  2345. ctl->discardable_bytes[BTRFS_STAT_CURR] -=
  2346. entry->bytes;
  2347. }
  2348. try_merge_free_space(ctl, entry, false);
  2349. steal_from_bitmap(ctl, entry, false);
  2350. /* As we insert directly, update these statistics */
  2351. if (!btrfs_free_space_trimmed(entry)) {
  2352. ctl->discardable_extents[BTRFS_STAT_CURR]++;
  2353. ctl->discardable_bytes[BTRFS_STAT_CURR] +=
  2354. entry->bytes;
  2355. }
  2356. }
  2357. tree_insert_offset(&ctl->free_space_offset,
  2358. entry->offset, &entry->offset_index, bitmap);
  2359. }
  2360. cluster->root = RB_ROOT;
  2361. spin_unlock(&cluster->lock);
  2362. btrfs_put_block_group(block_group);
  2363. }
  2364. static void __btrfs_remove_free_space_cache_locked(
  2365. struct btrfs_free_space_ctl *ctl)
  2366. {
  2367. struct btrfs_free_space *info;
  2368. struct rb_node *node;
  2369. while ((node = rb_last(&ctl->free_space_offset)) != NULL) {
  2370. info = rb_entry(node, struct btrfs_free_space, offset_index);
  2371. if (!info->bitmap) {
  2372. unlink_free_space(ctl, info);
  2373. kmem_cache_free(btrfs_free_space_cachep, info);
  2374. } else {
  2375. free_bitmap(ctl, info);
  2376. }
  2377. cond_resched_lock(&ctl->tree_lock);
  2378. }
  2379. }
  2380. void __btrfs_remove_free_space_cache(struct btrfs_free_space_ctl *ctl)
  2381. {
  2382. spin_lock(&ctl->tree_lock);
  2383. __btrfs_remove_free_space_cache_locked(ctl);
  2384. if (ctl->private)
  2385. btrfs_discard_update_discardable(ctl->private, ctl);
  2386. spin_unlock(&ctl->tree_lock);
  2387. }
  2388. void btrfs_remove_free_space_cache(struct btrfs_block_group *block_group)
  2389. {
  2390. struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
  2391. struct btrfs_free_cluster *cluster;
  2392. struct list_head *head;
  2393. spin_lock(&ctl->tree_lock);
  2394. while ((head = block_group->cluster_list.next) !=
  2395. &block_group->cluster_list) {
  2396. cluster = list_entry(head, struct btrfs_free_cluster,
  2397. block_group_list);
  2398. WARN_ON(cluster->block_group != block_group);
  2399. __btrfs_return_cluster_to_free_space(block_group, cluster);
  2400. cond_resched_lock(&ctl->tree_lock);
  2401. }
  2402. __btrfs_remove_free_space_cache_locked(ctl);
  2403. btrfs_discard_update_discardable(block_group, ctl);
  2404. spin_unlock(&ctl->tree_lock);
  2405. }
  2406. /**
  2407. * btrfs_is_free_space_trimmed - see if everything is trimmed
  2408. * @block_group: block_group of interest
  2409. *
  2410. * Walk @block_group's free space rb_tree to determine if everything is trimmed.
  2411. */
  2412. bool btrfs_is_free_space_trimmed(struct btrfs_block_group *block_group)
  2413. {
  2414. struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
  2415. struct btrfs_free_space *info;
  2416. struct rb_node *node;
  2417. bool ret = true;
  2418. spin_lock(&ctl->tree_lock);
  2419. node = rb_first(&ctl->free_space_offset);
  2420. while (node) {
  2421. info = rb_entry(node, struct btrfs_free_space, offset_index);
  2422. if (!btrfs_free_space_trimmed(info)) {
  2423. ret = false;
  2424. break;
  2425. }
  2426. node = rb_next(node);
  2427. }
  2428. spin_unlock(&ctl->tree_lock);
  2429. return ret;
  2430. }
  2431. u64 btrfs_find_space_for_alloc(struct btrfs_block_group *block_group,
  2432. u64 offset, u64 bytes, u64 empty_size,
  2433. u64 *max_extent_size)
  2434. {
  2435. struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
  2436. struct btrfs_discard_ctl *discard_ctl =
  2437. &block_group->fs_info->discard_ctl;
  2438. struct btrfs_free_space *entry = NULL;
  2439. u64 bytes_search = bytes + empty_size;
  2440. u64 ret = 0;
  2441. u64 align_gap = 0;
  2442. u64 align_gap_len = 0;
  2443. enum btrfs_trim_state align_gap_trim_state = BTRFS_TRIM_STATE_UNTRIMMED;
  2444. spin_lock(&ctl->tree_lock);
  2445. entry = find_free_space(ctl, &offset, &bytes_search,
  2446. block_group->full_stripe_len, max_extent_size);
  2447. if (!entry)
  2448. goto out;
  2449. ret = offset;
  2450. if (entry->bitmap) {
  2451. bitmap_clear_bits(ctl, entry, offset, bytes);
  2452. if (!btrfs_free_space_trimmed(entry))
  2453. atomic64_add(bytes, &discard_ctl->discard_bytes_saved);
  2454. if (!entry->bytes)
  2455. free_bitmap(ctl, entry);
  2456. } else {
  2457. unlink_free_space(ctl, entry);
  2458. align_gap_len = offset - entry->offset;
  2459. align_gap = entry->offset;
  2460. align_gap_trim_state = entry->trim_state;
  2461. if (!btrfs_free_space_trimmed(entry))
  2462. atomic64_add(bytes, &discard_ctl->discard_bytes_saved);
  2463. entry->offset = offset + bytes;
  2464. WARN_ON(entry->bytes < bytes + align_gap_len);
  2465. entry->bytes -= bytes + align_gap_len;
  2466. if (!entry->bytes)
  2467. kmem_cache_free(btrfs_free_space_cachep, entry);
  2468. else
  2469. link_free_space(ctl, entry);
  2470. }
  2471. out:
  2472. btrfs_discard_update_discardable(block_group, ctl);
  2473. spin_unlock(&ctl->tree_lock);
  2474. if (align_gap_len)
  2475. __btrfs_add_free_space(block_group->fs_info, ctl,
  2476. align_gap, align_gap_len,
  2477. align_gap_trim_state);
  2478. return ret;
  2479. }
  2480. /*
  2481. * given a cluster, put all of its extents back into the free space
  2482. * cache. If a block group is passed, this function will only free
  2483. * a cluster that belongs to the passed block group.
  2484. *
  2485. * Otherwise, it'll get a reference on the block group pointed to by the
  2486. * cluster and remove the cluster from it.
  2487. */
  2488. void btrfs_return_cluster_to_free_space(
  2489. struct btrfs_block_group *block_group,
  2490. struct btrfs_free_cluster *cluster)
  2491. {
  2492. struct btrfs_free_space_ctl *ctl;
  2493. /* first, get a safe pointer to the block group */
  2494. spin_lock(&cluster->lock);
  2495. if (!block_group) {
  2496. block_group = cluster->block_group;
  2497. if (!block_group) {
  2498. spin_unlock(&cluster->lock);
  2499. return;
  2500. }
  2501. } else if (cluster->block_group != block_group) {
  2502. /* someone else has already freed it don't redo their work */
  2503. spin_unlock(&cluster->lock);
  2504. return;
  2505. }
  2506. btrfs_get_block_group(block_group);
  2507. spin_unlock(&cluster->lock);
  2508. ctl = block_group->free_space_ctl;
  2509. /* now return any extents the cluster had on it */
  2510. spin_lock(&ctl->tree_lock);
  2511. __btrfs_return_cluster_to_free_space(block_group, cluster);
  2512. spin_unlock(&ctl->tree_lock);
  2513. btrfs_discard_queue_work(&block_group->fs_info->discard_ctl, block_group);
  2514. /* finally drop our ref */
  2515. btrfs_put_block_group(block_group);
  2516. }
  2517. static u64 btrfs_alloc_from_bitmap(struct btrfs_block_group *block_group,
  2518. struct btrfs_free_cluster *cluster,
  2519. struct btrfs_free_space *entry,
  2520. u64 bytes, u64 min_start,
  2521. u64 *max_extent_size)
  2522. {
  2523. struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
  2524. int err;
  2525. u64 search_start = cluster->window_start;
  2526. u64 search_bytes = bytes;
  2527. u64 ret = 0;
  2528. search_start = min_start;
  2529. search_bytes = bytes;
  2530. err = search_bitmap(ctl, entry, &search_start, &search_bytes, true);
  2531. if (err) {
  2532. *max_extent_size = max(get_max_extent_size(entry),
  2533. *max_extent_size);
  2534. return 0;
  2535. }
  2536. ret = search_start;
  2537. __bitmap_clear_bits(ctl, entry, ret, bytes);
  2538. return ret;
  2539. }
  2540. /*
  2541. * given a cluster, try to allocate 'bytes' from it, returns 0
  2542. * if it couldn't find anything suitably large, or a logical disk offset
  2543. * if things worked out
  2544. */
  2545. u64 btrfs_alloc_from_cluster(struct btrfs_block_group *block_group,
  2546. struct btrfs_free_cluster *cluster, u64 bytes,
  2547. u64 min_start, u64 *max_extent_size)
  2548. {
  2549. struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
  2550. struct btrfs_discard_ctl *discard_ctl =
  2551. &block_group->fs_info->discard_ctl;
  2552. struct btrfs_free_space *entry = NULL;
  2553. struct rb_node *node;
  2554. u64 ret = 0;
  2555. spin_lock(&cluster->lock);
  2556. if (bytes > cluster->max_size)
  2557. goto out;
  2558. if (cluster->block_group != block_group)
  2559. goto out;
  2560. node = rb_first(&cluster->root);
  2561. if (!node)
  2562. goto out;
  2563. entry = rb_entry(node, struct btrfs_free_space, offset_index);
  2564. while (1) {
  2565. if (entry->bytes < bytes)
  2566. *max_extent_size = max(get_max_extent_size(entry),
  2567. *max_extent_size);
  2568. if (entry->bytes < bytes ||
  2569. (!entry->bitmap && entry->offset < min_start)) {
  2570. node = rb_next(&entry->offset_index);
  2571. if (!node)
  2572. break;
  2573. entry = rb_entry(node, struct btrfs_free_space,
  2574. offset_index);
  2575. continue;
  2576. }
  2577. if (entry->bitmap) {
  2578. ret = btrfs_alloc_from_bitmap(block_group,
  2579. cluster, entry, bytes,
  2580. cluster->window_start,
  2581. max_extent_size);
  2582. if (ret == 0) {
  2583. node = rb_next(&entry->offset_index);
  2584. if (!node)
  2585. break;
  2586. entry = rb_entry(node, struct btrfs_free_space,
  2587. offset_index);
  2588. continue;
  2589. }
  2590. cluster->window_start += bytes;
  2591. } else {
  2592. ret = entry->offset;
  2593. entry->offset += bytes;
  2594. entry->bytes -= bytes;
  2595. }
  2596. break;
  2597. }
  2598. out:
  2599. spin_unlock(&cluster->lock);
  2600. if (!ret)
  2601. return 0;
  2602. spin_lock(&ctl->tree_lock);
  2603. if (!btrfs_free_space_trimmed(entry))
  2604. atomic64_add(bytes, &discard_ctl->discard_bytes_saved);
  2605. ctl->free_space -= bytes;
  2606. if (!entry->bitmap && !btrfs_free_space_trimmed(entry))
  2607. ctl->discardable_bytes[BTRFS_STAT_CURR] -= bytes;
  2608. spin_lock(&cluster->lock);
  2609. if (entry->bytes == 0) {
  2610. rb_erase(&entry->offset_index, &cluster->root);
  2611. ctl->free_extents--;
  2612. if (entry->bitmap) {
  2613. kmem_cache_free(btrfs_free_space_bitmap_cachep,
  2614. entry->bitmap);
  2615. ctl->total_bitmaps--;
  2616. ctl->op->recalc_thresholds(ctl);
  2617. } else if (!btrfs_free_space_trimmed(entry)) {
  2618. ctl->discardable_extents[BTRFS_STAT_CURR]--;
  2619. }
  2620. kmem_cache_free(btrfs_free_space_cachep, entry);
  2621. }
  2622. spin_unlock(&cluster->lock);
  2623. spin_unlock(&ctl->tree_lock);
  2624. return ret;
  2625. }
  2626. static int btrfs_bitmap_cluster(struct btrfs_block_group *block_group,
  2627. struct btrfs_free_space *entry,
  2628. struct btrfs_free_cluster *cluster,
  2629. u64 offset, u64 bytes,
  2630. u64 cont1_bytes, u64 min_bytes)
  2631. {
  2632. struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
  2633. unsigned long next_zero;
  2634. unsigned long i;
  2635. unsigned long want_bits;
  2636. unsigned long min_bits;
  2637. unsigned long found_bits;
  2638. unsigned long max_bits = 0;
  2639. unsigned long start = 0;
  2640. unsigned long total_found = 0;
  2641. int ret;
  2642. i = offset_to_bit(entry->offset, ctl->unit,
  2643. max_t(u64, offset, entry->offset));
  2644. want_bits = bytes_to_bits(bytes, ctl->unit);
  2645. min_bits = bytes_to_bits(min_bytes, ctl->unit);
  2646. /*
  2647. * Don't bother looking for a cluster in this bitmap if it's heavily
  2648. * fragmented.
  2649. */
  2650. if (entry->max_extent_size &&
  2651. entry->max_extent_size < cont1_bytes)
  2652. return -ENOSPC;
  2653. again:
  2654. found_bits = 0;
  2655. for_each_set_bit_from(i, entry->bitmap, BITS_PER_BITMAP) {
  2656. next_zero = find_next_zero_bit(entry->bitmap,
  2657. BITS_PER_BITMAP, i);
  2658. if (next_zero - i >= min_bits) {
  2659. found_bits = next_zero - i;
  2660. if (found_bits > max_bits)
  2661. max_bits = found_bits;
  2662. break;
  2663. }
  2664. if (next_zero - i > max_bits)
  2665. max_bits = next_zero - i;
  2666. i = next_zero;
  2667. }
  2668. if (!found_bits) {
  2669. entry->max_extent_size = (u64)max_bits * ctl->unit;
  2670. return -ENOSPC;
  2671. }
  2672. if (!total_found) {
  2673. start = i;
  2674. cluster->max_size = 0;
  2675. }
  2676. total_found += found_bits;
  2677. if (cluster->max_size < found_bits * ctl->unit)
  2678. cluster->max_size = found_bits * ctl->unit;
  2679. if (total_found < want_bits || cluster->max_size < cont1_bytes) {
  2680. i = next_zero + 1;
  2681. goto again;
  2682. }
  2683. cluster->window_start = start * ctl->unit + entry->offset;
  2684. rb_erase(&entry->offset_index, &ctl->free_space_offset);
  2685. ret = tree_insert_offset(&cluster->root, entry->offset,
  2686. &entry->offset_index, 1);
  2687. ASSERT(!ret); /* -EEXIST; Logic error */
  2688. trace_btrfs_setup_cluster(block_group, cluster,
  2689. total_found * ctl->unit, 1);
  2690. return 0;
  2691. }
  2692. /*
  2693. * This searches the block group for just extents to fill the cluster with.
  2694. * Try to find a cluster with at least bytes total bytes, at least one
  2695. * extent of cont1_bytes, and other clusters of at least min_bytes.
  2696. */
  2697. static noinline int
  2698. setup_cluster_no_bitmap(struct btrfs_block_group *block_group,
  2699. struct btrfs_free_cluster *cluster,
  2700. struct list_head *bitmaps, u64 offset, u64 bytes,
  2701. u64 cont1_bytes, u64 min_bytes)
  2702. {
  2703. struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
  2704. struct btrfs_free_space *first = NULL;
  2705. struct btrfs_free_space *entry = NULL;
  2706. struct btrfs_free_space *last;
  2707. struct rb_node *node;
  2708. u64 window_free;
  2709. u64 max_extent;
  2710. u64 total_size = 0;
  2711. entry = tree_search_offset(ctl, offset, 0, 1);
  2712. if (!entry)
  2713. return -ENOSPC;
  2714. /*
  2715. * We don't want bitmaps, so just move along until we find a normal
  2716. * extent entry.
  2717. */
  2718. while (entry->bitmap || entry->bytes < min_bytes) {
  2719. if (entry->bitmap && list_empty(&entry->list))
  2720. list_add_tail(&entry->list, bitmaps);
  2721. node = rb_next(&entry->offset_index);
  2722. if (!node)
  2723. return -ENOSPC;
  2724. entry = rb_entry(node, struct btrfs_free_space, offset_index);
  2725. }
  2726. window_free = entry->bytes;
  2727. max_extent = entry->bytes;
  2728. first = entry;
  2729. last = entry;
  2730. for (node = rb_next(&entry->offset_index); node;
  2731. node = rb_next(&entry->offset_index)) {
  2732. entry = rb_entry(node, struct btrfs_free_space, offset_index);
  2733. if (entry->bitmap) {
  2734. if (list_empty(&entry->list))
  2735. list_add_tail(&entry->list, bitmaps);
  2736. continue;
  2737. }
  2738. if (entry->bytes < min_bytes)
  2739. continue;
  2740. last = entry;
  2741. window_free += entry->bytes;
  2742. if (entry->bytes > max_extent)
  2743. max_extent = entry->bytes;
  2744. }
  2745. if (window_free < bytes || max_extent < cont1_bytes)
  2746. return -ENOSPC;
  2747. cluster->window_start = first->offset;
  2748. node = &first->offset_index;
  2749. /*
  2750. * now we've found our entries, pull them out of the free space
  2751. * cache and put them into the cluster rbtree
  2752. */
  2753. do {
  2754. int ret;
  2755. entry = rb_entry(node, struct btrfs_free_space, offset_index);
  2756. node = rb_next(&entry->offset_index);
  2757. if (entry->bitmap || entry->bytes < min_bytes)
  2758. continue;
  2759. rb_erase(&entry->offset_index, &ctl->free_space_offset);
  2760. ret = tree_insert_offset(&cluster->root, entry->offset,
  2761. &entry->offset_index, 0);
  2762. total_size += entry->bytes;
  2763. ASSERT(!ret); /* -EEXIST; Logic error */
  2764. } while (node && entry != last);
  2765. cluster->max_size = max_extent;
  2766. trace_btrfs_setup_cluster(block_group, cluster, total_size, 0);
  2767. return 0;
  2768. }
  2769. /*
  2770. * This specifically looks for bitmaps that may work in the cluster, we assume
  2771. * that we have already failed to find extents that will work.
  2772. */
  2773. static noinline int
  2774. setup_cluster_bitmap(struct btrfs_block_group *block_group,
  2775. struct btrfs_free_cluster *cluster,
  2776. struct list_head *bitmaps, u64 offset, u64 bytes,
  2777. u64 cont1_bytes, u64 min_bytes)
  2778. {
  2779. struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
  2780. struct btrfs_free_space *entry = NULL;
  2781. int ret = -ENOSPC;
  2782. u64 bitmap_offset = offset_to_bitmap(ctl, offset);
  2783. if (ctl->total_bitmaps == 0)
  2784. return -ENOSPC;
  2785. /*
  2786. * The bitmap that covers offset won't be in the list unless offset
  2787. * is just its start offset.
  2788. */
  2789. if (!list_empty(bitmaps))
  2790. entry = list_first_entry(bitmaps, struct btrfs_free_space, list);
  2791. if (!entry || entry->offset != bitmap_offset) {
  2792. entry = tree_search_offset(ctl, bitmap_offset, 1, 0);
  2793. if (entry && list_empty(&entry->list))
  2794. list_add(&entry->list, bitmaps);
  2795. }
  2796. list_for_each_entry(entry, bitmaps, list) {
  2797. if (entry->bytes < bytes)
  2798. continue;
  2799. ret = btrfs_bitmap_cluster(block_group, entry, cluster, offset,
  2800. bytes, cont1_bytes, min_bytes);
  2801. if (!ret)
  2802. return 0;
  2803. }
  2804. /*
  2805. * The bitmaps list has all the bitmaps that record free space
  2806. * starting after offset, so no more search is required.
  2807. */
  2808. return -ENOSPC;
  2809. }
  2810. /*
  2811. * here we try to find a cluster of blocks in a block group. The goal
  2812. * is to find at least bytes+empty_size.
  2813. * We might not find them all in one contiguous area.
  2814. *
  2815. * returns zero and sets up cluster if things worked out, otherwise
  2816. * it returns -enospc
  2817. */
  2818. int btrfs_find_space_cluster(struct btrfs_block_group *block_group,
  2819. struct btrfs_free_cluster *cluster,
  2820. u64 offset, u64 bytes, u64 empty_size)
  2821. {
  2822. struct btrfs_fs_info *fs_info = block_group->fs_info;
  2823. struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
  2824. struct btrfs_free_space *entry, *tmp;
  2825. LIST_HEAD(bitmaps);
  2826. u64 min_bytes;
  2827. u64 cont1_bytes;
  2828. int ret;
  2829. /*
  2830. * Choose the minimum extent size we'll require for this
  2831. * cluster. For SSD_SPREAD, don't allow any fragmentation.
  2832. * For metadata, allow allocates with smaller extents. For
  2833. * data, keep it dense.
  2834. */
  2835. if (btrfs_test_opt(fs_info, SSD_SPREAD)) {
  2836. cont1_bytes = min_bytes = bytes + empty_size;
  2837. } else if (block_group->flags & BTRFS_BLOCK_GROUP_METADATA) {
  2838. cont1_bytes = bytes;
  2839. min_bytes = fs_info->sectorsize;
  2840. } else {
  2841. cont1_bytes = max(bytes, (bytes + empty_size) >> 2);
  2842. min_bytes = fs_info->sectorsize;
  2843. }
  2844. spin_lock(&ctl->tree_lock);
  2845. /*
  2846. * If we know we don't have enough space to make a cluster don't even
  2847. * bother doing all the work to try and find one.
  2848. */
  2849. if (ctl->free_space < bytes) {
  2850. spin_unlock(&ctl->tree_lock);
  2851. return -ENOSPC;
  2852. }
  2853. spin_lock(&cluster->lock);
  2854. /* someone already found a cluster, hooray */
  2855. if (cluster->block_group) {
  2856. ret = 0;
  2857. goto out;
  2858. }
  2859. trace_btrfs_find_cluster(block_group, offset, bytes, empty_size,
  2860. min_bytes);
  2861. ret = setup_cluster_no_bitmap(block_group, cluster, &bitmaps, offset,
  2862. bytes + empty_size,
  2863. cont1_bytes, min_bytes);
  2864. if (ret)
  2865. ret = setup_cluster_bitmap(block_group, cluster, &bitmaps,
  2866. offset, bytes + empty_size,
  2867. cont1_bytes, min_bytes);
  2868. /* Clear our temporary list */
  2869. list_for_each_entry_safe(entry, tmp, &bitmaps, list)
  2870. list_del_init(&entry->list);
  2871. if (!ret) {
  2872. btrfs_get_block_group(block_group);
  2873. list_add_tail(&cluster->block_group_list,
  2874. &block_group->cluster_list);
  2875. cluster->block_group = block_group;
  2876. } else {
  2877. trace_btrfs_failed_cluster_setup(block_group);
  2878. }
  2879. out:
  2880. spin_unlock(&cluster->lock);
  2881. spin_unlock(&ctl->tree_lock);
  2882. return ret;
  2883. }
  2884. /*
  2885. * simple code to zero out a cluster
  2886. */
  2887. void btrfs_init_free_cluster(struct btrfs_free_cluster *cluster)
  2888. {
  2889. spin_lock_init(&cluster->lock);
  2890. spin_lock_init(&cluster->refill_lock);
  2891. cluster->root = RB_ROOT;
  2892. cluster->max_size = 0;
  2893. cluster->fragmented = false;
  2894. INIT_LIST_HEAD(&cluster->block_group_list);
  2895. cluster->block_group = NULL;
  2896. }
  2897. static int do_trimming(struct btrfs_block_group *block_group,
  2898. u64 *total_trimmed, u64 start, u64 bytes,
  2899. u64 reserved_start, u64 reserved_bytes,
  2900. enum btrfs_trim_state reserved_trim_state,
  2901. struct btrfs_trim_range *trim_entry)
  2902. {
  2903. struct btrfs_space_info *space_info = block_group->space_info;
  2904. struct btrfs_fs_info *fs_info = block_group->fs_info;
  2905. struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
  2906. int ret;
  2907. int update = 0;
  2908. const u64 end = start + bytes;
  2909. const u64 reserved_end = reserved_start + reserved_bytes;
  2910. enum btrfs_trim_state trim_state = BTRFS_TRIM_STATE_UNTRIMMED;
  2911. u64 trimmed = 0;
  2912. spin_lock(&space_info->lock);
  2913. spin_lock(&block_group->lock);
  2914. if (!block_group->ro) {
  2915. block_group->reserved += reserved_bytes;
  2916. space_info->bytes_reserved += reserved_bytes;
  2917. update = 1;
  2918. }
  2919. spin_unlock(&block_group->lock);
  2920. spin_unlock(&space_info->lock);
  2921. ret = btrfs_discard_extent(fs_info, start, bytes, &trimmed);
  2922. if (!ret) {
  2923. *total_trimmed += trimmed;
  2924. trim_state = BTRFS_TRIM_STATE_TRIMMED;
  2925. }
  2926. mutex_lock(&ctl->cache_writeout_mutex);
  2927. if (reserved_start < start)
  2928. __btrfs_add_free_space(fs_info, ctl, reserved_start,
  2929. start - reserved_start,
  2930. reserved_trim_state);
  2931. if (start + bytes < reserved_start + reserved_bytes)
  2932. __btrfs_add_free_space(fs_info, ctl, end, reserved_end - end,
  2933. reserved_trim_state);
  2934. __btrfs_add_free_space(fs_info, ctl, start, bytes, trim_state);
  2935. list_del(&trim_entry->list);
  2936. mutex_unlock(&ctl->cache_writeout_mutex);
  2937. if (update) {
  2938. spin_lock(&space_info->lock);
  2939. spin_lock(&block_group->lock);
  2940. if (block_group->ro)
  2941. space_info->bytes_readonly += reserved_bytes;
  2942. block_group->reserved -= reserved_bytes;
  2943. space_info->bytes_reserved -= reserved_bytes;
  2944. spin_unlock(&block_group->lock);
  2945. spin_unlock(&space_info->lock);
  2946. }
  2947. return ret;
  2948. }
  2949. /*
  2950. * If @async is set, then we will trim 1 region and return.
  2951. */
  2952. static int trim_no_bitmap(struct btrfs_block_group *block_group,
  2953. u64 *total_trimmed, u64 start, u64 end, u64 minlen,
  2954. bool async)
  2955. {
  2956. struct btrfs_discard_ctl *discard_ctl =
  2957. &block_group->fs_info->discard_ctl;
  2958. struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
  2959. struct btrfs_free_space *entry;
  2960. struct rb_node *node;
  2961. int ret = 0;
  2962. u64 extent_start;
  2963. u64 extent_bytes;
  2964. enum btrfs_trim_state extent_trim_state;
  2965. u64 bytes;
  2966. const u64 max_discard_size = READ_ONCE(discard_ctl->max_discard_size);
  2967. while (start < end) {
  2968. struct btrfs_trim_range trim_entry;
  2969. mutex_lock(&ctl->cache_writeout_mutex);
  2970. spin_lock(&ctl->tree_lock);
  2971. if (ctl->free_space < minlen)
  2972. goto out_unlock;
  2973. entry = tree_search_offset(ctl, start, 0, 1);
  2974. if (!entry)
  2975. goto out_unlock;
  2976. /* Skip bitmaps and if async, already trimmed entries */
  2977. while (entry->bitmap ||
  2978. (async && btrfs_free_space_trimmed(entry))) {
  2979. node = rb_next(&entry->offset_index);
  2980. if (!node)
  2981. goto out_unlock;
  2982. entry = rb_entry(node, struct btrfs_free_space,
  2983. offset_index);
  2984. }
  2985. if (entry->offset >= end)
  2986. goto out_unlock;
  2987. extent_start = entry->offset;
  2988. extent_bytes = entry->bytes;
  2989. extent_trim_state = entry->trim_state;
  2990. if (async) {
  2991. start = entry->offset;
  2992. bytes = entry->bytes;
  2993. if (bytes < minlen) {
  2994. spin_unlock(&ctl->tree_lock);
  2995. mutex_unlock(&ctl->cache_writeout_mutex);
  2996. goto next;
  2997. }
  2998. unlink_free_space(ctl, entry);
  2999. /*
  3000. * Let bytes = BTRFS_MAX_DISCARD_SIZE + X.
  3001. * If X < BTRFS_ASYNC_DISCARD_MIN_FILTER, we won't trim
  3002. * X when we come back around. So trim it now.
  3003. */
  3004. if (max_discard_size &&
  3005. bytes >= (max_discard_size +
  3006. BTRFS_ASYNC_DISCARD_MIN_FILTER)) {
  3007. bytes = max_discard_size;
  3008. extent_bytes = max_discard_size;
  3009. entry->offset += max_discard_size;
  3010. entry->bytes -= max_discard_size;
  3011. link_free_space(ctl, entry);
  3012. } else {
  3013. kmem_cache_free(btrfs_free_space_cachep, entry);
  3014. }
  3015. } else {
  3016. start = max(start, extent_start);
  3017. bytes = min(extent_start + extent_bytes, end) - start;
  3018. if (bytes < minlen) {
  3019. spin_unlock(&ctl->tree_lock);
  3020. mutex_unlock(&ctl->cache_writeout_mutex);
  3021. goto next;
  3022. }
  3023. unlink_free_space(ctl, entry);
  3024. kmem_cache_free(btrfs_free_space_cachep, entry);
  3025. }
  3026. spin_unlock(&ctl->tree_lock);
  3027. trim_entry.start = extent_start;
  3028. trim_entry.bytes = extent_bytes;
  3029. list_add_tail(&trim_entry.list, &ctl->trimming_ranges);
  3030. mutex_unlock(&ctl->cache_writeout_mutex);
  3031. ret = do_trimming(block_group, total_trimmed, start, bytes,
  3032. extent_start, extent_bytes, extent_trim_state,
  3033. &trim_entry);
  3034. if (ret) {
  3035. block_group->discard_cursor = start + bytes;
  3036. break;
  3037. }
  3038. next:
  3039. start += bytes;
  3040. block_group->discard_cursor = start;
  3041. if (async && *total_trimmed)
  3042. break;
  3043. if (fatal_signal_pending(current)) {
  3044. ret = -ERESTARTSYS;
  3045. break;
  3046. }
  3047. cond_resched();
  3048. }
  3049. return ret;
  3050. out_unlock:
  3051. block_group->discard_cursor = btrfs_block_group_end(block_group);
  3052. spin_unlock(&ctl->tree_lock);
  3053. mutex_unlock(&ctl->cache_writeout_mutex);
  3054. return ret;
  3055. }
  3056. /*
  3057. * If we break out of trimming a bitmap prematurely, we should reset the
  3058. * trimming bit. In a rather contrieved case, it's possible to race here so
  3059. * reset the state to BTRFS_TRIM_STATE_UNTRIMMED.
  3060. *
  3061. * start = start of bitmap
  3062. * end = near end of bitmap
  3063. *
  3064. * Thread 1: Thread 2:
  3065. * trim_bitmaps(start)
  3066. * trim_bitmaps(end)
  3067. * end_trimming_bitmap()
  3068. * reset_trimming_bitmap()
  3069. */
  3070. static void reset_trimming_bitmap(struct btrfs_free_space_ctl *ctl, u64 offset)
  3071. {
  3072. struct btrfs_free_space *entry;
  3073. spin_lock(&ctl->tree_lock);
  3074. entry = tree_search_offset(ctl, offset, 1, 0);
  3075. if (entry) {
  3076. if (btrfs_free_space_trimmed(entry)) {
  3077. ctl->discardable_extents[BTRFS_STAT_CURR] +=
  3078. entry->bitmap_extents;
  3079. ctl->discardable_bytes[BTRFS_STAT_CURR] += entry->bytes;
  3080. }
  3081. entry->trim_state = BTRFS_TRIM_STATE_UNTRIMMED;
  3082. }
  3083. spin_unlock(&ctl->tree_lock);
  3084. }
  3085. static void end_trimming_bitmap(struct btrfs_free_space_ctl *ctl,
  3086. struct btrfs_free_space *entry)
  3087. {
  3088. if (btrfs_free_space_trimming_bitmap(entry)) {
  3089. entry->trim_state = BTRFS_TRIM_STATE_TRIMMED;
  3090. ctl->discardable_extents[BTRFS_STAT_CURR] -=
  3091. entry->bitmap_extents;
  3092. ctl->discardable_bytes[BTRFS_STAT_CURR] -= entry->bytes;
  3093. }
  3094. }
  3095. /*
  3096. * If @async is set, then we will trim 1 region and return.
  3097. */
  3098. static int trim_bitmaps(struct btrfs_block_group *block_group,
  3099. u64 *total_trimmed, u64 start, u64 end, u64 minlen,
  3100. u64 maxlen, bool async)
  3101. {
  3102. struct btrfs_discard_ctl *discard_ctl =
  3103. &block_group->fs_info->discard_ctl;
  3104. struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
  3105. struct btrfs_free_space *entry;
  3106. int ret = 0;
  3107. int ret2;
  3108. u64 bytes;
  3109. u64 offset = offset_to_bitmap(ctl, start);
  3110. const u64 max_discard_size = READ_ONCE(discard_ctl->max_discard_size);
  3111. while (offset < end) {
  3112. bool next_bitmap = false;
  3113. struct btrfs_trim_range trim_entry;
  3114. mutex_lock(&ctl->cache_writeout_mutex);
  3115. spin_lock(&ctl->tree_lock);
  3116. if (ctl->free_space < minlen) {
  3117. block_group->discard_cursor =
  3118. btrfs_block_group_end(block_group);
  3119. spin_unlock(&ctl->tree_lock);
  3120. mutex_unlock(&ctl->cache_writeout_mutex);
  3121. break;
  3122. }
  3123. entry = tree_search_offset(ctl, offset, 1, 0);
  3124. /*
  3125. * Bitmaps are marked trimmed lossily now to prevent constant
  3126. * discarding of the same bitmap (the reason why we are bound
  3127. * by the filters). So, retrim the block group bitmaps when we
  3128. * are preparing to punt to the unused_bgs list. This uses
  3129. * @minlen to determine if we are in BTRFS_DISCARD_INDEX_UNUSED
  3130. * which is the only discard index which sets minlen to 0.
  3131. */
  3132. if (!entry || (async && minlen && start == offset &&
  3133. btrfs_free_space_trimmed(entry))) {
  3134. spin_unlock(&ctl->tree_lock);
  3135. mutex_unlock(&ctl->cache_writeout_mutex);
  3136. next_bitmap = true;
  3137. goto next;
  3138. }
  3139. /*
  3140. * Async discard bitmap trimming begins at by setting the start
  3141. * to be key.objectid and the offset_to_bitmap() aligns to the
  3142. * start of the bitmap. This lets us know we are fully
  3143. * scanning the bitmap rather than only some portion of it.
  3144. */
  3145. if (start == offset)
  3146. entry->trim_state = BTRFS_TRIM_STATE_TRIMMING;
  3147. bytes = minlen;
  3148. ret2 = search_bitmap(ctl, entry, &start, &bytes, false);
  3149. if (ret2 || start >= end) {
  3150. /*
  3151. * We lossily consider a bitmap trimmed if we only skip
  3152. * over regions <= BTRFS_ASYNC_DISCARD_MIN_FILTER.
  3153. */
  3154. if (ret2 && minlen <= BTRFS_ASYNC_DISCARD_MIN_FILTER)
  3155. end_trimming_bitmap(ctl, entry);
  3156. else
  3157. entry->trim_state = BTRFS_TRIM_STATE_UNTRIMMED;
  3158. spin_unlock(&ctl->tree_lock);
  3159. mutex_unlock(&ctl->cache_writeout_mutex);
  3160. next_bitmap = true;
  3161. goto next;
  3162. }
  3163. /*
  3164. * We already trimmed a region, but are using the locking above
  3165. * to reset the trim_state.
  3166. */
  3167. if (async && *total_trimmed) {
  3168. spin_unlock(&ctl->tree_lock);
  3169. mutex_unlock(&ctl->cache_writeout_mutex);
  3170. goto out;
  3171. }
  3172. bytes = min(bytes, end - start);
  3173. if (bytes < minlen || (async && maxlen && bytes > maxlen)) {
  3174. spin_unlock(&ctl->tree_lock);
  3175. mutex_unlock(&ctl->cache_writeout_mutex);
  3176. goto next;
  3177. }
  3178. /*
  3179. * Let bytes = BTRFS_MAX_DISCARD_SIZE + X.
  3180. * If X < @minlen, we won't trim X when we come back around.
  3181. * So trim it now. We differ here from trimming extents as we
  3182. * don't keep individual state per bit.
  3183. */
  3184. if (async &&
  3185. max_discard_size &&
  3186. bytes > (max_discard_size + minlen))
  3187. bytes = max_discard_size;
  3188. bitmap_clear_bits(ctl, entry, start, bytes);
  3189. if (entry->bytes == 0)
  3190. free_bitmap(ctl, entry);
  3191. spin_unlock(&ctl->tree_lock);
  3192. trim_entry.start = start;
  3193. trim_entry.bytes = bytes;
  3194. list_add_tail(&trim_entry.list, &ctl->trimming_ranges);
  3195. mutex_unlock(&ctl->cache_writeout_mutex);
  3196. ret = do_trimming(block_group, total_trimmed, start, bytes,
  3197. start, bytes, 0, &trim_entry);
  3198. if (ret) {
  3199. reset_trimming_bitmap(ctl, offset);
  3200. block_group->discard_cursor =
  3201. btrfs_block_group_end(block_group);
  3202. break;
  3203. }
  3204. next:
  3205. if (next_bitmap) {
  3206. offset += BITS_PER_BITMAP * ctl->unit;
  3207. start = offset;
  3208. } else {
  3209. start += bytes;
  3210. }
  3211. block_group->discard_cursor = start;
  3212. if (fatal_signal_pending(current)) {
  3213. if (start != offset)
  3214. reset_trimming_bitmap(ctl, offset);
  3215. ret = -ERESTARTSYS;
  3216. break;
  3217. }
  3218. cond_resched();
  3219. }
  3220. if (offset >= end)
  3221. block_group->discard_cursor = end;
  3222. out:
  3223. return ret;
  3224. }
  3225. int btrfs_trim_block_group(struct btrfs_block_group *block_group,
  3226. u64 *trimmed, u64 start, u64 end, u64 minlen)
  3227. {
  3228. struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
  3229. int ret;
  3230. u64 rem = 0;
  3231. *trimmed = 0;
  3232. spin_lock(&block_group->lock);
  3233. if (block_group->removed) {
  3234. spin_unlock(&block_group->lock);
  3235. return 0;
  3236. }
  3237. btrfs_freeze_block_group(block_group);
  3238. spin_unlock(&block_group->lock);
  3239. ret = trim_no_bitmap(block_group, trimmed, start, end, minlen, false);
  3240. if (ret)
  3241. goto out;
  3242. ret = trim_bitmaps(block_group, trimmed, start, end, minlen, 0, false);
  3243. div64_u64_rem(end, BITS_PER_BITMAP * ctl->unit, &rem);
  3244. /* If we ended in the middle of a bitmap, reset the trimming flag */
  3245. if (rem)
  3246. reset_trimming_bitmap(ctl, offset_to_bitmap(ctl, end));
  3247. out:
  3248. btrfs_unfreeze_block_group(block_group);
  3249. return ret;
  3250. }
  3251. int btrfs_trim_block_group_extents(struct btrfs_block_group *block_group,
  3252. u64 *trimmed, u64 start, u64 end, u64 minlen,
  3253. bool async)
  3254. {
  3255. int ret;
  3256. *trimmed = 0;
  3257. spin_lock(&block_group->lock);
  3258. if (block_group->removed) {
  3259. spin_unlock(&block_group->lock);
  3260. return 0;
  3261. }
  3262. btrfs_freeze_block_group(block_group);
  3263. spin_unlock(&block_group->lock);
  3264. ret = trim_no_bitmap(block_group, trimmed, start, end, minlen, async);
  3265. btrfs_unfreeze_block_group(block_group);
  3266. return ret;
  3267. }
  3268. int btrfs_trim_block_group_bitmaps(struct btrfs_block_group *block_group,
  3269. u64 *trimmed, u64 start, u64 end, u64 minlen,
  3270. u64 maxlen, bool async)
  3271. {
  3272. int ret;
  3273. *trimmed = 0;
  3274. spin_lock(&block_group->lock);
  3275. if (block_group->removed) {
  3276. spin_unlock(&block_group->lock);
  3277. return 0;
  3278. }
  3279. btrfs_freeze_block_group(block_group);
  3280. spin_unlock(&block_group->lock);
  3281. ret = trim_bitmaps(block_group, trimmed, start, end, minlen, maxlen,
  3282. async);
  3283. btrfs_unfreeze_block_group(block_group);
  3284. return ret;
  3285. }
  3286. /*
  3287. * Find the left-most item in the cache tree, and then return the
  3288. * smallest inode number in the item.
  3289. *
  3290. * Note: the returned inode number may not be the smallest one in
  3291. * the tree, if the left-most item is a bitmap.
  3292. */
  3293. u64 btrfs_find_ino_for_alloc(struct btrfs_root *fs_root)
  3294. {
  3295. struct btrfs_free_space_ctl *ctl = fs_root->free_ino_ctl;
  3296. struct btrfs_free_space *entry = NULL;
  3297. u64 ino = 0;
  3298. spin_lock(&ctl->tree_lock);
  3299. if (RB_EMPTY_ROOT(&ctl->free_space_offset))
  3300. goto out;
  3301. entry = rb_entry(rb_first(&ctl->free_space_offset),
  3302. struct btrfs_free_space, offset_index);
  3303. if (!entry->bitmap) {
  3304. ino = entry->offset;
  3305. unlink_free_space(ctl, entry);
  3306. entry->offset++;
  3307. entry->bytes--;
  3308. if (!entry->bytes)
  3309. kmem_cache_free(btrfs_free_space_cachep, entry);
  3310. else
  3311. link_free_space(ctl, entry);
  3312. } else {
  3313. u64 offset = 0;
  3314. u64 count = 1;
  3315. int ret;
  3316. ret = search_bitmap(ctl, entry, &offset, &count, true);
  3317. /* Logic error; Should be empty if it can't find anything */
  3318. ASSERT(!ret);
  3319. ino = offset;
  3320. bitmap_clear_bits(ctl, entry, offset, 1);
  3321. if (entry->bytes == 0)
  3322. free_bitmap(ctl, entry);
  3323. }
  3324. out:
  3325. spin_unlock(&ctl->tree_lock);
  3326. return ino;
  3327. }
  3328. struct inode *lookup_free_ino_inode(struct btrfs_root *root,
  3329. struct btrfs_path *path)
  3330. {
  3331. struct inode *inode = NULL;
  3332. spin_lock(&root->ino_cache_lock);
  3333. if (root->ino_cache_inode)
  3334. inode = igrab(root->ino_cache_inode);
  3335. spin_unlock(&root->ino_cache_lock);
  3336. if (inode)
  3337. return inode;
  3338. inode = __lookup_free_space_inode(root, path, 0);
  3339. if (IS_ERR(inode))
  3340. return inode;
  3341. spin_lock(&root->ino_cache_lock);
  3342. if (!btrfs_fs_closing(root->fs_info))
  3343. root->ino_cache_inode = igrab(inode);
  3344. spin_unlock(&root->ino_cache_lock);
  3345. return inode;
  3346. }
  3347. int create_free_ino_inode(struct btrfs_root *root,
  3348. struct btrfs_trans_handle *trans,
  3349. struct btrfs_path *path)
  3350. {
  3351. return __create_free_space_inode(root, trans, path,
  3352. BTRFS_FREE_INO_OBJECTID, 0);
  3353. }
  3354. int load_free_ino_cache(struct btrfs_fs_info *fs_info, struct btrfs_root *root)
  3355. {
  3356. struct btrfs_free_space_ctl *ctl = root->free_ino_ctl;
  3357. struct btrfs_path *path;
  3358. struct inode *inode;
  3359. int ret = 0;
  3360. u64 root_gen = btrfs_root_generation(&root->root_item);
  3361. if (!btrfs_test_opt(fs_info, INODE_MAP_CACHE))
  3362. return 0;
  3363. /*
  3364. * If we're unmounting then just return, since this does a search on the
  3365. * normal root and not the commit root and we could deadlock.
  3366. */
  3367. if (btrfs_fs_closing(fs_info))
  3368. return 0;
  3369. path = btrfs_alloc_path();
  3370. if (!path)
  3371. return 0;
  3372. inode = lookup_free_ino_inode(root, path);
  3373. if (IS_ERR(inode))
  3374. goto out;
  3375. if (root_gen != BTRFS_I(inode)->generation)
  3376. goto out_put;
  3377. ret = __load_free_space_cache(root, inode, ctl, path, 0);
  3378. if (ret < 0)
  3379. btrfs_err(fs_info,
  3380. "failed to load free ino cache for root %llu",
  3381. root->root_key.objectid);
  3382. out_put:
  3383. iput(inode);
  3384. out:
  3385. btrfs_free_path(path);
  3386. return ret;
  3387. }
  3388. int btrfs_write_out_ino_cache(struct btrfs_root *root,
  3389. struct btrfs_trans_handle *trans,
  3390. struct btrfs_path *path,
  3391. struct inode *inode)
  3392. {
  3393. struct btrfs_fs_info *fs_info = root->fs_info;
  3394. struct btrfs_free_space_ctl *ctl = root->free_ino_ctl;
  3395. int ret;
  3396. struct btrfs_io_ctl io_ctl;
  3397. bool release_metadata = true;
  3398. if (!btrfs_test_opt(fs_info, INODE_MAP_CACHE))
  3399. return 0;
  3400. memset(&io_ctl, 0, sizeof(io_ctl));
  3401. ret = __btrfs_write_out_cache(root, inode, ctl, NULL, &io_ctl, trans);
  3402. if (!ret) {
  3403. /*
  3404. * At this point writepages() didn't error out, so our metadata
  3405. * reservation is released when the writeback finishes, at
  3406. * inode.c:btrfs_finish_ordered_io(), regardless of it finishing
  3407. * with or without an error.
  3408. */
  3409. release_metadata = false;
  3410. ret = btrfs_wait_cache_io_root(root, trans, &io_ctl, path);
  3411. }
  3412. if (ret) {
  3413. if (release_metadata)
  3414. btrfs_delalloc_release_metadata(BTRFS_I(inode),
  3415. inode->i_size, true);
  3416. btrfs_debug(fs_info,
  3417. "failed to write free ino cache for root %llu error %d",
  3418. root->root_key.objectid, ret);
  3419. }
  3420. return ret;
  3421. }
  3422. #ifdef CONFIG_BTRFS_FS_RUN_SANITY_TESTS
  3423. /*
  3424. * Use this if you need to make a bitmap or extent entry specifically, it
  3425. * doesn't do any of the merging that add_free_space does, this acts a lot like
  3426. * how the free space cache loading stuff works, so you can get really weird
  3427. * configurations.
  3428. */
  3429. int test_add_free_space_entry(struct btrfs_block_group *cache,
  3430. u64 offset, u64 bytes, bool bitmap)
  3431. {
  3432. struct btrfs_free_space_ctl *ctl = cache->free_space_ctl;
  3433. struct btrfs_free_space *info = NULL, *bitmap_info;
  3434. void *map = NULL;
  3435. enum btrfs_trim_state trim_state = BTRFS_TRIM_STATE_TRIMMED;
  3436. u64 bytes_added;
  3437. int ret;
  3438. again:
  3439. if (!info) {
  3440. info = kmem_cache_zalloc(btrfs_free_space_cachep, GFP_NOFS);
  3441. if (!info)
  3442. return -ENOMEM;
  3443. }
  3444. if (!bitmap) {
  3445. spin_lock(&ctl->tree_lock);
  3446. info->offset = offset;
  3447. info->bytes = bytes;
  3448. info->max_extent_size = 0;
  3449. ret = link_free_space(ctl, info);
  3450. spin_unlock(&ctl->tree_lock);
  3451. if (ret)
  3452. kmem_cache_free(btrfs_free_space_cachep, info);
  3453. return ret;
  3454. }
  3455. if (!map) {
  3456. map = kmem_cache_zalloc(btrfs_free_space_bitmap_cachep, GFP_NOFS);
  3457. if (!map) {
  3458. kmem_cache_free(btrfs_free_space_cachep, info);
  3459. return -ENOMEM;
  3460. }
  3461. }
  3462. spin_lock(&ctl->tree_lock);
  3463. bitmap_info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset),
  3464. 1, 0);
  3465. if (!bitmap_info) {
  3466. info->bitmap = map;
  3467. map = NULL;
  3468. add_new_bitmap(ctl, info, offset);
  3469. bitmap_info = info;
  3470. info = NULL;
  3471. }
  3472. bytes_added = add_bytes_to_bitmap(ctl, bitmap_info, offset, bytes,
  3473. trim_state);
  3474. bytes -= bytes_added;
  3475. offset += bytes_added;
  3476. spin_unlock(&ctl->tree_lock);
  3477. if (bytes)
  3478. goto again;
  3479. if (info)
  3480. kmem_cache_free(btrfs_free_space_cachep, info);
  3481. if (map)
  3482. kmem_cache_free(btrfs_free_space_bitmap_cachep, map);
  3483. return 0;
  3484. }
  3485. /*
  3486. * Checks to see if the given range is in the free space cache. This is really
  3487. * just used to check the absence of space, so if there is free space in the
  3488. * range at all we will return 1.
  3489. */
  3490. int test_check_exists(struct btrfs_block_group *cache,
  3491. u64 offset, u64 bytes)
  3492. {
  3493. struct btrfs_free_space_ctl *ctl = cache->free_space_ctl;
  3494. struct btrfs_free_space *info;
  3495. int ret = 0;
  3496. spin_lock(&ctl->tree_lock);
  3497. info = tree_search_offset(ctl, offset, 0, 0);
  3498. if (!info) {
  3499. info = tree_search_offset(ctl, offset_to_bitmap(ctl, offset),
  3500. 1, 0);
  3501. if (!info)
  3502. goto out;
  3503. }
  3504. have_info:
  3505. if (info->bitmap) {
  3506. u64 bit_off, bit_bytes;
  3507. struct rb_node *n;
  3508. struct btrfs_free_space *tmp;
  3509. bit_off = offset;
  3510. bit_bytes = ctl->unit;
  3511. ret = search_bitmap(ctl, info, &bit_off, &bit_bytes, false);
  3512. if (!ret) {
  3513. if (bit_off == offset) {
  3514. ret = 1;
  3515. goto out;
  3516. } else if (bit_off > offset &&
  3517. offset + bytes > bit_off) {
  3518. ret = 1;
  3519. goto out;
  3520. }
  3521. }
  3522. n = rb_prev(&info->offset_index);
  3523. while (n) {
  3524. tmp = rb_entry(n, struct btrfs_free_space,
  3525. offset_index);
  3526. if (tmp->offset + tmp->bytes < offset)
  3527. break;
  3528. if (offset + bytes < tmp->offset) {
  3529. n = rb_prev(&tmp->offset_index);
  3530. continue;
  3531. }
  3532. info = tmp;
  3533. goto have_info;
  3534. }
  3535. n = rb_next(&info->offset_index);
  3536. while (n) {
  3537. tmp = rb_entry(n, struct btrfs_free_space,
  3538. offset_index);
  3539. if (offset + bytes < tmp->offset)
  3540. break;
  3541. if (tmp->offset + tmp->bytes < offset) {
  3542. n = rb_next(&tmp->offset_index);
  3543. continue;
  3544. }
  3545. info = tmp;
  3546. goto have_info;
  3547. }
  3548. ret = 0;
  3549. goto out;
  3550. }
  3551. if (info->offset == offset) {
  3552. ret = 1;
  3553. goto out;
  3554. }
  3555. if (offset > info->offset && offset < info->offset + info->bytes)
  3556. ret = 1;
  3557. out:
  3558. spin_unlock(&ctl->tree_lock);
  3559. return ret;
  3560. }
  3561. #endif /* CONFIG_BTRFS_FS_RUN_SANITY_TESTS */