extent-tree.c 73 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700170117021703170417051706170717081709171017111712171317141715171617171718171917201721172217231724172517261727172817291730173117321733173417351736173717381739174017411742174317441745174617471748174917501751175217531754175517561757175817591760176117621763176417651766176717681769177017711772177317741775177617771778177917801781178217831784178517861787178817891790179117921793179417951796179717981799180018011802180318041805180618071808180918101811181218131814181518161817181818191820182118221823182418251826182718281829183018311832183318341835183618371838183918401841184218431844184518461847184818491850185118521853185418551856185718581859186018611862186318641865186618671868186918701871187218731874187518761877187818791880188118821883188418851886188718881889189018911892189318941895189618971898189919001901190219031904190519061907190819091910191119121913191419151916191719181919192019211922192319241925192619271928192919301931193219331934193519361937193819391940194119421943194419451946194719481949195019511952195319541955195619571958195919601961196219631964196519661967196819691970197119721973197419751976197719781979198019811982198319841985198619871988198919901991199219931994199519961997199819992000200120022003200420052006200720082009201020112012201320142015201620172018201920202021202220232024202520262027202820292030203120322033203420352036203720382039204020412042204320442045204620472048204920502051205220532054205520562057205820592060206120622063206420652066206720682069207020712072207320742075207620772078207920802081208220832084208520862087208820892090209120922093209420952096209720982099210021012102210321042105210621072108210921102111211221132114211521162117211821192120212121222123212421252126212721282129213021312132213321342135213621372138213921402141214221432144214521462147214821492150215121522153215421552156215721582159216021612162216321642165216621672168216921702171217221732174217521762177217821792180218121822183218421852186218721882189219021912192219321942195219621972198219922002201220222032204220522062207220822092210221122122213221422152216221722182219222022212222222322242225222622272228222922302231223222332234223522362237223822392240224122422243224422452246224722482249225022512252225322542255225622572258225922602261226222632264226522662267226822692270227122722273227422752276227722782279228022812282228322842285228622872288228922902291229222932294229522962297229822992300230123022303230423052306230723082309231023112312231323142315231623172318231923202321232223232324232523262327232823292330233123322333233423352336233723382339234023412342234323442345234623472348234923502351235223532354235523562357235823592360236123622363236423652366236723682369237023712372237323742375237623772378237923802381238223832384238523862387238823892390239123922393239423952396239723982399240024012402240324042405240624072408240924102411241224132414241524162417241824192420242124222423242424252426242724282429243024312432243324342435243624372438243924402441244224432444244524462447244824492450245124522453245424552456245724582459246024612462246324642465246624672468246924702471247224732474247524762477247824792480248124822483248424852486248724882489249024912492249324942495249624972498249925002501250225032504250525062507250825092510251125122513251425152516251725182519252025212522252325242525252625272528252925302531253225332534253525362537253825392540254125422543254425452546254725482549255025512552255325542555255625572558255925602561256225632564256525662567256825692570257125722573257425752576257725782579258025812582258325842585258625872588258925902591259225932594259525962597259825992600260126022603260426052606260726082609261026112612261326142615261626172618261926202621262226232624262526262627262826292630263126322633263426352636263726382639264026412642264326442645264626472648264926502651265226532654265526562657265826592660266126622663266426652666266726682669267026712672267326742675267626772678267926802681268226832684268526862687268826892690269126922693269426952696269726982699270027012702270327042705270627072708270927102711271227132714271527162717271827192720272127222723272427252726272727282729273027312732273327342735273627372738273927402741274227432744274527462747274827492750275127522753275427552756275727582759276027612762276327642765276627672768276927702771277227732774277527762777277827792780278127822783278427852786278727882789279027912792279327942795279627972798279928002801280228032804280528062807280828092810281128122813281428152816281728182819282028212822282328242825282628272828282928302831
  1. /*
  2. * Copyright (C) 2007 Oracle. All rights reserved.
  3. *
  4. * This program is free software; you can redistribute it and/or
  5. * modify it under the terms of the GNU General Public
  6. * License v2 as published by the Free Software Foundation.
  7. *
  8. * This program is distributed in the hope that it will be useful,
  9. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  11. * General Public License for more details.
  12. *
  13. * You should have received a copy of the GNU General Public
  14. * License along with this program; if not, write to the
  15. * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  16. * Boston, MA 021110-1307, USA.
  17. */
  18. #include <linux/sched.h>
  19. #include <linux/pagemap.h>
  20. #include "hash.h"
  21. #include "crc32c.h"
  22. #include "ctree.h"
  23. #include "disk-io.h"
  24. #include "print-tree.h"
  25. #include "transaction.h"
  26. #include "volumes.h"
  27. #define BLOCK_GROUP_DATA EXTENT_WRITEBACK
  28. #define BLOCK_GROUP_METADATA EXTENT_UPTODATE
  29. #define BLOCK_GROUP_SYSTEM EXTENT_NEW
  30. #define BLOCK_GROUP_DIRTY EXTENT_DIRTY
  31. static int finish_current_insert(struct btrfs_trans_handle *trans, struct
  32. btrfs_root *extent_root);
  33. static int del_pending_extents(struct btrfs_trans_handle *trans, struct
  34. btrfs_root *extent_root);
  35. int btrfs_make_block_group(struct btrfs_trans_handle *trans,
  36. struct btrfs_root *root, u64 bytes_used,
  37. u64 type, u64 chunk_tree, u64 chunk_objectid,
  38. u64 size);
  39. static int cache_block_group(struct btrfs_root *root,
  40. struct btrfs_block_group_cache *block_group)
  41. {
  42. struct btrfs_path *path;
  43. int ret;
  44. struct btrfs_key key;
  45. struct extent_buffer *leaf;
  46. struct extent_io_tree *free_space_cache;
  47. int slot;
  48. u64 last = 0;
  49. u64 hole_size;
  50. u64 first_free;
  51. int found = 0;
  52. if (!block_group)
  53. return 0;
  54. root = root->fs_info->extent_root;
  55. free_space_cache = &root->fs_info->free_space_cache;
  56. if (block_group->cached)
  57. return 0;
  58. path = btrfs_alloc_path();
  59. if (!path)
  60. return -ENOMEM;
  61. path->reada = 2;
  62. first_free = block_group->key.objectid;
  63. key.objectid = block_group->key.objectid;
  64. key.offset = 0;
  65. btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
  66. ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
  67. if (ret < 0)
  68. return ret;
  69. ret = btrfs_previous_item(root, path, 0, BTRFS_EXTENT_ITEM_KEY);
  70. if (ret < 0)
  71. return ret;
  72. if (ret == 0) {
  73. leaf = path->nodes[0];
  74. btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
  75. if (key.objectid + key.offset > first_free)
  76. first_free = key.objectid + key.offset;
  77. }
  78. while(1) {
  79. leaf = path->nodes[0];
  80. slot = path->slots[0];
  81. if (slot >= btrfs_header_nritems(leaf)) {
  82. ret = btrfs_next_leaf(root, path);
  83. if (ret < 0)
  84. goto err;
  85. if (ret == 0) {
  86. continue;
  87. } else {
  88. break;
  89. }
  90. }
  91. btrfs_item_key_to_cpu(leaf, &key, slot);
  92. if (key.objectid < block_group->key.objectid) {
  93. goto next;
  94. }
  95. if (key.objectid >= block_group->key.objectid +
  96. block_group->key.offset) {
  97. break;
  98. }
  99. if (btrfs_key_type(&key) == BTRFS_EXTENT_ITEM_KEY) {
  100. if (!found) {
  101. last = first_free;
  102. found = 1;
  103. }
  104. if (key.objectid > last) {
  105. hole_size = key.objectid - last;
  106. set_extent_dirty(free_space_cache, last,
  107. last + hole_size - 1,
  108. GFP_NOFS);
  109. }
  110. last = key.objectid + key.offset;
  111. }
  112. next:
  113. path->slots[0]++;
  114. }
  115. if (!found)
  116. last = first_free;
  117. if (block_group->key.objectid +
  118. block_group->key.offset > last) {
  119. hole_size = block_group->key.objectid +
  120. block_group->key.offset - last;
  121. set_extent_dirty(free_space_cache, last,
  122. last + hole_size - 1, GFP_NOFS);
  123. }
  124. block_group->cached = 1;
  125. err:
  126. btrfs_free_path(path);
  127. return 0;
  128. }
  129. struct btrfs_block_group_cache *btrfs_lookup_block_group(struct
  130. btrfs_fs_info *info,
  131. u64 bytenr)
  132. {
  133. struct extent_io_tree *block_group_cache;
  134. struct btrfs_block_group_cache *block_group = NULL;
  135. u64 ptr;
  136. u64 start;
  137. u64 end;
  138. int ret;
  139. block_group_cache = &info->block_group_cache;
  140. ret = find_first_extent_bit(block_group_cache,
  141. bytenr, &start, &end,
  142. BLOCK_GROUP_DATA | BLOCK_GROUP_METADATA |
  143. BLOCK_GROUP_SYSTEM);
  144. if (ret) {
  145. return NULL;
  146. }
  147. ret = get_state_private(block_group_cache, start, &ptr);
  148. if (ret)
  149. return NULL;
  150. block_group = (struct btrfs_block_group_cache *)(unsigned long)ptr;
  151. if (block_group->key.objectid <= bytenr && bytenr <
  152. block_group->key.objectid + block_group->key.offset)
  153. return block_group;
  154. return NULL;
  155. }
  156. static int block_group_bits(struct btrfs_block_group_cache *cache, u64 bits)
  157. {
  158. return (cache->flags & bits) == bits;
  159. }
  160. static int noinline find_search_start(struct btrfs_root *root,
  161. struct btrfs_block_group_cache **cache_ret,
  162. u64 *start_ret, int num, int data)
  163. {
  164. int ret;
  165. struct btrfs_block_group_cache *cache = *cache_ret;
  166. struct extent_io_tree *free_space_cache;
  167. struct extent_state *state;
  168. u64 last;
  169. u64 start = 0;
  170. u64 cache_miss = 0;
  171. u64 total_fs_bytes;
  172. u64 search_start = *start_ret;
  173. int wrapped = 0;
  174. if (!cache)
  175. goto out;
  176. total_fs_bytes = btrfs_super_total_bytes(&root->fs_info->super_copy);
  177. free_space_cache = &root->fs_info->free_space_cache;
  178. again:
  179. ret = cache_block_group(root, cache);
  180. if (ret)
  181. goto out;
  182. last = max(search_start, cache->key.objectid);
  183. if (!block_group_bits(cache, data)) {
  184. goto new_group;
  185. }
  186. spin_lock_irq(&free_space_cache->lock);
  187. state = find_first_extent_bit_state(free_space_cache, last, EXTENT_DIRTY);
  188. while(1) {
  189. if (!state) {
  190. if (!cache_miss)
  191. cache_miss = last;
  192. spin_unlock_irq(&free_space_cache->lock);
  193. goto new_group;
  194. }
  195. start = max(last, state->start);
  196. last = state->end + 1;
  197. if (last - start < num) {
  198. if (last == cache->key.objectid + cache->key.offset)
  199. cache_miss = start;
  200. do {
  201. state = extent_state_next(state);
  202. } while(state && !(state->state & EXTENT_DIRTY));
  203. continue;
  204. }
  205. spin_unlock_irq(&free_space_cache->lock);
  206. if (start + num > cache->key.objectid + cache->key.offset)
  207. goto new_group;
  208. if (start + num > total_fs_bytes)
  209. goto new_group;
  210. if (!block_group_bits(cache, data)) {
  211. printk("block group bits don't match %Lu %d\n", cache->flags, data);
  212. }
  213. *start_ret = start;
  214. return 0;
  215. }
  216. out:
  217. cache = btrfs_lookup_block_group(root->fs_info, search_start);
  218. if (!cache) {
  219. printk("Unable to find block group for %Lu\n", search_start);
  220. WARN_ON(1);
  221. }
  222. return -ENOSPC;
  223. new_group:
  224. last = cache->key.objectid + cache->key.offset;
  225. wrapped:
  226. cache = btrfs_lookup_block_group(root->fs_info, last);
  227. if (!cache || cache->key.objectid >= total_fs_bytes) {
  228. no_cache:
  229. if (!wrapped) {
  230. wrapped = 1;
  231. last = search_start;
  232. goto wrapped;
  233. }
  234. goto out;
  235. }
  236. if (cache_miss && !cache->cached) {
  237. cache_block_group(root, cache);
  238. last = cache_miss;
  239. cache = btrfs_lookup_block_group(root->fs_info, last);
  240. }
  241. cache = btrfs_find_block_group(root, cache, last, data, 0);
  242. if (!cache)
  243. goto no_cache;
  244. *cache_ret = cache;
  245. cache_miss = 0;
  246. goto again;
  247. }
  248. static u64 div_factor(u64 num, int factor)
  249. {
  250. if (factor == 10)
  251. return num;
  252. num *= factor;
  253. do_div(num, 10);
  254. return num;
  255. }
  256. static int block_group_state_bits(u64 flags)
  257. {
  258. int bits = 0;
  259. if (flags & BTRFS_BLOCK_GROUP_DATA)
  260. bits |= BLOCK_GROUP_DATA;
  261. if (flags & BTRFS_BLOCK_GROUP_METADATA)
  262. bits |= BLOCK_GROUP_METADATA;
  263. if (flags & BTRFS_BLOCK_GROUP_SYSTEM)
  264. bits |= BLOCK_GROUP_SYSTEM;
  265. return bits;
  266. }
  267. struct btrfs_block_group_cache *btrfs_find_block_group(struct btrfs_root *root,
  268. struct btrfs_block_group_cache
  269. *hint, u64 search_start,
  270. int data, int owner)
  271. {
  272. struct btrfs_block_group_cache *cache;
  273. struct extent_io_tree *block_group_cache;
  274. struct btrfs_block_group_cache *found_group = NULL;
  275. struct btrfs_fs_info *info = root->fs_info;
  276. u64 used;
  277. u64 last = 0;
  278. u64 hint_last;
  279. u64 start;
  280. u64 end;
  281. u64 free_check;
  282. u64 ptr;
  283. u64 total_fs_bytes;
  284. int bit;
  285. int ret;
  286. int full_search = 0;
  287. int factor = 8;
  288. block_group_cache = &info->block_group_cache;
  289. total_fs_bytes = btrfs_super_total_bytes(&root->fs_info->super_copy);
  290. if (!owner)
  291. factor = 8;
  292. bit = block_group_state_bits(data);
  293. if (search_start && search_start < total_fs_bytes) {
  294. struct btrfs_block_group_cache *shint;
  295. shint = btrfs_lookup_block_group(info, search_start);
  296. if (shint && block_group_bits(shint, data)) {
  297. used = btrfs_block_group_used(&shint->item);
  298. if (used + shint->pinned <
  299. div_factor(shint->key.offset, factor)) {
  300. return shint;
  301. }
  302. }
  303. }
  304. if (hint && block_group_bits(hint, data) &&
  305. hint->key.objectid < total_fs_bytes) {
  306. used = btrfs_block_group_used(&hint->item);
  307. if (used + hint->pinned <
  308. div_factor(hint->key.offset, factor)) {
  309. return hint;
  310. }
  311. last = hint->key.objectid + hint->key.offset;
  312. hint_last = last;
  313. } else {
  314. if (hint)
  315. hint_last = max(hint->key.objectid, search_start);
  316. else
  317. hint_last = search_start;
  318. if (hint_last >= total_fs_bytes)
  319. hint_last = search_start;
  320. last = hint_last;
  321. }
  322. again:
  323. while(1) {
  324. ret = find_first_extent_bit(block_group_cache, last,
  325. &start, &end, bit);
  326. if (ret)
  327. break;
  328. ret = get_state_private(block_group_cache, start, &ptr);
  329. if (ret)
  330. break;
  331. cache = (struct btrfs_block_group_cache *)(unsigned long)ptr;
  332. last = cache->key.objectid + cache->key.offset;
  333. used = btrfs_block_group_used(&cache->item);
  334. if (cache->key.objectid > total_fs_bytes)
  335. break;
  336. if (block_group_bits(cache, data)) {
  337. if (full_search)
  338. free_check = cache->key.offset;
  339. else
  340. free_check = div_factor(cache->key.offset,
  341. factor);
  342. if (used + cache->pinned < free_check) {
  343. found_group = cache;
  344. goto found;
  345. }
  346. }
  347. cond_resched();
  348. }
  349. if (!full_search) {
  350. last = search_start;
  351. full_search = 1;
  352. goto again;
  353. }
  354. found:
  355. return found_group;
  356. }
  357. static u64 hash_extent_ref(u64 root_objectid, u64 ref_generation,
  358. u64 owner, u64 owner_offset)
  359. {
  360. u32 high_crc = ~(u32)0;
  361. u32 low_crc = ~(u32)0;
  362. __le64 lenum;
  363. lenum = cpu_to_le64(root_objectid);
  364. high_crc = btrfs_crc32c(high_crc, &lenum, sizeof(lenum));
  365. lenum = cpu_to_le64(ref_generation);
  366. low_crc = btrfs_crc32c(low_crc, &lenum, sizeof(lenum));
  367. if (owner >= BTRFS_FIRST_FREE_OBJECTID) {
  368. lenum = cpu_to_le64(owner);
  369. low_crc = btrfs_crc32c(low_crc, &lenum, sizeof(lenum));
  370. lenum = cpu_to_le64(owner_offset);
  371. low_crc = btrfs_crc32c(low_crc, &lenum, sizeof(lenum));
  372. }
  373. return ((u64)high_crc << 32) | (u64)low_crc;
  374. }
  375. static int match_extent_ref(struct extent_buffer *leaf,
  376. struct btrfs_extent_ref *disk_ref,
  377. struct btrfs_extent_ref *cpu_ref)
  378. {
  379. int ret;
  380. int len;
  381. if (cpu_ref->objectid)
  382. len = sizeof(*cpu_ref);
  383. else
  384. len = 2 * sizeof(u64);
  385. ret = memcmp_extent_buffer(leaf, cpu_ref, (unsigned long)disk_ref,
  386. len);
  387. return ret == 0;
  388. }
  389. static int noinline lookup_extent_backref(struct btrfs_trans_handle *trans,
  390. struct btrfs_root *root,
  391. struct btrfs_path *path, u64 bytenr,
  392. u64 root_objectid,
  393. u64 ref_generation, u64 owner,
  394. u64 owner_offset, int del)
  395. {
  396. u64 hash;
  397. struct btrfs_key key;
  398. struct btrfs_key found_key;
  399. struct btrfs_extent_ref ref;
  400. struct extent_buffer *leaf;
  401. struct btrfs_extent_ref *disk_ref;
  402. int ret;
  403. int ret2;
  404. btrfs_set_stack_ref_root(&ref, root_objectid);
  405. btrfs_set_stack_ref_generation(&ref, ref_generation);
  406. btrfs_set_stack_ref_objectid(&ref, owner);
  407. btrfs_set_stack_ref_offset(&ref, owner_offset);
  408. hash = hash_extent_ref(root_objectid, ref_generation, owner,
  409. owner_offset);
  410. key.offset = hash;
  411. key.objectid = bytenr;
  412. key.type = BTRFS_EXTENT_REF_KEY;
  413. while (1) {
  414. ret = btrfs_search_slot(trans, root, &key, path,
  415. del ? -1 : 0, del);
  416. if (ret < 0)
  417. goto out;
  418. leaf = path->nodes[0];
  419. if (ret != 0) {
  420. u32 nritems = btrfs_header_nritems(leaf);
  421. if (path->slots[0] >= nritems) {
  422. ret2 = btrfs_next_leaf(root, path);
  423. if (ret2)
  424. goto out;
  425. leaf = path->nodes[0];
  426. }
  427. btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
  428. if (found_key.objectid != bytenr ||
  429. found_key.type != BTRFS_EXTENT_REF_KEY)
  430. goto out;
  431. key.offset = found_key.offset;
  432. if (del) {
  433. btrfs_release_path(root, path);
  434. continue;
  435. }
  436. }
  437. disk_ref = btrfs_item_ptr(path->nodes[0],
  438. path->slots[0],
  439. struct btrfs_extent_ref);
  440. if (match_extent_ref(path->nodes[0], disk_ref, &ref)) {
  441. ret = 0;
  442. goto out;
  443. }
  444. btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
  445. key.offset = found_key.offset + 1;
  446. btrfs_release_path(root, path);
  447. }
  448. out:
  449. return ret;
  450. }
  451. /*
  452. * Back reference rules. Back refs have three main goals:
  453. *
  454. * 1) differentiate between all holders of references to an extent so that
  455. * when a reference is dropped we can make sure it was a valid reference
  456. * before freeing the extent.
  457. *
  458. * 2) Provide enough information to quickly find the holders of an extent
  459. * if we notice a given block is corrupted or bad.
  460. *
  461. * 3) Make it easy to migrate blocks for FS shrinking or storage pool
  462. * maintenance. This is actually the same as #2, but with a slightly
  463. * different use case.
  464. *
  465. * File extents can be referenced by:
  466. *
  467. * - multiple snapshots, subvolumes, or different generations in one subvol
  468. * - different files inside a single subvolume (in theory, not implemented yet)
  469. * - different offsets inside a file (bookend extents in file.c)
  470. *
  471. * The extent ref structure has fields for:
  472. *
  473. * - Objectid of the subvolume root
  474. * - Generation number of the tree holding the reference
  475. * - objectid of the file holding the reference
  476. * - offset in the file corresponding to the key holding the reference
  477. *
  478. * When a file extent is allocated the fields are filled in:
  479. * (root_key.objectid, trans->transid, inode objectid, offset in file)
  480. *
  481. * When a leaf is cow'd new references are added for every file extent found
  482. * in the leaf. It looks the same as the create case, but trans->transid
  483. * will be different when the block is cow'd.
  484. *
  485. * (root_key.objectid, trans->transid, inode objectid, offset in file)
  486. *
  487. * When a file extent is removed either during snapshot deletion or file
  488. * truncation, the corresponding back reference is found
  489. * by searching for:
  490. *
  491. * (btrfs_header_owner(leaf), btrfs_header_generation(leaf),
  492. * inode objectid, offset in file)
  493. *
  494. * Btree extents can be referenced by:
  495. *
  496. * - Different subvolumes
  497. * - Different generations of the same subvolume
  498. *
  499. * Storing sufficient information for a full reverse mapping of a btree
  500. * block would require storing the lowest key of the block in the backref,
  501. * and it would require updating that lowest key either before write out or
  502. * every time it changed. Instead, the objectid of the lowest key is stored
  503. * along with the level of the tree block. This provides a hint
  504. * about where in the btree the block can be found. Searches through the
  505. * btree only need to look for a pointer to that block, so they stop one
  506. * level higher than the level recorded in the backref.
  507. *
  508. * Some btrees do not do reference counting on their extents. These
  509. * include the extent tree and the tree of tree roots. Backrefs for these
  510. * trees always have a generation of zero.
  511. *
  512. * When a tree block is created, back references are inserted:
  513. *
  514. * (root->root_key.objectid, trans->transid or zero, level, lowest_key_objectid)
  515. *
  516. * When a tree block is cow'd in a reference counted root,
  517. * new back references are added for all the blocks it points to.
  518. * These are of the form (trans->transid will have increased since creation):
  519. *
  520. * (root->root_key.objectid, trans->transid, level, lowest_key_objectid)
  521. *
  522. * Because the lowest_key_objectid and the level are just hints
  523. * they are not used when backrefs are deleted. When a backref is deleted:
  524. *
  525. * if backref was for a tree root:
  526. * root_objectid = root->root_key.objectid
  527. * else
  528. * root_objectid = btrfs_header_owner(parent)
  529. *
  530. * (root_objectid, btrfs_header_generation(parent) or zero, 0, 0)
  531. *
  532. * Back Reference Key hashing:
  533. *
  534. * Back references have four fields, each 64 bits long. Unfortunately,
  535. * This is hashed into a single 64 bit number and placed into the key offset.
  536. * The key objectid corresponds to the first byte in the extent, and the
  537. * key type is set to BTRFS_EXTENT_REF_KEY
  538. */
  539. int btrfs_insert_extent_backref(struct btrfs_trans_handle *trans,
  540. struct btrfs_root *root,
  541. struct btrfs_path *path, u64 bytenr,
  542. u64 root_objectid, u64 ref_generation,
  543. u64 owner, u64 owner_offset)
  544. {
  545. u64 hash;
  546. struct btrfs_key key;
  547. struct btrfs_extent_ref ref;
  548. struct btrfs_extent_ref *disk_ref;
  549. int ret;
  550. btrfs_set_stack_ref_root(&ref, root_objectid);
  551. btrfs_set_stack_ref_generation(&ref, ref_generation);
  552. btrfs_set_stack_ref_objectid(&ref, owner);
  553. btrfs_set_stack_ref_offset(&ref, owner_offset);
  554. hash = hash_extent_ref(root_objectid, ref_generation, owner,
  555. owner_offset);
  556. key.offset = hash;
  557. key.objectid = bytenr;
  558. key.type = BTRFS_EXTENT_REF_KEY;
  559. ret = btrfs_insert_empty_item(trans, root, path, &key, sizeof(ref));
  560. while (ret == -EEXIST) {
  561. disk_ref = btrfs_item_ptr(path->nodes[0], path->slots[0],
  562. struct btrfs_extent_ref);
  563. if (match_extent_ref(path->nodes[0], disk_ref, &ref))
  564. goto out;
  565. key.offset++;
  566. btrfs_release_path(root, path);
  567. ret = btrfs_insert_empty_item(trans, root, path, &key,
  568. sizeof(ref));
  569. }
  570. if (ret)
  571. goto out;
  572. disk_ref = btrfs_item_ptr(path->nodes[0], path->slots[0],
  573. struct btrfs_extent_ref);
  574. write_extent_buffer(path->nodes[0], &ref, (unsigned long)disk_ref,
  575. sizeof(ref));
  576. btrfs_mark_buffer_dirty(path->nodes[0]);
  577. out:
  578. btrfs_release_path(root, path);
  579. return ret;
  580. }
  581. int btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
  582. struct btrfs_root *root,
  583. u64 bytenr, u64 num_bytes,
  584. u64 root_objectid, u64 ref_generation,
  585. u64 owner, u64 owner_offset)
  586. {
  587. struct btrfs_path *path;
  588. int ret;
  589. struct btrfs_key key;
  590. struct extent_buffer *l;
  591. struct btrfs_extent_item *item;
  592. u32 refs;
  593. WARN_ON(num_bytes < root->sectorsize);
  594. path = btrfs_alloc_path();
  595. if (!path)
  596. return -ENOMEM;
  597. path->reada = 0;
  598. key.objectid = bytenr;
  599. btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
  600. key.offset = num_bytes;
  601. ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
  602. 0, 1);
  603. if (ret < 0)
  604. return ret;
  605. if (ret != 0) {
  606. BUG();
  607. }
  608. BUG_ON(ret != 0);
  609. l = path->nodes[0];
  610. item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
  611. refs = btrfs_extent_refs(l, item);
  612. btrfs_set_extent_refs(l, item, refs + 1);
  613. btrfs_mark_buffer_dirty(path->nodes[0]);
  614. btrfs_release_path(root->fs_info->extent_root, path);
  615. path->reada = 0;
  616. ret = btrfs_insert_extent_backref(trans, root->fs_info->extent_root,
  617. path, bytenr, root_objectid,
  618. ref_generation, owner, owner_offset);
  619. BUG_ON(ret);
  620. finish_current_insert(trans, root->fs_info->extent_root);
  621. del_pending_extents(trans, root->fs_info->extent_root);
  622. btrfs_free_path(path);
  623. return 0;
  624. }
  625. int btrfs_extent_post_op(struct btrfs_trans_handle *trans,
  626. struct btrfs_root *root)
  627. {
  628. finish_current_insert(trans, root->fs_info->extent_root);
  629. del_pending_extents(trans, root->fs_info->extent_root);
  630. return 0;
  631. }
  632. static int lookup_extent_ref(struct btrfs_trans_handle *trans,
  633. struct btrfs_root *root, u64 bytenr,
  634. u64 num_bytes, u32 *refs)
  635. {
  636. struct btrfs_path *path;
  637. int ret;
  638. struct btrfs_key key;
  639. struct extent_buffer *l;
  640. struct btrfs_extent_item *item;
  641. WARN_ON(num_bytes < root->sectorsize);
  642. path = btrfs_alloc_path();
  643. path->reada = 0;
  644. key.objectid = bytenr;
  645. key.offset = num_bytes;
  646. btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
  647. ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
  648. 0, 0);
  649. if (ret < 0)
  650. goto out;
  651. if (ret != 0) {
  652. btrfs_print_leaf(root, path->nodes[0]);
  653. printk("failed to find block number %Lu\n", bytenr);
  654. BUG();
  655. }
  656. l = path->nodes[0];
  657. item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
  658. *refs = btrfs_extent_refs(l, item);
  659. out:
  660. btrfs_free_path(path);
  661. return 0;
  662. }
  663. u32 btrfs_count_snapshots_in_path(struct btrfs_root *root,
  664. struct btrfs_path *count_path,
  665. u64 first_extent)
  666. {
  667. struct btrfs_root *extent_root = root->fs_info->extent_root;
  668. struct btrfs_path *path;
  669. u64 bytenr;
  670. u64 found_objectid;
  671. u64 root_objectid = root->root_key.objectid;
  672. u32 total_count = 0;
  673. u32 cur_count;
  674. u32 nritems;
  675. int ret;
  676. struct btrfs_key key;
  677. struct btrfs_key found_key;
  678. struct extent_buffer *l;
  679. struct btrfs_extent_item *item;
  680. struct btrfs_extent_ref *ref_item;
  681. int level = -1;
  682. path = btrfs_alloc_path();
  683. again:
  684. if (level == -1)
  685. bytenr = first_extent;
  686. else
  687. bytenr = count_path->nodes[level]->start;
  688. cur_count = 0;
  689. key.objectid = bytenr;
  690. key.offset = 0;
  691. btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
  692. ret = btrfs_search_slot(NULL, extent_root, &key, path, 0, 0);
  693. if (ret < 0)
  694. goto out;
  695. BUG_ON(ret == 0);
  696. l = path->nodes[0];
  697. btrfs_item_key_to_cpu(l, &found_key, path->slots[0]);
  698. if (found_key.objectid != bytenr ||
  699. found_key.type != BTRFS_EXTENT_ITEM_KEY) {
  700. goto out;
  701. }
  702. item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
  703. while (1) {
  704. l = path->nodes[0];
  705. nritems = btrfs_header_nritems(l);
  706. if (path->slots[0] >= nritems) {
  707. ret = btrfs_next_leaf(extent_root, path);
  708. if (ret == 0)
  709. continue;
  710. break;
  711. }
  712. btrfs_item_key_to_cpu(l, &found_key, path->slots[0]);
  713. if (found_key.objectid != bytenr)
  714. break;
  715. if (found_key.type != BTRFS_EXTENT_REF_KEY) {
  716. path->slots[0]++;
  717. continue;
  718. }
  719. cur_count++;
  720. ref_item = btrfs_item_ptr(l, path->slots[0],
  721. struct btrfs_extent_ref);
  722. found_objectid = btrfs_ref_root(l, ref_item);
  723. if (found_objectid != root_objectid) {
  724. total_count = 2;
  725. goto out;
  726. }
  727. total_count = 1;
  728. path->slots[0]++;
  729. }
  730. if (cur_count == 0) {
  731. total_count = 0;
  732. goto out;
  733. }
  734. if (level >= 0 && root->node == count_path->nodes[level])
  735. goto out;
  736. level++;
  737. btrfs_release_path(root, path);
  738. goto again;
  739. out:
  740. btrfs_free_path(path);
  741. return total_count;
  742. }
  743. int btrfs_inc_root_ref(struct btrfs_trans_handle *trans,
  744. struct btrfs_root *root, u64 owner_objectid)
  745. {
  746. u64 generation;
  747. u64 key_objectid;
  748. u64 level;
  749. u32 nritems;
  750. struct btrfs_disk_key disk_key;
  751. level = btrfs_header_level(root->node);
  752. generation = trans->transid;
  753. nritems = btrfs_header_nritems(root->node);
  754. if (nritems > 0) {
  755. if (level == 0)
  756. btrfs_item_key(root->node, &disk_key, 0);
  757. else
  758. btrfs_node_key(root->node, &disk_key, 0);
  759. key_objectid = btrfs_disk_key_objectid(&disk_key);
  760. } else {
  761. key_objectid = 0;
  762. }
  763. return btrfs_inc_extent_ref(trans, root, root->node->start,
  764. root->node->len, owner_objectid,
  765. generation, level, key_objectid);
  766. }
  767. int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
  768. struct extent_buffer *buf)
  769. {
  770. u64 bytenr;
  771. u32 nritems;
  772. struct btrfs_key key;
  773. struct btrfs_file_extent_item *fi;
  774. int i;
  775. int level;
  776. int ret;
  777. int faili;
  778. if (!root->ref_cows)
  779. return 0;
  780. level = btrfs_header_level(buf);
  781. nritems = btrfs_header_nritems(buf);
  782. for (i = 0; i < nritems; i++) {
  783. if (level == 0) {
  784. u64 disk_bytenr;
  785. btrfs_item_key_to_cpu(buf, &key, i);
  786. if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
  787. continue;
  788. fi = btrfs_item_ptr(buf, i,
  789. struct btrfs_file_extent_item);
  790. if (btrfs_file_extent_type(buf, fi) ==
  791. BTRFS_FILE_EXTENT_INLINE)
  792. continue;
  793. disk_bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
  794. if (disk_bytenr == 0)
  795. continue;
  796. ret = btrfs_inc_extent_ref(trans, root, disk_bytenr,
  797. btrfs_file_extent_disk_num_bytes(buf, fi),
  798. root->root_key.objectid, trans->transid,
  799. key.objectid, key.offset);
  800. if (ret) {
  801. faili = i;
  802. goto fail;
  803. }
  804. } else {
  805. bytenr = btrfs_node_blockptr(buf, i);
  806. btrfs_node_key_to_cpu(buf, &key, i);
  807. ret = btrfs_inc_extent_ref(trans, root, bytenr,
  808. btrfs_level_size(root, level - 1),
  809. root->root_key.objectid,
  810. trans->transid,
  811. level - 1, key.objectid);
  812. if (ret) {
  813. faili = i;
  814. goto fail;
  815. }
  816. }
  817. }
  818. return 0;
  819. fail:
  820. WARN_ON(1);
  821. #if 0
  822. for (i =0; i < faili; i++) {
  823. if (level == 0) {
  824. u64 disk_bytenr;
  825. btrfs_item_key_to_cpu(buf, &key, i);
  826. if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
  827. continue;
  828. fi = btrfs_item_ptr(buf, i,
  829. struct btrfs_file_extent_item);
  830. if (btrfs_file_extent_type(buf, fi) ==
  831. BTRFS_FILE_EXTENT_INLINE)
  832. continue;
  833. disk_bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
  834. if (disk_bytenr == 0)
  835. continue;
  836. err = btrfs_free_extent(trans, root, disk_bytenr,
  837. btrfs_file_extent_disk_num_bytes(buf,
  838. fi), 0);
  839. BUG_ON(err);
  840. } else {
  841. bytenr = btrfs_node_blockptr(buf, i);
  842. err = btrfs_free_extent(trans, root, bytenr,
  843. btrfs_level_size(root, level - 1), 0);
  844. BUG_ON(err);
  845. }
  846. }
  847. #endif
  848. return ret;
  849. }
  850. static int write_one_cache_group(struct btrfs_trans_handle *trans,
  851. struct btrfs_root *root,
  852. struct btrfs_path *path,
  853. struct btrfs_block_group_cache *cache)
  854. {
  855. int ret;
  856. int pending_ret;
  857. struct btrfs_root *extent_root = root->fs_info->extent_root;
  858. unsigned long bi;
  859. struct extent_buffer *leaf;
  860. ret = btrfs_search_slot(trans, extent_root, &cache->key, path, 0, 1);
  861. if (ret < 0)
  862. goto fail;
  863. BUG_ON(ret);
  864. leaf = path->nodes[0];
  865. bi = btrfs_item_ptr_offset(leaf, path->slots[0]);
  866. write_extent_buffer(leaf, &cache->item, bi, sizeof(cache->item));
  867. btrfs_mark_buffer_dirty(leaf);
  868. btrfs_release_path(extent_root, path);
  869. fail:
  870. finish_current_insert(trans, extent_root);
  871. pending_ret = del_pending_extents(trans, extent_root);
  872. if (ret)
  873. return ret;
  874. if (pending_ret)
  875. return pending_ret;
  876. return 0;
  877. }
  878. int btrfs_write_dirty_block_groups(struct btrfs_trans_handle *trans,
  879. struct btrfs_root *root)
  880. {
  881. struct extent_io_tree *block_group_cache;
  882. struct btrfs_block_group_cache *cache;
  883. int ret;
  884. int err = 0;
  885. int werr = 0;
  886. struct btrfs_path *path;
  887. u64 last = 0;
  888. u64 start;
  889. u64 end;
  890. u64 ptr;
  891. block_group_cache = &root->fs_info->block_group_cache;
  892. path = btrfs_alloc_path();
  893. if (!path)
  894. return -ENOMEM;
  895. while(1) {
  896. ret = find_first_extent_bit(block_group_cache, last,
  897. &start, &end, BLOCK_GROUP_DIRTY);
  898. if (ret)
  899. break;
  900. last = end + 1;
  901. ret = get_state_private(block_group_cache, start, &ptr);
  902. if (ret)
  903. break;
  904. cache = (struct btrfs_block_group_cache *)(unsigned long)ptr;
  905. err = write_one_cache_group(trans, root,
  906. path, cache);
  907. /*
  908. * if we fail to write the cache group, we want
  909. * to keep it marked dirty in hopes that a later
  910. * write will work
  911. */
  912. if (err) {
  913. werr = err;
  914. continue;
  915. }
  916. clear_extent_bits(block_group_cache, start, end,
  917. BLOCK_GROUP_DIRTY, GFP_NOFS);
  918. }
  919. btrfs_free_path(path);
  920. return werr;
  921. }
  922. static struct btrfs_space_info *__find_space_info(struct btrfs_fs_info *info,
  923. u64 flags)
  924. {
  925. struct list_head *head = &info->space_info;
  926. struct list_head *cur;
  927. struct btrfs_space_info *found;
  928. list_for_each(cur, head) {
  929. found = list_entry(cur, struct btrfs_space_info, list);
  930. if (found->flags == flags)
  931. return found;
  932. }
  933. return NULL;
  934. }
  935. static int update_space_info(struct btrfs_fs_info *info, u64 flags,
  936. u64 total_bytes, u64 bytes_used,
  937. struct btrfs_space_info **space_info)
  938. {
  939. struct btrfs_space_info *found;
  940. found = __find_space_info(info, flags);
  941. if (found) {
  942. found->total_bytes += total_bytes;
  943. found->bytes_used += bytes_used;
  944. WARN_ON(found->total_bytes < found->bytes_used);
  945. *space_info = found;
  946. return 0;
  947. }
  948. found = kmalloc(sizeof(*found), GFP_NOFS);
  949. if (!found)
  950. return -ENOMEM;
  951. list_add(&found->list, &info->space_info);
  952. found->flags = flags;
  953. found->total_bytes = total_bytes;
  954. found->bytes_used = bytes_used;
  955. found->bytes_pinned = 0;
  956. found->full = 0;
  957. *space_info = found;
  958. return 0;
  959. }
  960. static void set_avail_alloc_bits(struct btrfs_fs_info *fs_info, u64 flags)
  961. {
  962. u64 extra_flags = flags & (BTRFS_BLOCK_GROUP_RAID0 |
  963. BTRFS_BLOCK_GROUP_RAID1 |
  964. BTRFS_BLOCK_GROUP_DUP);
  965. if (extra_flags) {
  966. if (flags & BTRFS_BLOCK_GROUP_DATA)
  967. fs_info->avail_data_alloc_bits |= extra_flags;
  968. if (flags & BTRFS_BLOCK_GROUP_METADATA)
  969. fs_info->avail_metadata_alloc_bits |= extra_flags;
  970. if (flags & BTRFS_BLOCK_GROUP_SYSTEM)
  971. fs_info->avail_system_alloc_bits |= extra_flags;
  972. }
  973. }
  974. static int do_chunk_alloc(struct btrfs_trans_handle *trans,
  975. struct btrfs_root *extent_root, u64 alloc_bytes,
  976. u64 flags)
  977. {
  978. struct btrfs_space_info *space_info;
  979. u64 thresh;
  980. u64 start;
  981. u64 num_bytes;
  982. int ret;
  983. space_info = __find_space_info(extent_root->fs_info, flags);
  984. if (!space_info) {
  985. ret = update_space_info(extent_root->fs_info, flags,
  986. 0, 0, &space_info);
  987. BUG_ON(ret);
  988. }
  989. BUG_ON(!space_info);
  990. if (space_info->full)
  991. return 0;
  992. thresh = div_factor(space_info->total_bytes, 6);
  993. if ((space_info->bytes_used + space_info->bytes_pinned + alloc_bytes) <
  994. thresh)
  995. return 0;
  996. ret = btrfs_alloc_chunk(trans, extent_root, &start, &num_bytes, flags);
  997. if (ret == -ENOSPC) {
  998. printk("space info full %Lu\n", flags);
  999. space_info->full = 1;
  1000. return 0;
  1001. }
  1002. BUG_ON(ret);
  1003. ret = btrfs_make_block_group(trans, extent_root, 0, flags,
  1004. extent_root->fs_info->chunk_root->root_key.objectid,
  1005. start, num_bytes);
  1006. BUG_ON(ret);
  1007. return 0;
  1008. }
  1009. static int update_block_group(struct btrfs_trans_handle *trans,
  1010. struct btrfs_root *root,
  1011. u64 bytenr, u64 num_bytes, int alloc,
  1012. int mark_free)
  1013. {
  1014. struct btrfs_block_group_cache *cache;
  1015. struct btrfs_fs_info *info = root->fs_info;
  1016. u64 total = num_bytes;
  1017. u64 old_val;
  1018. u64 byte_in_group;
  1019. u64 start;
  1020. u64 end;
  1021. while(total) {
  1022. cache = btrfs_lookup_block_group(info, bytenr);
  1023. if (!cache) {
  1024. return -1;
  1025. }
  1026. byte_in_group = bytenr - cache->key.objectid;
  1027. WARN_ON(byte_in_group > cache->key.offset);
  1028. start = cache->key.objectid;
  1029. end = start + cache->key.offset - 1;
  1030. set_extent_bits(&info->block_group_cache, start, end,
  1031. BLOCK_GROUP_DIRTY, GFP_NOFS);
  1032. old_val = btrfs_block_group_used(&cache->item);
  1033. num_bytes = min(total, cache->key.offset - byte_in_group);
  1034. if (alloc) {
  1035. old_val += num_bytes;
  1036. cache->space_info->bytes_used += num_bytes;
  1037. } else {
  1038. old_val -= num_bytes;
  1039. cache->space_info->bytes_used -= num_bytes;
  1040. if (mark_free) {
  1041. set_extent_dirty(&info->free_space_cache,
  1042. bytenr, bytenr + num_bytes - 1,
  1043. GFP_NOFS);
  1044. }
  1045. }
  1046. btrfs_set_block_group_used(&cache->item, old_val);
  1047. total -= num_bytes;
  1048. bytenr += num_bytes;
  1049. }
  1050. return 0;
  1051. }
  1052. static int update_pinned_extents(struct btrfs_root *root,
  1053. u64 bytenr, u64 num, int pin)
  1054. {
  1055. u64 len;
  1056. struct btrfs_block_group_cache *cache;
  1057. struct btrfs_fs_info *fs_info = root->fs_info;
  1058. if (pin) {
  1059. set_extent_dirty(&fs_info->pinned_extents,
  1060. bytenr, bytenr + num - 1, GFP_NOFS);
  1061. } else {
  1062. clear_extent_dirty(&fs_info->pinned_extents,
  1063. bytenr, bytenr + num - 1, GFP_NOFS);
  1064. }
  1065. while (num > 0) {
  1066. cache = btrfs_lookup_block_group(fs_info, bytenr);
  1067. WARN_ON(!cache);
  1068. len = min(num, cache->key.offset -
  1069. (bytenr - cache->key.objectid));
  1070. if (pin) {
  1071. cache->pinned += len;
  1072. cache->space_info->bytes_pinned += len;
  1073. fs_info->total_pinned += len;
  1074. } else {
  1075. cache->pinned -= len;
  1076. cache->space_info->bytes_pinned -= len;
  1077. fs_info->total_pinned -= len;
  1078. }
  1079. bytenr += len;
  1080. num -= len;
  1081. }
  1082. return 0;
  1083. }
  1084. int btrfs_copy_pinned(struct btrfs_root *root, struct extent_io_tree *copy)
  1085. {
  1086. u64 last = 0;
  1087. u64 start;
  1088. u64 end;
  1089. struct extent_io_tree *pinned_extents = &root->fs_info->pinned_extents;
  1090. int ret;
  1091. while(1) {
  1092. ret = find_first_extent_bit(pinned_extents, last,
  1093. &start, &end, EXTENT_DIRTY);
  1094. if (ret)
  1095. break;
  1096. set_extent_dirty(copy, start, end, GFP_NOFS);
  1097. last = end + 1;
  1098. }
  1099. return 0;
  1100. }
  1101. int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans,
  1102. struct btrfs_root *root,
  1103. struct extent_io_tree *unpin)
  1104. {
  1105. u64 start;
  1106. u64 end;
  1107. int ret;
  1108. struct extent_io_tree *free_space_cache;
  1109. free_space_cache = &root->fs_info->free_space_cache;
  1110. while(1) {
  1111. ret = find_first_extent_bit(unpin, 0, &start, &end,
  1112. EXTENT_DIRTY);
  1113. if (ret)
  1114. break;
  1115. update_pinned_extents(root, start, end + 1 - start, 0);
  1116. clear_extent_dirty(unpin, start, end, GFP_NOFS);
  1117. set_extent_dirty(free_space_cache, start, end, GFP_NOFS);
  1118. }
  1119. return 0;
  1120. }
  1121. static int finish_current_insert(struct btrfs_trans_handle *trans,
  1122. struct btrfs_root *extent_root)
  1123. {
  1124. u64 start;
  1125. u64 end;
  1126. struct btrfs_fs_info *info = extent_root->fs_info;
  1127. struct extent_buffer *eb;
  1128. struct btrfs_path *path;
  1129. struct btrfs_key ins;
  1130. struct btrfs_disk_key first;
  1131. struct btrfs_extent_item extent_item;
  1132. int ret;
  1133. int level;
  1134. int err = 0;
  1135. btrfs_set_stack_extent_refs(&extent_item, 1);
  1136. btrfs_set_key_type(&ins, BTRFS_EXTENT_ITEM_KEY);
  1137. path = btrfs_alloc_path();
  1138. while(1) {
  1139. ret = find_first_extent_bit(&info->extent_ins, 0, &start,
  1140. &end, EXTENT_LOCKED);
  1141. if (ret)
  1142. break;
  1143. ins.objectid = start;
  1144. ins.offset = end + 1 - start;
  1145. err = btrfs_insert_item(trans, extent_root, &ins,
  1146. &extent_item, sizeof(extent_item));
  1147. clear_extent_bits(&info->extent_ins, start, end, EXTENT_LOCKED,
  1148. GFP_NOFS);
  1149. eb = read_tree_block(extent_root, ins.objectid, ins.offset);
  1150. level = btrfs_header_level(eb);
  1151. if (level == 0) {
  1152. btrfs_item_key(eb, &first, 0);
  1153. } else {
  1154. btrfs_node_key(eb, &first, 0);
  1155. }
  1156. err = btrfs_insert_extent_backref(trans, extent_root, path,
  1157. start, extent_root->root_key.objectid,
  1158. 0, level,
  1159. btrfs_disk_key_objectid(&first));
  1160. BUG_ON(err);
  1161. free_extent_buffer(eb);
  1162. }
  1163. btrfs_free_path(path);
  1164. return 0;
  1165. }
  1166. static int pin_down_bytes(struct btrfs_root *root, u64 bytenr, u32 num_bytes,
  1167. int pending)
  1168. {
  1169. int err = 0;
  1170. struct extent_buffer *buf;
  1171. if (!pending) {
  1172. buf = btrfs_find_tree_block(root, bytenr, num_bytes);
  1173. if (buf) {
  1174. if (btrfs_buffer_uptodate(buf)) {
  1175. u64 transid =
  1176. root->fs_info->running_transaction->transid;
  1177. u64 header_transid =
  1178. btrfs_header_generation(buf);
  1179. if (header_transid == transid &&
  1180. !btrfs_header_flag(buf,
  1181. BTRFS_HEADER_FLAG_WRITTEN)) {
  1182. clean_tree_block(NULL, root, buf);
  1183. free_extent_buffer(buf);
  1184. return 1;
  1185. }
  1186. }
  1187. free_extent_buffer(buf);
  1188. }
  1189. update_pinned_extents(root, bytenr, num_bytes, 1);
  1190. } else {
  1191. set_extent_bits(&root->fs_info->pending_del,
  1192. bytenr, bytenr + num_bytes - 1,
  1193. EXTENT_LOCKED, GFP_NOFS);
  1194. }
  1195. BUG_ON(err < 0);
  1196. return 0;
  1197. }
  1198. /*
  1199. * remove an extent from the root, returns 0 on success
  1200. */
  1201. static int __free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
  1202. *root, u64 bytenr, u64 num_bytes,
  1203. u64 root_objectid, u64 ref_generation,
  1204. u64 owner_objectid, u64 owner_offset, int pin,
  1205. int mark_free)
  1206. {
  1207. struct btrfs_path *path;
  1208. struct btrfs_key key;
  1209. struct btrfs_fs_info *info = root->fs_info;
  1210. struct btrfs_root *extent_root = info->extent_root;
  1211. struct extent_buffer *leaf;
  1212. int ret;
  1213. int extent_slot = 0;
  1214. int found_extent = 0;
  1215. int num_to_del = 1;
  1216. struct btrfs_extent_item *ei;
  1217. u32 refs;
  1218. key.objectid = bytenr;
  1219. btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
  1220. key.offset = num_bytes;
  1221. path = btrfs_alloc_path();
  1222. if (!path)
  1223. return -ENOMEM;
  1224. path->reada = 0;
  1225. ret = lookup_extent_backref(trans, extent_root, path,
  1226. bytenr, root_objectid,
  1227. ref_generation,
  1228. owner_objectid, owner_offset, 1);
  1229. if (ret == 0) {
  1230. struct btrfs_key found_key;
  1231. extent_slot = path->slots[0];
  1232. while(extent_slot > 0) {
  1233. extent_slot--;
  1234. btrfs_item_key_to_cpu(path->nodes[0], &found_key,
  1235. extent_slot);
  1236. if (found_key.objectid != bytenr)
  1237. break;
  1238. if (found_key.type == BTRFS_EXTENT_ITEM_KEY &&
  1239. found_key.offset == num_bytes) {
  1240. found_extent = 1;
  1241. break;
  1242. }
  1243. if (path->slots[0] - extent_slot > 5)
  1244. break;
  1245. }
  1246. if (!found_extent)
  1247. ret = btrfs_del_item(trans, extent_root, path);
  1248. } else {
  1249. btrfs_print_leaf(extent_root, path->nodes[0]);
  1250. WARN_ON(1);
  1251. printk("Unable to find ref byte nr %Lu root %Lu "
  1252. " gen %Lu owner %Lu offset %Lu\n", bytenr,
  1253. root_objectid, ref_generation, owner_objectid,
  1254. owner_offset);
  1255. }
  1256. if (!found_extent) {
  1257. btrfs_release_path(extent_root, path);
  1258. ret = btrfs_search_slot(trans, extent_root, &key, path, -1, 1);
  1259. if (ret < 0)
  1260. return ret;
  1261. BUG_ON(ret);
  1262. extent_slot = path->slots[0];
  1263. }
  1264. leaf = path->nodes[0];
  1265. ei = btrfs_item_ptr(leaf, extent_slot,
  1266. struct btrfs_extent_item);
  1267. refs = btrfs_extent_refs(leaf, ei);
  1268. BUG_ON(refs == 0);
  1269. refs -= 1;
  1270. btrfs_set_extent_refs(leaf, ei, refs);
  1271. btrfs_mark_buffer_dirty(leaf);
  1272. if (refs == 0 && found_extent && path->slots[0] == extent_slot + 1) {
  1273. /* if the back ref and the extent are next to each other
  1274. * they get deleted below in one shot
  1275. */
  1276. path->slots[0] = extent_slot;
  1277. num_to_del = 2;
  1278. } else if (found_extent) {
  1279. /* otherwise delete the extent back ref */
  1280. ret = btrfs_del_item(trans, extent_root, path);
  1281. BUG_ON(ret);
  1282. /* if refs are 0, we need to setup the path for deletion */
  1283. if (refs == 0) {
  1284. btrfs_release_path(extent_root, path);
  1285. ret = btrfs_search_slot(trans, extent_root, &key, path,
  1286. -1, 1);
  1287. if (ret < 0)
  1288. return ret;
  1289. BUG_ON(ret);
  1290. }
  1291. }
  1292. if (refs == 0) {
  1293. u64 super_used;
  1294. u64 root_used;
  1295. if (pin) {
  1296. ret = pin_down_bytes(root, bytenr, num_bytes, 0);
  1297. if (ret > 0)
  1298. mark_free = 1;
  1299. BUG_ON(ret < 0);
  1300. }
  1301. /* block accounting for super block */
  1302. super_used = btrfs_super_bytes_used(&info->super_copy);
  1303. btrfs_set_super_bytes_used(&info->super_copy,
  1304. super_used - num_bytes);
  1305. /* block accounting for root item */
  1306. root_used = btrfs_root_used(&root->root_item);
  1307. btrfs_set_root_used(&root->root_item,
  1308. root_used - num_bytes);
  1309. ret = btrfs_del_items(trans, extent_root, path, path->slots[0],
  1310. num_to_del);
  1311. if (ret) {
  1312. return ret;
  1313. }
  1314. ret = update_block_group(trans, root, bytenr, num_bytes, 0,
  1315. mark_free);
  1316. BUG_ON(ret);
  1317. }
  1318. btrfs_free_path(path);
  1319. finish_current_insert(trans, extent_root);
  1320. return ret;
  1321. }
  1322. /*
  1323. * find all the blocks marked as pending in the radix tree and remove
  1324. * them from the extent map
  1325. */
  1326. static int del_pending_extents(struct btrfs_trans_handle *trans, struct
  1327. btrfs_root *extent_root)
  1328. {
  1329. int ret;
  1330. int err = 0;
  1331. u64 start;
  1332. u64 end;
  1333. struct extent_io_tree *pending_del;
  1334. struct extent_io_tree *pinned_extents;
  1335. pending_del = &extent_root->fs_info->pending_del;
  1336. pinned_extents = &extent_root->fs_info->pinned_extents;
  1337. while(1) {
  1338. ret = find_first_extent_bit(pending_del, 0, &start, &end,
  1339. EXTENT_LOCKED);
  1340. if (ret)
  1341. break;
  1342. update_pinned_extents(extent_root, start, end + 1 - start, 1);
  1343. clear_extent_bits(pending_del, start, end, EXTENT_LOCKED,
  1344. GFP_NOFS);
  1345. ret = __free_extent(trans, extent_root,
  1346. start, end + 1 - start,
  1347. extent_root->root_key.objectid,
  1348. 0, 0, 0, 0, 0);
  1349. if (ret)
  1350. err = ret;
  1351. }
  1352. return err;
  1353. }
  1354. /*
  1355. * remove an extent from the root, returns 0 on success
  1356. */
  1357. int btrfs_free_extent(struct btrfs_trans_handle *trans, struct btrfs_root
  1358. *root, u64 bytenr, u64 num_bytes,
  1359. u64 root_objectid, u64 ref_generation,
  1360. u64 owner_objectid, u64 owner_offset, int pin)
  1361. {
  1362. struct btrfs_root *extent_root = root->fs_info->extent_root;
  1363. int pending_ret;
  1364. int ret;
  1365. WARN_ON(num_bytes < root->sectorsize);
  1366. if (!root->ref_cows)
  1367. ref_generation = 0;
  1368. if (root == extent_root) {
  1369. pin_down_bytes(root, bytenr, num_bytes, 1);
  1370. return 0;
  1371. }
  1372. ret = __free_extent(trans, root, bytenr, num_bytes, root_objectid,
  1373. ref_generation, owner_objectid, owner_offset,
  1374. pin, pin == 0);
  1375. pending_ret = del_pending_extents(trans, root->fs_info->extent_root);
  1376. return ret ? ret : pending_ret;
  1377. }
  1378. static u64 stripe_align(struct btrfs_root *root, u64 val)
  1379. {
  1380. u64 mask = ((u64)root->stripesize - 1);
  1381. u64 ret = (val + mask) & ~mask;
  1382. return ret;
  1383. }
  1384. /*
  1385. * walks the btree of allocated extents and find a hole of a given size.
  1386. * The key ins is changed to record the hole:
  1387. * ins->objectid == block start
  1388. * ins->flags = BTRFS_EXTENT_ITEM_KEY
  1389. * ins->offset == number of blocks
  1390. * Any available blocks before search_start are skipped.
  1391. */
  1392. static int noinline find_free_extent(struct btrfs_trans_handle *trans,
  1393. struct btrfs_root *orig_root,
  1394. u64 num_bytes, u64 empty_size,
  1395. u64 search_start, u64 search_end,
  1396. u64 hint_byte, struct btrfs_key *ins,
  1397. u64 exclude_start, u64 exclude_nr,
  1398. int data)
  1399. {
  1400. int ret;
  1401. u64 orig_search_start = search_start;
  1402. struct btrfs_root * root = orig_root->fs_info->extent_root;
  1403. struct btrfs_fs_info *info = root->fs_info;
  1404. u64 total_needed = num_bytes;
  1405. u64 *last_ptr = NULL;
  1406. struct btrfs_block_group_cache *block_group;
  1407. int full_scan = 0;
  1408. int wrapped = 0;
  1409. int empty_cluster = 2 * 1024 * 1024;
  1410. WARN_ON(num_bytes < root->sectorsize);
  1411. btrfs_set_key_type(ins, BTRFS_EXTENT_ITEM_KEY);
  1412. if (data & BTRFS_BLOCK_GROUP_METADATA) {
  1413. last_ptr = &root->fs_info->last_alloc;
  1414. empty_cluster = 256 * 1024;
  1415. }
  1416. if ((data & BTRFS_BLOCK_GROUP_DATA) && btrfs_test_opt(root, SSD)) {
  1417. last_ptr = &root->fs_info->last_data_alloc;
  1418. }
  1419. if (last_ptr) {
  1420. if (*last_ptr)
  1421. hint_byte = *last_ptr;
  1422. else {
  1423. empty_size += empty_cluster;
  1424. }
  1425. }
  1426. if (search_end == (u64)-1)
  1427. search_end = btrfs_super_total_bytes(&info->super_copy);
  1428. if (hint_byte) {
  1429. block_group = btrfs_lookup_block_group(info, hint_byte);
  1430. if (!block_group)
  1431. hint_byte = search_start;
  1432. block_group = btrfs_find_block_group(root, block_group,
  1433. hint_byte, data, 1);
  1434. if (last_ptr && *last_ptr == 0 && block_group)
  1435. hint_byte = block_group->key.objectid;
  1436. } else {
  1437. block_group = btrfs_find_block_group(root,
  1438. trans->block_group,
  1439. search_start, data, 1);
  1440. }
  1441. search_start = max(search_start, hint_byte);
  1442. total_needed += empty_size;
  1443. check_failed:
  1444. if (!block_group) {
  1445. block_group = btrfs_lookup_block_group(info, search_start);
  1446. if (!block_group)
  1447. block_group = btrfs_lookup_block_group(info,
  1448. orig_search_start);
  1449. }
  1450. ret = find_search_start(root, &block_group, &search_start,
  1451. total_needed, data);
  1452. if (ret == -ENOSPC && last_ptr && *last_ptr) {
  1453. *last_ptr = 0;
  1454. block_group = btrfs_lookup_block_group(info,
  1455. orig_search_start);
  1456. search_start = orig_search_start;
  1457. ret = find_search_start(root, &block_group, &search_start,
  1458. total_needed, data);
  1459. }
  1460. if (ret == -ENOSPC)
  1461. goto enospc;
  1462. if (ret)
  1463. goto error;
  1464. if (last_ptr && *last_ptr && search_start != *last_ptr) {
  1465. *last_ptr = 0;
  1466. if (!empty_size) {
  1467. empty_size += empty_cluster;
  1468. total_needed += empty_size;
  1469. }
  1470. block_group = btrfs_lookup_block_group(info,
  1471. orig_search_start);
  1472. search_start = orig_search_start;
  1473. ret = find_search_start(root, &block_group,
  1474. &search_start, total_needed, data);
  1475. if (ret == -ENOSPC)
  1476. goto enospc;
  1477. if (ret)
  1478. goto error;
  1479. }
  1480. search_start = stripe_align(root, search_start);
  1481. ins->objectid = search_start;
  1482. ins->offset = num_bytes;
  1483. if (ins->objectid + num_bytes >= search_end)
  1484. goto enospc;
  1485. if (ins->objectid + num_bytes >
  1486. block_group->key.objectid + block_group->key.offset) {
  1487. search_start = block_group->key.objectid +
  1488. block_group->key.offset;
  1489. goto new_group;
  1490. }
  1491. if (test_range_bit(&info->extent_ins, ins->objectid,
  1492. ins->objectid + num_bytes -1, EXTENT_LOCKED, 0)) {
  1493. search_start = ins->objectid + num_bytes;
  1494. goto new_group;
  1495. }
  1496. if (test_range_bit(&info->pinned_extents, ins->objectid,
  1497. ins->objectid + num_bytes -1, EXTENT_DIRTY, 0)) {
  1498. search_start = ins->objectid + num_bytes;
  1499. goto new_group;
  1500. }
  1501. if (exclude_nr > 0 && (ins->objectid + num_bytes > exclude_start &&
  1502. ins->objectid < exclude_start + exclude_nr)) {
  1503. search_start = exclude_start + exclude_nr;
  1504. goto new_group;
  1505. }
  1506. if (!(data & BTRFS_BLOCK_GROUP_DATA)) {
  1507. block_group = btrfs_lookup_block_group(info, ins->objectid);
  1508. if (block_group)
  1509. trans->block_group = block_group;
  1510. }
  1511. ins->offset = num_bytes;
  1512. if (last_ptr) {
  1513. *last_ptr = ins->objectid + ins->offset;
  1514. if (*last_ptr ==
  1515. btrfs_super_total_bytes(&root->fs_info->super_copy)) {
  1516. *last_ptr = 0;
  1517. }
  1518. }
  1519. return 0;
  1520. new_group:
  1521. if (search_start + num_bytes >= search_end) {
  1522. enospc:
  1523. search_start = orig_search_start;
  1524. if (full_scan) {
  1525. ret = -ENOSPC;
  1526. goto error;
  1527. }
  1528. if (wrapped) {
  1529. if (!full_scan)
  1530. total_needed -= empty_size;
  1531. full_scan = 1;
  1532. } else
  1533. wrapped = 1;
  1534. }
  1535. block_group = btrfs_lookup_block_group(info, search_start);
  1536. cond_resched();
  1537. block_group = btrfs_find_block_group(root, block_group,
  1538. search_start, data, 0);
  1539. goto check_failed;
  1540. error:
  1541. return ret;
  1542. }
  1543. /*
  1544. * finds a free extent and does all the dirty work required for allocation
  1545. * returns the key for the extent through ins, and a tree buffer for
  1546. * the first block of the extent through buf.
  1547. *
  1548. * returns 0 if everything worked, non-zero otherwise.
  1549. */
  1550. int btrfs_alloc_extent(struct btrfs_trans_handle *trans,
  1551. struct btrfs_root *root,
  1552. u64 num_bytes, u64 min_alloc_size,
  1553. u64 root_objectid, u64 ref_generation,
  1554. u64 owner, u64 owner_offset,
  1555. u64 empty_size, u64 hint_byte,
  1556. u64 search_end, struct btrfs_key *ins, int data)
  1557. {
  1558. int ret;
  1559. int pending_ret;
  1560. u64 super_used;
  1561. u64 root_used;
  1562. u64 search_start = 0;
  1563. u64 new_hint;
  1564. u64 alloc_profile;
  1565. u32 sizes[2];
  1566. struct btrfs_fs_info *info = root->fs_info;
  1567. struct btrfs_root *extent_root = info->extent_root;
  1568. struct btrfs_extent_item *extent_item;
  1569. struct btrfs_extent_ref *ref;
  1570. struct btrfs_path *path;
  1571. struct btrfs_key keys[2];
  1572. if (data) {
  1573. alloc_profile = info->avail_data_alloc_bits &
  1574. info->data_alloc_profile;
  1575. data = BTRFS_BLOCK_GROUP_DATA | alloc_profile;
  1576. } else if (root == root->fs_info->chunk_root) {
  1577. alloc_profile = info->avail_system_alloc_bits &
  1578. info->system_alloc_profile;
  1579. data = BTRFS_BLOCK_GROUP_SYSTEM | alloc_profile;
  1580. } else {
  1581. alloc_profile = info->avail_metadata_alloc_bits &
  1582. info->metadata_alloc_profile;
  1583. data = BTRFS_BLOCK_GROUP_METADATA | alloc_profile;
  1584. }
  1585. again:
  1586. if (root->ref_cows) {
  1587. if (!(data & BTRFS_BLOCK_GROUP_METADATA)) {
  1588. ret = do_chunk_alloc(trans, root->fs_info->extent_root,
  1589. 2 * 1024 * 1024,
  1590. BTRFS_BLOCK_GROUP_METADATA |
  1591. (info->metadata_alloc_profile &
  1592. info->avail_metadata_alloc_bits));
  1593. BUG_ON(ret);
  1594. }
  1595. ret = do_chunk_alloc(trans, root->fs_info->extent_root,
  1596. num_bytes + 2 * 1024 * 1024, data);
  1597. BUG_ON(ret);
  1598. }
  1599. new_hint = max(hint_byte, root->fs_info->alloc_start);
  1600. if (new_hint < btrfs_super_total_bytes(&info->super_copy))
  1601. hint_byte = new_hint;
  1602. WARN_ON(num_bytes < root->sectorsize);
  1603. ret = find_free_extent(trans, root, num_bytes, empty_size,
  1604. search_start, search_end, hint_byte, ins,
  1605. trans->alloc_exclude_start,
  1606. trans->alloc_exclude_nr, data);
  1607. if (ret == -ENOSPC && num_bytes > min_alloc_size) {
  1608. num_bytes = num_bytes >> 1;
  1609. num_bytes = max(num_bytes, min_alloc_size);
  1610. goto again;
  1611. }
  1612. BUG_ON(ret);
  1613. if (ret)
  1614. return ret;
  1615. /* block accounting for super block */
  1616. super_used = btrfs_super_bytes_used(&info->super_copy);
  1617. btrfs_set_super_bytes_used(&info->super_copy, super_used + num_bytes);
  1618. /* block accounting for root item */
  1619. root_used = btrfs_root_used(&root->root_item);
  1620. btrfs_set_root_used(&root->root_item, root_used + num_bytes);
  1621. clear_extent_dirty(&root->fs_info->free_space_cache,
  1622. ins->objectid, ins->objectid + ins->offset - 1,
  1623. GFP_NOFS);
  1624. if (root == extent_root) {
  1625. set_extent_bits(&root->fs_info->extent_ins, ins->objectid,
  1626. ins->objectid + ins->offset - 1,
  1627. EXTENT_LOCKED, GFP_NOFS);
  1628. goto update_block;
  1629. }
  1630. WARN_ON(trans->alloc_exclude_nr);
  1631. trans->alloc_exclude_start = ins->objectid;
  1632. trans->alloc_exclude_nr = ins->offset;
  1633. memcpy(&keys[0], ins, sizeof(*ins));
  1634. keys[1].offset = hash_extent_ref(root_objectid, ref_generation,
  1635. owner, owner_offset);
  1636. keys[1].objectid = ins->objectid;
  1637. keys[1].type = BTRFS_EXTENT_REF_KEY;
  1638. sizes[0] = sizeof(*extent_item);
  1639. sizes[1] = sizeof(*ref);
  1640. path = btrfs_alloc_path();
  1641. BUG_ON(!path);
  1642. ret = btrfs_insert_empty_items(trans, extent_root, path, keys,
  1643. sizes, 2);
  1644. BUG_ON(ret);
  1645. extent_item = btrfs_item_ptr(path->nodes[0], path->slots[0],
  1646. struct btrfs_extent_item);
  1647. btrfs_set_extent_refs(path->nodes[0], extent_item, 1);
  1648. ref = btrfs_item_ptr(path->nodes[0], path->slots[0] + 1,
  1649. struct btrfs_extent_ref);
  1650. btrfs_set_ref_root(path->nodes[0], ref, root_objectid);
  1651. btrfs_set_ref_generation(path->nodes[0], ref, ref_generation);
  1652. btrfs_set_ref_objectid(path->nodes[0], ref, owner);
  1653. btrfs_set_ref_offset(path->nodes[0], ref, owner_offset);
  1654. btrfs_mark_buffer_dirty(path->nodes[0]);
  1655. trans->alloc_exclude_start = 0;
  1656. trans->alloc_exclude_nr = 0;
  1657. btrfs_free_path(path);
  1658. finish_current_insert(trans, extent_root);
  1659. pending_ret = del_pending_extents(trans, extent_root);
  1660. if (ret) {
  1661. return ret;
  1662. }
  1663. if (pending_ret) {
  1664. return pending_ret;
  1665. }
  1666. update_block:
  1667. ret = update_block_group(trans, root, ins->objectid, ins->offset, 1, 0);
  1668. if (ret) {
  1669. printk("update block group failed for %Lu %Lu\n",
  1670. ins->objectid, ins->offset);
  1671. BUG();
  1672. }
  1673. return 0;
  1674. }
  1675. /*
  1676. * helper function to allocate a block for a given tree
  1677. * returns the tree buffer or NULL.
  1678. */
  1679. struct extent_buffer *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
  1680. struct btrfs_root *root,
  1681. u32 blocksize,
  1682. u64 root_objectid, u64 hint,
  1683. u64 empty_size)
  1684. {
  1685. u64 ref_generation;
  1686. if (root->ref_cows)
  1687. ref_generation = trans->transid;
  1688. else
  1689. ref_generation = 0;
  1690. return __btrfs_alloc_free_block(trans, root, blocksize, root_objectid,
  1691. ref_generation, 0, 0, hint, empty_size);
  1692. }
  1693. /*
  1694. * helper function to allocate a block for a given tree
  1695. * returns the tree buffer or NULL.
  1696. */
  1697. struct extent_buffer *__btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
  1698. struct btrfs_root *root,
  1699. u32 blocksize,
  1700. u64 root_objectid,
  1701. u64 ref_generation,
  1702. u64 first_objectid,
  1703. int level,
  1704. u64 hint,
  1705. u64 empty_size)
  1706. {
  1707. struct btrfs_key ins;
  1708. int ret;
  1709. struct extent_buffer *buf;
  1710. ret = btrfs_alloc_extent(trans, root, blocksize, blocksize,
  1711. root_objectid, ref_generation,
  1712. level, first_objectid, empty_size, hint,
  1713. (u64)-1, &ins, 0);
  1714. if (ret) {
  1715. BUG_ON(ret > 0);
  1716. return ERR_PTR(ret);
  1717. }
  1718. buf = btrfs_find_create_tree_block(root, ins.objectid, blocksize);
  1719. if (!buf) {
  1720. btrfs_free_extent(trans, root, ins.objectid, blocksize,
  1721. root->root_key.objectid, ref_generation,
  1722. 0, 0, 0);
  1723. return ERR_PTR(-ENOMEM);
  1724. }
  1725. btrfs_set_header_generation(buf, trans->transid);
  1726. clean_tree_block(trans, root, buf);
  1727. wait_on_tree_block_writeback(root, buf);
  1728. btrfs_set_buffer_uptodate(buf);
  1729. if (PageDirty(buf->first_page)) {
  1730. printk("page %lu dirty\n", buf->first_page->index);
  1731. WARN_ON(1);
  1732. }
  1733. set_extent_dirty(&trans->transaction->dirty_pages, buf->start,
  1734. buf->start + buf->len - 1, GFP_NOFS);
  1735. if (!btrfs_test_opt(root, SSD))
  1736. btrfs_set_buffer_defrag(buf);
  1737. trans->blocks_used++;
  1738. return buf;
  1739. }
  1740. static int noinline drop_leaf_ref(struct btrfs_trans_handle *trans,
  1741. struct btrfs_root *root,
  1742. struct extent_buffer *leaf)
  1743. {
  1744. u64 leaf_owner;
  1745. u64 leaf_generation;
  1746. struct btrfs_key key;
  1747. struct btrfs_file_extent_item *fi;
  1748. int i;
  1749. int nritems;
  1750. int ret;
  1751. BUG_ON(!btrfs_is_leaf(leaf));
  1752. nritems = btrfs_header_nritems(leaf);
  1753. leaf_owner = btrfs_header_owner(leaf);
  1754. leaf_generation = btrfs_header_generation(leaf);
  1755. for (i = 0; i < nritems; i++) {
  1756. u64 disk_bytenr;
  1757. btrfs_item_key_to_cpu(leaf, &key, i);
  1758. if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
  1759. continue;
  1760. fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
  1761. if (btrfs_file_extent_type(leaf, fi) ==
  1762. BTRFS_FILE_EXTENT_INLINE)
  1763. continue;
  1764. /*
  1765. * FIXME make sure to insert a trans record that
  1766. * repeats the snapshot del on crash
  1767. */
  1768. disk_bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
  1769. if (disk_bytenr == 0)
  1770. continue;
  1771. ret = btrfs_free_extent(trans, root, disk_bytenr,
  1772. btrfs_file_extent_disk_num_bytes(leaf, fi),
  1773. leaf_owner, leaf_generation,
  1774. key.objectid, key.offset, 0);
  1775. BUG_ON(ret);
  1776. }
  1777. return 0;
  1778. }
  1779. static void noinline reada_walk_down(struct btrfs_root *root,
  1780. struct extent_buffer *node,
  1781. int slot)
  1782. {
  1783. u64 bytenr;
  1784. u64 last = 0;
  1785. u32 nritems;
  1786. u32 refs;
  1787. u32 blocksize;
  1788. int ret;
  1789. int i;
  1790. int level;
  1791. int skipped = 0;
  1792. nritems = btrfs_header_nritems(node);
  1793. level = btrfs_header_level(node);
  1794. if (level)
  1795. return;
  1796. for (i = slot; i < nritems && skipped < 32; i++) {
  1797. bytenr = btrfs_node_blockptr(node, i);
  1798. if (last && ((bytenr > last && bytenr - last > 32 * 1024) ||
  1799. (last > bytenr && last - bytenr > 32 * 1024))) {
  1800. skipped++;
  1801. continue;
  1802. }
  1803. blocksize = btrfs_level_size(root, level - 1);
  1804. if (i != slot) {
  1805. ret = lookup_extent_ref(NULL, root, bytenr,
  1806. blocksize, &refs);
  1807. BUG_ON(ret);
  1808. if (refs != 1) {
  1809. skipped++;
  1810. continue;
  1811. }
  1812. }
  1813. mutex_unlock(&root->fs_info->fs_mutex);
  1814. ret = readahead_tree_block(root, bytenr, blocksize);
  1815. last = bytenr + blocksize;
  1816. cond_resched();
  1817. mutex_lock(&root->fs_info->fs_mutex);
  1818. if (ret)
  1819. break;
  1820. }
  1821. }
  1822. /*
  1823. * helper function for drop_snapshot, this walks down the tree dropping ref
  1824. * counts as it goes.
  1825. */
  1826. static int noinline walk_down_tree(struct btrfs_trans_handle *trans,
  1827. struct btrfs_root *root,
  1828. struct btrfs_path *path, int *level)
  1829. {
  1830. u64 root_owner;
  1831. u64 root_gen;
  1832. u64 bytenr;
  1833. struct extent_buffer *next;
  1834. struct extent_buffer *cur;
  1835. struct extent_buffer *parent;
  1836. u32 blocksize;
  1837. int ret;
  1838. u32 refs;
  1839. WARN_ON(*level < 0);
  1840. WARN_ON(*level >= BTRFS_MAX_LEVEL);
  1841. ret = lookup_extent_ref(trans, root,
  1842. path->nodes[*level]->start,
  1843. path->nodes[*level]->len, &refs);
  1844. BUG_ON(ret);
  1845. if (refs > 1)
  1846. goto out;
  1847. /*
  1848. * walk down to the last node level and free all the leaves
  1849. */
  1850. while(*level >= 0) {
  1851. WARN_ON(*level < 0);
  1852. WARN_ON(*level >= BTRFS_MAX_LEVEL);
  1853. cur = path->nodes[*level];
  1854. if (btrfs_header_level(cur) != *level)
  1855. WARN_ON(1);
  1856. if (path->slots[*level] >=
  1857. btrfs_header_nritems(cur))
  1858. break;
  1859. if (*level == 0) {
  1860. ret = drop_leaf_ref(trans, root, cur);
  1861. BUG_ON(ret);
  1862. break;
  1863. }
  1864. bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
  1865. blocksize = btrfs_level_size(root, *level - 1);
  1866. ret = lookup_extent_ref(trans, root, bytenr, blocksize, &refs);
  1867. BUG_ON(ret);
  1868. if (refs != 1) {
  1869. parent = path->nodes[*level];
  1870. root_owner = btrfs_header_owner(parent);
  1871. root_gen = btrfs_header_generation(parent);
  1872. path->slots[*level]++;
  1873. ret = btrfs_free_extent(trans, root, bytenr,
  1874. blocksize, root_owner,
  1875. root_gen, 0, 0, 1);
  1876. BUG_ON(ret);
  1877. continue;
  1878. }
  1879. next = btrfs_find_tree_block(root, bytenr, blocksize);
  1880. if (!next || !btrfs_buffer_uptodate(next)) {
  1881. free_extent_buffer(next);
  1882. reada_walk_down(root, cur, path->slots[*level]);
  1883. mutex_unlock(&root->fs_info->fs_mutex);
  1884. next = read_tree_block(root, bytenr, blocksize);
  1885. mutex_lock(&root->fs_info->fs_mutex);
  1886. /* we've dropped the lock, double check */
  1887. ret = lookup_extent_ref(trans, root, bytenr,
  1888. blocksize, &refs);
  1889. BUG_ON(ret);
  1890. if (refs != 1) {
  1891. parent = path->nodes[*level];
  1892. root_owner = btrfs_header_owner(parent);
  1893. root_gen = btrfs_header_generation(parent);
  1894. path->slots[*level]++;
  1895. free_extent_buffer(next);
  1896. ret = btrfs_free_extent(trans, root, bytenr,
  1897. blocksize,
  1898. root_owner,
  1899. root_gen, 0, 0, 1);
  1900. BUG_ON(ret);
  1901. continue;
  1902. }
  1903. } else if (next) {
  1904. btrfs_verify_block_csum(root, next);
  1905. }
  1906. WARN_ON(*level <= 0);
  1907. if (path->nodes[*level-1])
  1908. free_extent_buffer(path->nodes[*level-1]);
  1909. path->nodes[*level-1] = next;
  1910. *level = btrfs_header_level(next);
  1911. path->slots[*level] = 0;
  1912. }
  1913. out:
  1914. WARN_ON(*level < 0);
  1915. WARN_ON(*level >= BTRFS_MAX_LEVEL);
  1916. if (path->nodes[*level] == root->node) {
  1917. root_owner = root->root_key.objectid;
  1918. parent = path->nodes[*level];
  1919. } else {
  1920. parent = path->nodes[*level + 1];
  1921. root_owner = btrfs_header_owner(parent);
  1922. }
  1923. root_gen = btrfs_header_generation(parent);
  1924. ret = btrfs_free_extent(trans, root, path->nodes[*level]->start,
  1925. path->nodes[*level]->len,
  1926. root_owner, root_gen, 0, 0, 1);
  1927. free_extent_buffer(path->nodes[*level]);
  1928. path->nodes[*level] = NULL;
  1929. *level += 1;
  1930. BUG_ON(ret);
  1931. return 0;
  1932. }
  1933. /*
  1934. * helper for dropping snapshots. This walks back up the tree in the path
  1935. * to find the first node higher up where we haven't yet gone through
  1936. * all the slots
  1937. */
  1938. static int noinline walk_up_tree(struct btrfs_trans_handle *trans,
  1939. struct btrfs_root *root,
  1940. struct btrfs_path *path, int *level)
  1941. {
  1942. u64 root_owner;
  1943. u64 root_gen;
  1944. struct btrfs_root_item *root_item = &root->root_item;
  1945. int i;
  1946. int slot;
  1947. int ret;
  1948. for(i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
  1949. slot = path->slots[i];
  1950. if (slot < btrfs_header_nritems(path->nodes[i]) - 1) {
  1951. struct extent_buffer *node;
  1952. struct btrfs_disk_key disk_key;
  1953. node = path->nodes[i];
  1954. path->slots[i]++;
  1955. *level = i;
  1956. WARN_ON(*level == 0);
  1957. btrfs_node_key(node, &disk_key, path->slots[i]);
  1958. memcpy(&root_item->drop_progress,
  1959. &disk_key, sizeof(disk_key));
  1960. root_item->drop_level = i;
  1961. return 0;
  1962. } else {
  1963. if (path->nodes[*level] == root->node) {
  1964. root_owner = root->root_key.objectid;
  1965. root_gen =
  1966. btrfs_header_generation(path->nodes[*level]);
  1967. } else {
  1968. struct extent_buffer *node;
  1969. node = path->nodes[*level + 1];
  1970. root_owner = btrfs_header_owner(node);
  1971. root_gen = btrfs_header_generation(node);
  1972. }
  1973. ret = btrfs_free_extent(trans, root,
  1974. path->nodes[*level]->start,
  1975. path->nodes[*level]->len,
  1976. root_owner, root_gen, 0, 0, 1);
  1977. BUG_ON(ret);
  1978. free_extent_buffer(path->nodes[*level]);
  1979. path->nodes[*level] = NULL;
  1980. *level = i + 1;
  1981. }
  1982. }
  1983. return 1;
  1984. }
  1985. /*
  1986. * drop the reference count on the tree rooted at 'snap'. This traverses
  1987. * the tree freeing any blocks that have a ref count of zero after being
  1988. * decremented.
  1989. */
  1990. int btrfs_drop_snapshot(struct btrfs_trans_handle *trans, struct btrfs_root
  1991. *root)
  1992. {
  1993. int ret = 0;
  1994. int wret;
  1995. int level;
  1996. struct btrfs_path *path;
  1997. int i;
  1998. int orig_level;
  1999. struct btrfs_root_item *root_item = &root->root_item;
  2000. path = btrfs_alloc_path();
  2001. BUG_ON(!path);
  2002. level = btrfs_header_level(root->node);
  2003. orig_level = level;
  2004. if (btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
  2005. path->nodes[level] = root->node;
  2006. extent_buffer_get(root->node);
  2007. path->slots[level] = 0;
  2008. } else {
  2009. struct btrfs_key key;
  2010. struct btrfs_disk_key found_key;
  2011. struct extent_buffer *node;
  2012. btrfs_disk_key_to_cpu(&key, &root_item->drop_progress);
  2013. level = root_item->drop_level;
  2014. path->lowest_level = level;
  2015. wret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
  2016. if (wret < 0) {
  2017. ret = wret;
  2018. goto out;
  2019. }
  2020. node = path->nodes[level];
  2021. btrfs_node_key(node, &found_key, path->slots[level]);
  2022. WARN_ON(memcmp(&found_key, &root_item->drop_progress,
  2023. sizeof(found_key)));
  2024. }
  2025. while(1) {
  2026. wret = walk_down_tree(trans, root, path, &level);
  2027. if (wret > 0)
  2028. break;
  2029. if (wret < 0)
  2030. ret = wret;
  2031. wret = walk_up_tree(trans, root, path, &level);
  2032. if (wret > 0)
  2033. break;
  2034. if (wret < 0)
  2035. ret = wret;
  2036. ret = -EAGAIN;
  2037. break;
  2038. }
  2039. for (i = 0; i <= orig_level; i++) {
  2040. if (path->nodes[i]) {
  2041. free_extent_buffer(path->nodes[i]);
  2042. path->nodes[i] = NULL;
  2043. }
  2044. }
  2045. out:
  2046. btrfs_free_path(path);
  2047. return ret;
  2048. }
  2049. int btrfs_free_block_groups(struct btrfs_fs_info *info)
  2050. {
  2051. u64 start;
  2052. u64 end;
  2053. u64 ptr;
  2054. int ret;
  2055. while(1) {
  2056. ret = find_first_extent_bit(&info->block_group_cache, 0,
  2057. &start, &end, (unsigned int)-1);
  2058. if (ret)
  2059. break;
  2060. ret = get_state_private(&info->block_group_cache, start, &ptr);
  2061. if (!ret)
  2062. kfree((void *)(unsigned long)ptr);
  2063. clear_extent_bits(&info->block_group_cache, start,
  2064. end, (unsigned int)-1, GFP_NOFS);
  2065. }
  2066. while(1) {
  2067. ret = find_first_extent_bit(&info->free_space_cache, 0,
  2068. &start, &end, EXTENT_DIRTY);
  2069. if (ret)
  2070. break;
  2071. clear_extent_dirty(&info->free_space_cache, start,
  2072. end, GFP_NOFS);
  2073. }
  2074. return 0;
  2075. }
  2076. static int noinline relocate_inode_pages(struct inode *inode, u64 start,
  2077. u64 len)
  2078. {
  2079. u64 page_start;
  2080. u64 page_end;
  2081. u64 delalloc_start;
  2082. u64 existing_delalloc;
  2083. unsigned long last_index;
  2084. unsigned long i;
  2085. struct page *page;
  2086. struct extent_io_tree *io_tree = &BTRFS_I(inode)->io_tree;
  2087. struct file_ra_state *ra;
  2088. ra = kzalloc(sizeof(*ra), GFP_NOFS);
  2089. mutex_lock(&inode->i_mutex);
  2090. i = start >> PAGE_CACHE_SHIFT;
  2091. last_index = (start + len - 1) >> PAGE_CACHE_SHIFT;
  2092. file_ra_state_init(ra, inode->i_mapping);
  2093. btrfs_force_ra(inode->i_mapping, ra, NULL, i, last_index);
  2094. kfree(ra);
  2095. for (; i <= last_index; i++) {
  2096. page = grab_cache_page(inode->i_mapping, i);
  2097. if (!page)
  2098. goto out_unlock;
  2099. if (!PageUptodate(page)) {
  2100. btrfs_readpage(NULL, page);
  2101. lock_page(page);
  2102. if (!PageUptodate(page)) {
  2103. unlock_page(page);
  2104. page_cache_release(page);
  2105. goto out_unlock;
  2106. }
  2107. }
  2108. page_start = (u64)page->index << PAGE_CACHE_SHIFT;
  2109. page_end = page_start + PAGE_CACHE_SIZE - 1;
  2110. lock_extent(io_tree, page_start, page_end, GFP_NOFS);
  2111. delalloc_start = page_start;
  2112. existing_delalloc = count_range_bits(io_tree,
  2113. &delalloc_start, page_end,
  2114. PAGE_CACHE_SIZE, EXTENT_DELALLOC);
  2115. set_extent_delalloc(io_tree, page_start,
  2116. page_end, GFP_NOFS);
  2117. unlock_extent(io_tree, page_start, page_end, GFP_NOFS);
  2118. set_page_dirty(page);
  2119. unlock_page(page);
  2120. page_cache_release(page);
  2121. }
  2122. out_unlock:
  2123. mutex_unlock(&inode->i_mutex);
  2124. return 0;
  2125. }
  2126. /*
  2127. * note, this releases the path
  2128. */
  2129. static int noinline relocate_one_reference(struct btrfs_root *extent_root,
  2130. struct btrfs_path *path,
  2131. struct btrfs_key *extent_key)
  2132. {
  2133. struct inode *inode;
  2134. struct btrfs_root *found_root;
  2135. struct btrfs_key *root_location;
  2136. struct btrfs_extent_ref *ref;
  2137. u64 ref_root;
  2138. u64 ref_gen;
  2139. u64 ref_objectid;
  2140. u64 ref_offset;
  2141. int ret;
  2142. ref = btrfs_item_ptr(path->nodes[0], path->slots[0],
  2143. struct btrfs_extent_ref);
  2144. ref_root = btrfs_ref_root(path->nodes[0], ref);
  2145. ref_gen = btrfs_ref_generation(path->nodes[0], ref);
  2146. ref_objectid = btrfs_ref_objectid(path->nodes[0], ref);
  2147. ref_offset = btrfs_ref_offset(path->nodes[0], ref);
  2148. btrfs_release_path(extent_root, path);
  2149. root_location = kmalloc(sizeof(*root_location), GFP_NOFS);
  2150. root_location->objectid = ref_root;
  2151. if (ref_gen == 0)
  2152. root_location->offset = 0;
  2153. else
  2154. root_location->offset = (u64)-1;
  2155. root_location->type = BTRFS_ROOT_ITEM_KEY;
  2156. found_root = btrfs_read_fs_root_no_name(extent_root->fs_info,
  2157. root_location);
  2158. BUG_ON(!found_root);
  2159. kfree(root_location);
  2160. if (ref_objectid >= BTRFS_FIRST_FREE_OBJECTID) {
  2161. mutex_unlock(&extent_root->fs_info->fs_mutex);
  2162. inode = btrfs_iget_locked(extent_root->fs_info->sb,
  2163. ref_objectid, found_root);
  2164. if (inode->i_state & I_NEW) {
  2165. /* the inode and parent dir are two different roots */
  2166. BTRFS_I(inode)->root = found_root;
  2167. BTRFS_I(inode)->location.objectid = ref_objectid;
  2168. BTRFS_I(inode)->location.type = BTRFS_INODE_ITEM_KEY;
  2169. BTRFS_I(inode)->location.offset = 0;
  2170. btrfs_read_locked_inode(inode);
  2171. unlock_new_inode(inode);
  2172. }
  2173. /* this can happen if the reference is not against
  2174. * the latest version of the tree root
  2175. */
  2176. if (is_bad_inode(inode)) {
  2177. mutex_lock(&extent_root->fs_info->fs_mutex);
  2178. goto out;
  2179. }
  2180. relocate_inode_pages(inode, ref_offset, extent_key->offset);
  2181. /* FIXME, data=ordered will help get rid of this */
  2182. filemap_fdatawrite(inode->i_mapping);
  2183. iput(inode);
  2184. mutex_lock(&extent_root->fs_info->fs_mutex);
  2185. } else {
  2186. struct btrfs_trans_handle *trans;
  2187. struct btrfs_key found_key;
  2188. struct extent_buffer *eb;
  2189. int level;
  2190. int i;
  2191. trans = btrfs_start_transaction(found_root, 1);
  2192. eb = read_tree_block(found_root, extent_key->objectid,
  2193. extent_key->offset);
  2194. level = btrfs_header_level(eb);
  2195. if (level == 0)
  2196. btrfs_item_key_to_cpu(eb, &found_key, 0);
  2197. else
  2198. btrfs_node_key_to_cpu(eb, &found_key, 0);
  2199. free_extent_buffer(eb);
  2200. path->lowest_level = level;
  2201. path->reada = 2;
  2202. ret = btrfs_search_slot(trans, found_root, &found_key, path,
  2203. 0, 1);
  2204. path->lowest_level = 0;
  2205. for (i = level; i < BTRFS_MAX_LEVEL; i++) {
  2206. if (!path->nodes[i])
  2207. break;
  2208. free_extent_buffer(path->nodes[i]);
  2209. path->nodes[i] = NULL;
  2210. }
  2211. btrfs_release_path(found_root, path);
  2212. btrfs_end_transaction(trans, found_root);
  2213. }
  2214. out:
  2215. return 0;
  2216. }
  2217. static int noinline relocate_one_extent(struct btrfs_root *extent_root,
  2218. struct btrfs_path *path,
  2219. struct btrfs_key *extent_key)
  2220. {
  2221. struct btrfs_key key;
  2222. struct btrfs_key found_key;
  2223. struct extent_buffer *leaf;
  2224. u32 nritems;
  2225. u32 item_size;
  2226. int ret = 0;
  2227. key.objectid = extent_key->objectid;
  2228. key.type = BTRFS_EXTENT_REF_KEY;
  2229. key.offset = 0;
  2230. while(1) {
  2231. ret = btrfs_search_slot(NULL, extent_root, &key, path, 0, 0);
  2232. if (ret < 0)
  2233. goto out;
  2234. ret = 0;
  2235. leaf = path->nodes[0];
  2236. nritems = btrfs_header_nritems(leaf);
  2237. if (path->slots[0] == nritems)
  2238. goto out;
  2239. btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
  2240. if (found_key.objectid != extent_key->objectid)
  2241. break;
  2242. if (found_key.type != BTRFS_EXTENT_REF_KEY)
  2243. break;
  2244. key.offset = found_key.offset + 1;
  2245. item_size = btrfs_item_size_nr(leaf, path->slots[0]);
  2246. ret = relocate_one_reference(extent_root, path, extent_key);
  2247. if (ret)
  2248. goto out;
  2249. }
  2250. ret = 0;
  2251. out:
  2252. btrfs_release_path(extent_root, path);
  2253. return ret;
  2254. }
  2255. int btrfs_shrink_extent_tree(struct btrfs_root *root, u64 new_size)
  2256. {
  2257. struct btrfs_trans_handle *trans;
  2258. struct btrfs_root *tree_root = root->fs_info->tree_root;
  2259. struct btrfs_path *path;
  2260. u64 cur_byte;
  2261. u64 total_found;
  2262. struct btrfs_fs_info *info = root->fs_info;
  2263. struct extent_io_tree *block_group_cache;
  2264. struct btrfs_key key;
  2265. struct btrfs_key found_key;
  2266. struct extent_buffer *leaf;
  2267. u32 nritems;
  2268. int ret;
  2269. int progress = 0;
  2270. btrfs_set_super_total_bytes(&info->super_copy, new_size);
  2271. clear_extent_dirty(&info->free_space_cache, new_size, (u64)-1,
  2272. GFP_NOFS);
  2273. block_group_cache = &info->block_group_cache;
  2274. path = btrfs_alloc_path();
  2275. root = root->fs_info->extent_root;
  2276. path->reada = 2;
  2277. again:
  2278. total_found = 0;
  2279. key.objectid = new_size;
  2280. key.offset = 0;
  2281. key.type = 0;
  2282. cur_byte = key.objectid;
  2283. ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
  2284. if (ret < 0)
  2285. goto out;
  2286. ret = btrfs_previous_item(root, path, 0, BTRFS_EXTENT_ITEM_KEY);
  2287. if (ret < 0)
  2288. goto out;
  2289. if (ret == 0) {
  2290. leaf = path->nodes[0];
  2291. btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
  2292. if (found_key.objectid + found_key.offset > new_size) {
  2293. cur_byte = found_key.objectid;
  2294. key.objectid = cur_byte;
  2295. }
  2296. }
  2297. btrfs_release_path(root, path);
  2298. while(1) {
  2299. ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
  2300. if (ret < 0)
  2301. goto out;
  2302. leaf = path->nodes[0];
  2303. nritems = btrfs_header_nritems(leaf);
  2304. next:
  2305. if (path->slots[0] >= nritems) {
  2306. ret = btrfs_next_leaf(root, path);
  2307. if (ret < 0)
  2308. goto out;
  2309. if (ret == 1) {
  2310. ret = 0;
  2311. break;
  2312. }
  2313. leaf = path->nodes[0];
  2314. nritems = btrfs_header_nritems(leaf);
  2315. }
  2316. btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
  2317. if (progress && need_resched()) {
  2318. memcpy(&key, &found_key, sizeof(key));
  2319. mutex_unlock(&root->fs_info->fs_mutex);
  2320. cond_resched();
  2321. mutex_lock(&root->fs_info->fs_mutex);
  2322. btrfs_release_path(root, path);
  2323. btrfs_search_slot(NULL, root, &key, path, 0, 0);
  2324. progress = 0;
  2325. goto next;
  2326. }
  2327. progress = 1;
  2328. if (btrfs_key_type(&found_key) != BTRFS_EXTENT_ITEM_KEY ||
  2329. found_key.objectid + found_key.offset <= cur_byte) {
  2330. path->slots[0]++;
  2331. goto next;
  2332. }
  2333. total_found++;
  2334. cur_byte = found_key.objectid + found_key.offset;
  2335. key.objectid = cur_byte;
  2336. btrfs_release_path(root, path);
  2337. ret = relocate_one_extent(root, path, &found_key);
  2338. }
  2339. btrfs_release_path(root, path);
  2340. if (total_found > 0) {
  2341. trans = btrfs_start_transaction(tree_root, 1);
  2342. btrfs_commit_transaction(trans, tree_root);
  2343. mutex_unlock(&root->fs_info->fs_mutex);
  2344. btrfs_clean_old_snapshots(tree_root);
  2345. mutex_lock(&root->fs_info->fs_mutex);
  2346. trans = btrfs_start_transaction(tree_root, 1);
  2347. btrfs_commit_transaction(trans, tree_root);
  2348. goto again;
  2349. }
  2350. trans = btrfs_start_transaction(root, 1);
  2351. key.objectid = new_size;
  2352. key.offset = 0;
  2353. key.type = 0;
  2354. while(1) {
  2355. u64 ptr;
  2356. ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
  2357. if (ret < 0)
  2358. goto out;
  2359. leaf = path->nodes[0];
  2360. nritems = btrfs_header_nritems(leaf);
  2361. bg_next:
  2362. if (path->slots[0] >= nritems) {
  2363. ret = btrfs_next_leaf(root, path);
  2364. if (ret < 0)
  2365. break;
  2366. if (ret == 1) {
  2367. ret = 0;
  2368. break;
  2369. }
  2370. leaf = path->nodes[0];
  2371. btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
  2372. /*
  2373. * btrfs_next_leaf doesn't cow buffers, we have to
  2374. * do the search again
  2375. */
  2376. memcpy(&key, &found_key, sizeof(key));
  2377. btrfs_release_path(root, path);
  2378. goto resched_check;
  2379. }
  2380. btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
  2381. if (btrfs_key_type(&found_key) != BTRFS_BLOCK_GROUP_ITEM_KEY) {
  2382. printk("shrinker found key %Lu %u %Lu\n",
  2383. found_key.objectid, found_key.type,
  2384. found_key.offset);
  2385. path->slots[0]++;
  2386. goto bg_next;
  2387. }
  2388. ret = get_state_private(&info->block_group_cache,
  2389. found_key.objectid, &ptr);
  2390. if (!ret)
  2391. kfree((void *)(unsigned long)ptr);
  2392. clear_extent_bits(&info->block_group_cache, found_key.objectid,
  2393. found_key.objectid + found_key.offset - 1,
  2394. (unsigned int)-1, GFP_NOFS);
  2395. key.objectid = found_key.objectid + 1;
  2396. btrfs_del_item(trans, root, path);
  2397. btrfs_release_path(root, path);
  2398. resched_check:
  2399. if (need_resched()) {
  2400. mutex_unlock(&root->fs_info->fs_mutex);
  2401. cond_resched();
  2402. mutex_lock(&root->fs_info->fs_mutex);
  2403. }
  2404. }
  2405. clear_extent_dirty(&info->free_space_cache, new_size, (u64)-1,
  2406. GFP_NOFS);
  2407. btrfs_commit_transaction(trans, root);
  2408. out:
  2409. btrfs_free_path(path);
  2410. return ret;
  2411. }
  2412. int btrfs_grow_extent_tree(struct btrfs_trans_handle *trans,
  2413. struct btrfs_root *root, u64 new_size)
  2414. {
  2415. btrfs_set_super_total_bytes(&root->fs_info->super_copy, new_size);
  2416. return 0;
  2417. }
  2418. int find_first_block_group(struct btrfs_root *root, struct btrfs_path *path,
  2419. struct btrfs_key *key)
  2420. {
  2421. int ret;
  2422. struct btrfs_key found_key;
  2423. struct extent_buffer *leaf;
  2424. int slot;
  2425. ret = btrfs_search_slot(NULL, root, key, path, 0, 0);
  2426. if (ret < 0)
  2427. return ret;
  2428. while(1) {
  2429. slot = path->slots[0];
  2430. leaf = path->nodes[0];
  2431. if (slot >= btrfs_header_nritems(leaf)) {
  2432. ret = btrfs_next_leaf(root, path);
  2433. if (ret == 0)
  2434. continue;
  2435. if (ret < 0)
  2436. goto error;
  2437. break;
  2438. }
  2439. btrfs_item_key_to_cpu(leaf, &found_key, slot);
  2440. if (found_key.objectid >= key->objectid &&
  2441. found_key.type == BTRFS_BLOCK_GROUP_ITEM_KEY)
  2442. return 0;
  2443. path->slots[0]++;
  2444. }
  2445. ret = -ENOENT;
  2446. error:
  2447. return ret;
  2448. }
  2449. int btrfs_read_block_groups(struct btrfs_root *root)
  2450. {
  2451. struct btrfs_path *path;
  2452. int ret;
  2453. int bit;
  2454. struct btrfs_block_group_cache *cache;
  2455. struct btrfs_fs_info *info = root->fs_info;
  2456. struct btrfs_space_info *space_info;
  2457. struct extent_io_tree *block_group_cache;
  2458. struct btrfs_key key;
  2459. struct btrfs_key found_key;
  2460. struct extent_buffer *leaf;
  2461. block_group_cache = &info->block_group_cache;
  2462. root = info->extent_root;
  2463. key.objectid = 0;
  2464. key.offset = 0;
  2465. btrfs_set_key_type(&key, BTRFS_BLOCK_GROUP_ITEM_KEY);
  2466. path = btrfs_alloc_path();
  2467. if (!path)
  2468. return -ENOMEM;
  2469. while(1) {
  2470. ret = find_first_block_group(root, path, &key);
  2471. if (ret > 0) {
  2472. ret = 0;
  2473. goto error;
  2474. }
  2475. if (ret != 0)
  2476. goto error;
  2477. leaf = path->nodes[0];
  2478. btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
  2479. cache = kmalloc(sizeof(*cache), GFP_NOFS);
  2480. if (!cache) {
  2481. ret = -ENOMEM;
  2482. break;
  2483. }
  2484. read_extent_buffer(leaf, &cache->item,
  2485. btrfs_item_ptr_offset(leaf, path->slots[0]),
  2486. sizeof(cache->item));
  2487. memcpy(&cache->key, &found_key, sizeof(found_key));
  2488. cache->cached = 0;
  2489. cache->pinned = 0;
  2490. key.objectid = found_key.objectid + found_key.offset;
  2491. btrfs_release_path(root, path);
  2492. cache->flags = btrfs_block_group_flags(&cache->item);
  2493. bit = 0;
  2494. if (cache->flags & BTRFS_BLOCK_GROUP_DATA) {
  2495. bit = BLOCK_GROUP_DATA;
  2496. } else if (cache->flags & BTRFS_BLOCK_GROUP_SYSTEM) {
  2497. bit = BLOCK_GROUP_SYSTEM;
  2498. } else if (cache->flags & BTRFS_BLOCK_GROUP_METADATA) {
  2499. bit = BLOCK_GROUP_METADATA;
  2500. }
  2501. set_avail_alloc_bits(info, cache->flags);
  2502. ret = update_space_info(info, cache->flags, found_key.offset,
  2503. btrfs_block_group_used(&cache->item),
  2504. &space_info);
  2505. BUG_ON(ret);
  2506. cache->space_info = space_info;
  2507. /* use EXTENT_LOCKED to prevent merging */
  2508. set_extent_bits(block_group_cache, found_key.objectid,
  2509. found_key.objectid + found_key.offset - 1,
  2510. bit | EXTENT_LOCKED, GFP_NOFS);
  2511. set_state_private(block_group_cache, found_key.objectid,
  2512. (unsigned long)cache);
  2513. if (key.objectid >=
  2514. btrfs_super_total_bytes(&info->super_copy))
  2515. break;
  2516. }
  2517. ret = 0;
  2518. error:
  2519. btrfs_free_path(path);
  2520. return ret;
  2521. }
  2522. int btrfs_make_block_group(struct btrfs_trans_handle *trans,
  2523. struct btrfs_root *root, u64 bytes_used,
  2524. u64 type, u64 chunk_tree, u64 chunk_objectid,
  2525. u64 size)
  2526. {
  2527. int ret;
  2528. int bit = 0;
  2529. struct btrfs_root *extent_root;
  2530. struct btrfs_block_group_cache *cache;
  2531. struct extent_io_tree *block_group_cache;
  2532. extent_root = root->fs_info->extent_root;
  2533. block_group_cache = &root->fs_info->block_group_cache;
  2534. cache = kmalloc(sizeof(*cache), GFP_NOFS);
  2535. BUG_ON(!cache);
  2536. cache->key.objectid = chunk_objectid;
  2537. cache->key.offset = size;
  2538. cache->cached = 0;
  2539. cache->pinned = 0;
  2540. btrfs_set_key_type(&cache->key, BTRFS_BLOCK_GROUP_ITEM_KEY);
  2541. memset(&cache->item, 0, sizeof(cache->item));
  2542. btrfs_set_block_group_used(&cache->item, bytes_used);
  2543. btrfs_set_block_group_chunk_tree(&cache->item, chunk_tree);
  2544. btrfs_set_block_group_chunk_objectid(&cache->item, chunk_objectid);
  2545. cache->flags = type;
  2546. btrfs_set_block_group_flags(&cache->item, type);
  2547. ret = update_space_info(root->fs_info, cache->flags, size, bytes_used,
  2548. &cache->space_info);
  2549. BUG_ON(ret);
  2550. bit = block_group_state_bits(type);
  2551. set_extent_bits(block_group_cache, chunk_objectid,
  2552. chunk_objectid + size - 1,
  2553. bit | EXTENT_LOCKED, GFP_NOFS);
  2554. set_state_private(block_group_cache, chunk_objectid,
  2555. (unsigned long)cache);
  2556. ret = btrfs_insert_item(trans, extent_root, &cache->key, &cache->item,
  2557. sizeof(cache->item));
  2558. BUG_ON(ret);
  2559. finish_current_insert(trans, extent_root);
  2560. ret = del_pending_extents(trans, extent_root);
  2561. BUG_ON(ret);
  2562. set_avail_alloc_bits(extent_root->fs_info, type);
  2563. return 0;
  2564. }