extent-tree.c 70 KB

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