extent-tree.c 80 KB

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