ctree.c 72 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768176917701771177217731774177517761777177817791780178117821783178417851786178717881789179017911792179317941795179617971798179918001801180218031804180518061807180818091810181118121813181418151816181718181819182018211822182318241825182618271828182918301831183218331834183518361837183818391840184118421843184418451846184718481849185018511852185318541855185618571858185918601861186218631864186518661867186818691870187118721873187418751876187718781879188018811882188318841885188618871888188918901891189218931894189518961897189818991900190119021903190419051906190719081909191019111912191319141915191619171918191919201921192219231924192519261927192819291930193119321933193419351936193719381939194019411942194319441945194619471948194919501951195219531954195519561957195819591960196119621963196419651966196719681969197019711972197319741975197619771978197919801981198219831984198519861987198819891990199119921993199419951996199719981999200020012002200320042005200620072008200920102011201220132014201520162017201820192020202120222023202420252026202720282029203020312032203320342035203620372038203920402041204220432044204520462047204820492050205120522053205420552056205720582059206020612062206320642065206620672068206920702071207220732074207520762077207820792080208120822083208420852086208720882089209020912092209320942095209620972098209921002101210221032104210521062107210821092110211121122113211421152116211721182119212021212122212321242125212621272128212921302131213221332134213521362137213821392140214121422143214421452146214721482149215021512152215321542155215621572158215921602161216221632164216521662167216821692170217121722173217421752176217721782179218021812182218321842185218621872188218921902191219221932194219521962197219821992200220122022203220422052206220722082209221022112212221322142215221622172218221922202221222222232224222522262227222822292230223122322233223422352236223722382239224022412242224322442245224622472248224922502251225222532254225522562257225822592260226122622263226422652266226722682269227022712272227322742275227622772278227922802281228222832284228522862287228822892290229122922293229422952296229722982299230023012302230323042305230623072308230923102311231223132314231523162317231823192320232123222323232423252326232723282329233023312332233323342335233623372338233923402341234223432344234523462347234823492350235123522353235423552356235723582359236023612362236323642365236623672368236923702371237223732374237523762377237823792380238123822383238423852386238723882389239023912392239323942395239623972398239924002401240224032404240524062407240824092410241124122413241424152416241724182419242024212422242324242425242624272428242924302431243224332434243524362437243824392440244124422443244424452446244724482449245024512452245324542455245624572458245924602461246224632464246524662467246824692470247124722473247424752476247724782479248024812482248324842485248624872488248924902491249224932494249524962497249824992500250125022503250425052506250725082509251025112512251325142515251625172518251925202521252225232524252525262527252825292530253125322533253425352536253725382539254025412542254325442545254625472548254925502551255225532554255525562557255825592560256125622563256425652566256725682569257025712572257325742575257625772578257925802581258225832584258525862587258825892590259125922593259425952596259725982599260026012602260326042605260626072608260926102611261226132614261526162617261826192620262126222623262426252626262726282629263026312632263326342635263626372638263926402641264226432644264526462647264826492650265126522653265426552656265726582659266026612662266326642665266626672668266926702671267226732674267526762677267826792680268126822683268426852686268726882689269026912692269326942695269626972698269927002701270227032704270527062707270827092710271127122713271427152716271727182719272027212722272327242725272627272728272927302731273227332734273527362737273827392740274127422743274427452746274727482749275027512752275327542755275627572758275927602761276227632764276527662767276827692770277127722773277427752776277727782779278027812782278327842785278627872788278927902791279227932794279527962797279827992800280128022803280428052806280728082809281028112812281328142815281628172818281928202821282228232824282528262827282828292830
  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 "ctree.h"
  20. #include "disk-io.h"
  21. #include "transaction.h"
  22. #include "print-tree.h"
  23. static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root
  24. *root, struct btrfs_path *path, int level);
  25. static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root
  26. *root, struct btrfs_key *ins_key,
  27. struct btrfs_path *path, int data_size, int extend);
  28. static int push_node_left(struct btrfs_trans_handle *trans,
  29. struct btrfs_root *root, struct extent_buffer *dst,
  30. struct extent_buffer *src);
  31. static int balance_node_right(struct btrfs_trans_handle *trans,
  32. struct btrfs_root *root,
  33. struct extent_buffer *dst_buf,
  34. struct extent_buffer *src_buf);
  35. static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root,
  36. struct btrfs_path *path, int level, int slot);
  37. inline void btrfs_init_path(struct btrfs_path *p)
  38. {
  39. memset(p, 0, sizeof(*p));
  40. }
  41. struct btrfs_path *btrfs_alloc_path(void)
  42. {
  43. struct btrfs_path *path;
  44. path = kmem_cache_alloc(btrfs_path_cachep, GFP_NOFS);
  45. if (path) {
  46. btrfs_init_path(path);
  47. path->reada = 1;
  48. }
  49. return path;
  50. }
  51. void btrfs_free_path(struct btrfs_path *p)
  52. {
  53. btrfs_release_path(NULL, p);
  54. kmem_cache_free(btrfs_path_cachep, p);
  55. }
  56. void btrfs_release_path(struct btrfs_root *root, struct btrfs_path *p)
  57. {
  58. int i;
  59. for (i = 0; i < BTRFS_MAX_LEVEL; i++) {
  60. if (!p->nodes[i])
  61. break;
  62. free_extent_buffer(p->nodes[i]);
  63. }
  64. memset(p, 0, sizeof(*p));
  65. }
  66. static void add_root_to_dirty_list(struct btrfs_root *root)
  67. {
  68. if (root->track_dirty && list_empty(&root->dirty_list)) {
  69. list_add(&root->dirty_list,
  70. &root->fs_info->dirty_cowonly_roots);
  71. }
  72. }
  73. int btrfs_copy_root(struct btrfs_trans_handle *trans,
  74. struct btrfs_root *root,
  75. struct extent_buffer *buf,
  76. struct extent_buffer **cow_ret, u64 new_root_objectid)
  77. {
  78. struct extent_buffer *cow;
  79. u32 nritems;
  80. int ret = 0;
  81. int level;
  82. struct btrfs_key first_key;
  83. struct btrfs_root *new_root;
  84. new_root = kmalloc(sizeof(*new_root), GFP_NOFS);
  85. if (!new_root)
  86. return -ENOMEM;
  87. memcpy(new_root, root, sizeof(*new_root));
  88. new_root->root_key.objectid = new_root_objectid;
  89. WARN_ON(root->ref_cows && trans->transid !=
  90. root->fs_info->running_transaction->transid);
  91. WARN_ON(root->ref_cows && trans->transid != root->last_trans);
  92. level = btrfs_header_level(buf);
  93. nritems = btrfs_header_nritems(buf);
  94. if (nritems) {
  95. if (level == 0)
  96. btrfs_item_key_to_cpu(buf, &first_key, 0);
  97. else
  98. btrfs_node_key_to_cpu(buf, &first_key, 0);
  99. } else {
  100. first_key.objectid = 0;
  101. }
  102. cow = __btrfs_alloc_free_block(trans, new_root, buf->len,
  103. new_root_objectid,
  104. trans->transid, first_key.objectid,
  105. level, buf->start, 0);
  106. if (IS_ERR(cow)) {
  107. kfree(new_root);
  108. return PTR_ERR(cow);
  109. }
  110. copy_extent_buffer(cow, buf, 0, 0, cow->len);
  111. btrfs_set_header_bytenr(cow, cow->start);
  112. btrfs_set_header_generation(cow, trans->transid);
  113. btrfs_set_header_owner(cow, new_root_objectid);
  114. btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN);
  115. WARN_ON(btrfs_header_generation(buf) > trans->transid);
  116. ret = btrfs_inc_ref(trans, new_root, buf);
  117. kfree(new_root);
  118. if (ret)
  119. return ret;
  120. btrfs_mark_buffer_dirty(cow);
  121. *cow_ret = cow;
  122. return 0;
  123. }
  124. int __btrfs_cow_block(struct btrfs_trans_handle *trans,
  125. struct btrfs_root *root,
  126. struct extent_buffer *buf,
  127. struct extent_buffer *parent, int parent_slot,
  128. struct extent_buffer **cow_ret,
  129. u64 search_start, u64 empty_size)
  130. {
  131. u64 root_gen;
  132. struct extent_buffer *cow;
  133. u32 nritems;
  134. int ret = 0;
  135. int different_trans = 0;
  136. int level;
  137. struct btrfs_key first_key;
  138. if (root->ref_cows) {
  139. root_gen = trans->transid;
  140. } else {
  141. root_gen = 0;
  142. }
  143. if (!(buf->flags & EXTENT_CSUM))
  144. WARN_ON(1);
  145. WARN_ON(root->ref_cows && trans->transid !=
  146. root->fs_info->running_transaction->transid);
  147. WARN_ON(root->ref_cows && trans->transid != root->last_trans);
  148. level = btrfs_header_level(buf);
  149. nritems = btrfs_header_nritems(buf);
  150. if (nritems) {
  151. if (level == 0)
  152. btrfs_item_key_to_cpu(buf, &first_key, 0);
  153. else
  154. btrfs_node_key_to_cpu(buf, &first_key, 0);
  155. } else {
  156. first_key.objectid = 0;
  157. }
  158. cow = __btrfs_alloc_free_block(trans, root, buf->len,
  159. root->root_key.objectid,
  160. root_gen, first_key.objectid, level,
  161. search_start, empty_size);
  162. if (IS_ERR(cow))
  163. return PTR_ERR(cow);
  164. copy_extent_buffer(cow, buf, 0, 0, cow->len);
  165. btrfs_set_header_bytenr(cow, cow->start);
  166. btrfs_set_header_generation(cow, trans->transid);
  167. btrfs_set_header_owner(cow, root->root_key.objectid);
  168. btrfs_clear_header_flag(cow, BTRFS_HEADER_FLAG_WRITTEN);
  169. WARN_ON(btrfs_header_generation(buf) > trans->transid);
  170. if (btrfs_header_generation(buf) != trans->transid) {
  171. different_trans = 1;
  172. ret = btrfs_inc_ref(trans, root, buf);
  173. if (ret)
  174. return ret;
  175. } else {
  176. clean_tree_block(trans, root, buf);
  177. }
  178. if (buf == root->node) {
  179. root_gen = btrfs_header_generation(buf);
  180. root->node = cow;
  181. extent_buffer_get(cow);
  182. if (buf != root->commit_root) {
  183. btrfs_free_extent(trans, root, buf->start,
  184. buf->len, root->root_key.objectid,
  185. root_gen, 0, 0, 1);
  186. }
  187. free_extent_buffer(buf);
  188. add_root_to_dirty_list(root);
  189. } else {
  190. root_gen = btrfs_header_generation(parent);
  191. btrfs_set_node_blockptr(parent, parent_slot,
  192. cow->start);
  193. WARN_ON(trans->transid == 0);
  194. btrfs_set_node_ptr_generation(parent, parent_slot,
  195. trans->transid);
  196. btrfs_mark_buffer_dirty(parent);
  197. WARN_ON(btrfs_header_generation(parent) != trans->transid);
  198. btrfs_free_extent(trans, root, buf->start, buf->len,
  199. btrfs_header_owner(parent), root_gen,
  200. 0, 0, 1);
  201. }
  202. free_extent_buffer(buf);
  203. btrfs_mark_buffer_dirty(cow);
  204. *cow_ret = cow;
  205. return 0;
  206. }
  207. int btrfs_cow_block(struct btrfs_trans_handle *trans,
  208. struct btrfs_root *root, struct extent_buffer *buf,
  209. struct extent_buffer *parent, int parent_slot,
  210. struct extent_buffer **cow_ret)
  211. {
  212. u64 search_start;
  213. u64 header_trans;
  214. int ret;
  215. if (trans->transaction != root->fs_info->running_transaction) {
  216. printk(KERN_CRIT "trans %Lu running %Lu\n", trans->transid,
  217. root->fs_info->running_transaction->transid);
  218. WARN_ON(1);
  219. }
  220. if (trans->transid != root->fs_info->generation) {
  221. printk(KERN_CRIT "trans %Lu running %Lu\n", trans->transid,
  222. root->fs_info->generation);
  223. WARN_ON(1);
  224. }
  225. if (!(buf->flags & EXTENT_CSUM))
  226. WARN_ON(1);
  227. header_trans = btrfs_header_generation(buf);
  228. spin_lock(&root->fs_info->hash_lock);
  229. if (header_trans == trans->transid &&
  230. !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_WRITTEN)) {
  231. *cow_ret = buf;
  232. spin_unlock(&root->fs_info->hash_lock);
  233. return 0;
  234. }
  235. spin_unlock(&root->fs_info->hash_lock);
  236. search_start = buf->start & ~((u64)(1024 * 1024 * 1024) - 1);
  237. ret = __btrfs_cow_block(trans, root, buf, parent,
  238. parent_slot, cow_ret, search_start, 0);
  239. return ret;
  240. }
  241. static int close_blocks(u64 blocknr, u64 other, u32 blocksize)
  242. {
  243. if (blocknr < other && other - (blocknr + blocksize) < 32768)
  244. return 1;
  245. if (blocknr > other && blocknr - (other + blocksize) < 32768)
  246. return 1;
  247. return 0;
  248. }
  249. /*
  250. * compare two keys in a memcmp fashion
  251. */
  252. static int comp_keys(struct btrfs_disk_key *disk, struct btrfs_key *k2)
  253. {
  254. struct btrfs_key k1;
  255. btrfs_disk_key_to_cpu(&k1, disk);
  256. if (k1.objectid > k2->objectid)
  257. return 1;
  258. if (k1.objectid < k2->objectid)
  259. return -1;
  260. if (k1.type > k2->type)
  261. return 1;
  262. if (k1.type < k2->type)
  263. return -1;
  264. if (k1.offset > k2->offset)
  265. return 1;
  266. if (k1.offset < k2->offset)
  267. return -1;
  268. return 0;
  269. }
  270. int btrfs_realloc_node(struct btrfs_trans_handle *trans,
  271. struct btrfs_root *root, struct extent_buffer *parent,
  272. int start_slot, int cache_only, u64 *last_ret,
  273. struct btrfs_key *progress)
  274. {
  275. struct extent_buffer *cur;
  276. struct extent_buffer *tmp;
  277. u64 blocknr;
  278. u64 search_start = *last_ret;
  279. u64 last_block = 0;
  280. u64 other;
  281. u32 parent_nritems;
  282. int end_slot;
  283. int i;
  284. int err = 0;
  285. int parent_level;
  286. int uptodate;
  287. u32 blocksize;
  288. int progress_passed = 0;
  289. struct btrfs_disk_key disk_key;
  290. parent_level = btrfs_header_level(parent);
  291. if (cache_only && parent_level != 1)
  292. return 0;
  293. if (trans->transaction != root->fs_info->running_transaction) {
  294. printk(KERN_CRIT "trans %Lu running %Lu\n", trans->transid,
  295. root->fs_info->running_transaction->transid);
  296. WARN_ON(1);
  297. }
  298. if (trans->transid != root->fs_info->generation) {
  299. printk(KERN_CRIT "trans %Lu running %Lu\n", trans->transid,
  300. root->fs_info->generation);
  301. WARN_ON(1);
  302. }
  303. parent_nritems = btrfs_header_nritems(parent);
  304. blocksize = btrfs_level_size(root, parent_level - 1);
  305. end_slot = parent_nritems;
  306. if (parent_nritems == 1)
  307. return 0;
  308. for (i = start_slot; i < end_slot; i++) {
  309. int close = 1;
  310. if (!parent->map_token) {
  311. map_extent_buffer(parent,
  312. btrfs_node_key_ptr_offset(i),
  313. sizeof(struct btrfs_key_ptr),
  314. &parent->map_token, &parent->kaddr,
  315. &parent->map_start, &parent->map_len,
  316. KM_USER1);
  317. }
  318. btrfs_node_key(parent, &disk_key, i);
  319. if (!progress_passed && comp_keys(&disk_key, progress) < 0)
  320. continue;
  321. progress_passed = 1;
  322. blocknr = btrfs_node_blockptr(parent, i);
  323. if (last_block == 0)
  324. last_block = blocknr;
  325. if (i > 0) {
  326. other = btrfs_node_blockptr(parent, i - 1);
  327. close = close_blocks(blocknr, other, blocksize);
  328. }
  329. if (close && i < end_slot - 2) {
  330. other = btrfs_node_blockptr(parent, i + 1);
  331. close = close_blocks(blocknr, other, blocksize);
  332. }
  333. if (close) {
  334. last_block = blocknr;
  335. continue;
  336. }
  337. if (parent->map_token) {
  338. unmap_extent_buffer(parent, parent->map_token,
  339. KM_USER1);
  340. parent->map_token = NULL;
  341. }
  342. cur = btrfs_find_tree_block(root, blocknr, blocksize);
  343. if (cur)
  344. uptodate = btrfs_buffer_uptodate(cur);
  345. else
  346. uptodate = 0;
  347. if (!cur || !uptodate) {
  348. if (cache_only) {
  349. free_extent_buffer(cur);
  350. continue;
  351. }
  352. if (!cur) {
  353. cur = read_tree_block(root, blocknr,
  354. blocksize);
  355. } else if (!uptodate) {
  356. btrfs_read_buffer(cur);
  357. }
  358. }
  359. if (search_start == 0)
  360. search_start = last_block;
  361. btrfs_verify_block_csum(root, cur);
  362. err = __btrfs_cow_block(trans, root, cur, parent, i,
  363. &tmp, search_start,
  364. min(16 * blocksize,
  365. (end_slot - i) * blocksize));
  366. if (err) {
  367. free_extent_buffer(cur);
  368. break;
  369. }
  370. search_start = tmp->start;
  371. last_block = tmp->start;
  372. *last_ret = search_start;
  373. if (parent_level == 1)
  374. btrfs_clear_buffer_defrag(tmp);
  375. free_extent_buffer(tmp);
  376. }
  377. if (parent->map_token) {
  378. unmap_extent_buffer(parent, parent->map_token,
  379. KM_USER1);
  380. parent->map_token = NULL;
  381. }
  382. return err;
  383. }
  384. /*
  385. * The leaf data grows from end-to-front in the node.
  386. * this returns the address of the start of the last item,
  387. * which is the stop of the leaf data stack
  388. */
  389. static inline unsigned int leaf_data_end(struct btrfs_root *root,
  390. struct extent_buffer *leaf)
  391. {
  392. u32 nr = btrfs_header_nritems(leaf);
  393. if (nr == 0)
  394. return BTRFS_LEAF_DATA_SIZE(root);
  395. return btrfs_item_offset_nr(leaf, nr - 1);
  396. }
  397. static int check_node(struct btrfs_root *root, struct btrfs_path *path,
  398. int level)
  399. {
  400. struct extent_buffer *parent = NULL;
  401. struct extent_buffer *node = path->nodes[level];
  402. struct btrfs_disk_key parent_key;
  403. struct btrfs_disk_key node_key;
  404. int parent_slot;
  405. int slot;
  406. struct btrfs_key cpukey;
  407. u32 nritems = btrfs_header_nritems(node);
  408. if (path->nodes[level + 1])
  409. parent = path->nodes[level + 1];
  410. slot = path->slots[level];
  411. BUG_ON(nritems == 0);
  412. if (parent) {
  413. parent_slot = path->slots[level + 1];
  414. btrfs_node_key(parent, &parent_key, parent_slot);
  415. btrfs_node_key(node, &node_key, 0);
  416. BUG_ON(memcmp(&parent_key, &node_key,
  417. sizeof(struct btrfs_disk_key)));
  418. BUG_ON(btrfs_node_blockptr(parent, parent_slot) !=
  419. btrfs_header_bytenr(node));
  420. }
  421. BUG_ON(nritems > BTRFS_NODEPTRS_PER_BLOCK(root));
  422. if (slot != 0) {
  423. btrfs_node_key_to_cpu(node, &cpukey, slot - 1);
  424. btrfs_node_key(node, &node_key, slot);
  425. BUG_ON(comp_keys(&node_key, &cpukey) <= 0);
  426. }
  427. if (slot < nritems - 1) {
  428. btrfs_node_key_to_cpu(node, &cpukey, slot + 1);
  429. btrfs_node_key(node, &node_key, slot);
  430. BUG_ON(comp_keys(&node_key, &cpukey) >= 0);
  431. }
  432. return 0;
  433. }
  434. static int check_leaf(struct btrfs_root *root, struct btrfs_path *path,
  435. int level)
  436. {
  437. struct extent_buffer *leaf = path->nodes[level];
  438. struct extent_buffer *parent = NULL;
  439. int parent_slot;
  440. struct btrfs_key cpukey;
  441. struct btrfs_disk_key parent_key;
  442. struct btrfs_disk_key leaf_key;
  443. int slot = path->slots[0];
  444. u32 nritems = btrfs_header_nritems(leaf);
  445. if (path->nodes[level + 1])
  446. parent = path->nodes[level + 1];
  447. if (nritems == 0)
  448. return 0;
  449. if (parent) {
  450. parent_slot = path->slots[level + 1];
  451. btrfs_node_key(parent, &parent_key, parent_slot);
  452. btrfs_item_key(leaf, &leaf_key, 0);
  453. BUG_ON(memcmp(&parent_key, &leaf_key,
  454. sizeof(struct btrfs_disk_key)));
  455. BUG_ON(btrfs_node_blockptr(parent, parent_slot) !=
  456. btrfs_header_bytenr(leaf));
  457. }
  458. #if 0
  459. for (i = 0; nritems > 1 && i < nritems - 2; i++) {
  460. btrfs_item_key_to_cpu(leaf, &cpukey, i + 1);
  461. btrfs_item_key(leaf, &leaf_key, i);
  462. if (comp_keys(&leaf_key, &cpukey) >= 0) {
  463. btrfs_print_leaf(root, leaf);
  464. printk("slot %d offset bad key\n", i);
  465. BUG_ON(1);
  466. }
  467. if (btrfs_item_offset_nr(leaf, i) !=
  468. btrfs_item_end_nr(leaf, i + 1)) {
  469. btrfs_print_leaf(root, leaf);
  470. printk("slot %d offset bad\n", i);
  471. BUG_ON(1);
  472. }
  473. if (i == 0) {
  474. if (btrfs_item_offset_nr(leaf, i) +
  475. btrfs_item_size_nr(leaf, i) !=
  476. BTRFS_LEAF_DATA_SIZE(root)) {
  477. btrfs_print_leaf(root, leaf);
  478. printk("slot %d first offset bad\n", i);
  479. BUG_ON(1);
  480. }
  481. }
  482. }
  483. if (nritems > 0) {
  484. if (btrfs_item_size_nr(leaf, nritems - 1) > 4096) {
  485. btrfs_print_leaf(root, leaf);
  486. printk("slot %d bad size \n", nritems - 1);
  487. BUG_ON(1);
  488. }
  489. }
  490. #endif
  491. if (slot != 0 && slot < nritems - 1) {
  492. btrfs_item_key(leaf, &leaf_key, slot);
  493. btrfs_item_key_to_cpu(leaf, &cpukey, slot - 1);
  494. if (comp_keys(&leaf_key, &cpukey) <= 0) {
  495. btrfs_print_leaf(root, leaf);
  496. printk("slot %d offset bad key\n", slot);
  497. BUG_ON(1);
  498. }
  499. if (btrfs_item_offset_nr(leaf, slot - 1) !=
  500. btrfs_item_end_nr(leaf, slot)) {
  501. btrfs_print_leaf(root, leaf);
  502. printk("slot %d offset bad\n", slot);
  503. BUG_ON(1);
  504. }
  505. }
  506. if (slot < nritems - 1) {
  507. btrfs_item_key(leaf, &leaf_key, slot);
  508. btrfs_item_key_to_cpu(leaf, &cpukey, slot + 1);
  509. BUG_ON(comp_keys(&leaf_key, &cpukey) >= 0);
  510. if (btrfs_item_offset_nr(leaf, slot) !=
  511. btrfs_item_end_nr(leaf, slot + 1)) {
  512. btrfs_print_leaf(root, leaf);
  513. printk("slot %d offset bad\n", slot);
  514. BUG_ON(1);
  515. }
  516. }
  517. BUG_ON(btrfs_item_offset_nr(leaf, 0) +
  518. btrfs_item_size_nr(leaf, 0) != BTRFS_LEAF_DATA_SIZE(root));
  519. return 0;
  520. }
  521. static int noinline check_block(struct btrfs_root *root,
  522. struct btrfs_path *path, int level)
  523. {
  524. return 0;
  525. #if 0
  526. struct extent_buffer *buf = path->nodes[level];
  527. if (memcmp_extent_buffer(buf, root->fs_info->fsid,
  528. (unsigned long)btrfs_header_fsid(buf),
  529. BTRFS_FSID_SIZE)) {
  530. printk("warning bad block %Lu\n", buf->start);
  531. return 1;
  532. }
  533. #endif
  534. if (level == 0)
  535. return check_leaf(root, path, level);
  536. return check_node(root, path, level);
  537. }
  538. /*
  539. * search for key in the extent_buffer. The items start at offset p,
  540. * and they are item_size apart. There are 'max' items in p.
  541. *
  542. * the slot in the array is returned via slot, and it points to
  543. * the place where you would insert key if it is not found in
  544. * the array.
  545. *
  546. * slot may point to max if the key is bigger than all of the keys
  547. */
  548. static int generic_bin_search(struct extent_buffer *eb, unsigned long p,
  549. int item_size, struct btrfs_key *key,
  550. int max, int *slot)
  551. {
  552. int low = 0;
  553. int high = max;
  554. int mid;
  555. int ret;
  556. struct btrfs_disk_key *tmp = NULL;
  557. struct btrfs_disk_key unaligned;
  558. unsigned long offset;
  559. char *map_token = NULL;
  560. char *kaddr = NULL;
  561. unsigned long map_start = 0;
  562. unsigned long map_len = 0;
  563. int err;
  564. while(low < high) {
  565. mid = (low + high) / 2;
  566. offset = p + mid * item_size;
  567. if (!map_token || offset < map_start ||
  568. (offset + sizeof(struct btrfs_disk_key)) >
  569. map_start + map_len) {
  570. if (map_token) {
  571. unmap_extent_buffer(eb, map_token, KM_USER0);
  572. map_token = NULL;
  573. }
  574. err = map_extent_buffer(eb, offset,
  575. sizeof(struct btrfs_disk_key),
  576. &map_token, &kaddr,
  577. &map_start, &map_len, KM_USER0);
  578. if (!err) {
  579. tmp = (struct btrfs_disk_key *)(kaddr + offset -
  580. map_start);
  581. } else {
  582. read_extent_buffer(eb, &unaligned,
  583. offset, sizeof(unaligned));
  584. tmp = &unaligned;
  585. }
  586. } else {
  587. tmp = (struct btrfs_disk_key *)(kaddr + offset -
  588. map_start);
  589. }
  590. ret = comp_keys(tmp, key);
  591. if (ret < 0)
  592. low = mid + 1;
  593. else if (ret > 0)
  594. high = mid;
  595. else {
  596. *slot = mid;
  597. if (map_token)
  598. unmap_extent_buffer(eb, map_token, KM_USER0);
  599. return 0;
  600. }
  601. }
  602. *slot = low;
  603. if (map_token)
  604. unmap_extent_buffer(eb, map_token, KM_USER0);
  605. return 1;
  606. }
  607. /*
  608. * simple bin_search frontend that does the right thing for
  609. * leaves vs nodes
  610. */
  611. static int bin_search(struct extent_buffer *eb, struct btrfs_key *key,
  612. int level, int *slot)
  613. {
  614. if (level == 0) {
  615. return generic_bin_search(eb,
  616. offsetof(struct btrfs_leaf, items),
  617. sizeof(struct btrfs_item),
  618. key, btrfs_header_nritems(eb),
  619. slot);
  620. } else {
  621. return generic_bin_search(eb,
  622. offsetof(struct btrfs_node, ptrs),
  623. sizeof(struct btrfs_key_ptr),
  624. key, btrfs_header_nritems(eb),
  625. slot);
  626. }
  627. return -1;
  628. }
  629. static struct extent_buffer *read_node_slot(struct btrfs_root *root,
  630. struct extent_buffer *parent, int slot)
  631. {
  632. if (slot < 0)
  633. return NULL;
  634. if (slot >= btrfs_header_nritems(parent))
  635. return NULL;
  636. return read_tree_block(root, btrfs_node_blockptr(parent, slot),
  637. btrfs_level_size(root, btrfs_header_level(parent) - 1));
  638. }
  639. static int balance_level(struct btrfs_trans_handle *trans,
  640. struct btrfs_root *root,
  641. struct btrfs_path *path, int level)
  642. {
  643. struct extent_buffer *right = NULL;
  644. struct extent_buffer *mid;
  645. struct extent_buffer *left = NULL;
  646. struct extent_buffer *parent = NULL;
  647. int ret = 0;
  648. int wret;
  649. int pslot;
  650. int orig_slot = path->slots[level];
  651. int err_on_enospc = 0;
  652. u64 orig_ptr;
  653. if (level == 0)
  654. return 0;
  655. mid = path->nodes[level];
  656. WARN_ON(btrfs_header_generation(mid) != trans->transid);
  657. orig_ptr = btrfs_node_blockptr(mid, orig_slot);
  658. if (level < BTRFS_MAX_LEVEL - 1)
  659. parent = path->nodes[level + 1];
  660. pslot = path->slots[level + 1];
  661. /*
  662. * deal with the case where there is only one pointer in the root
  663. * by promoting the node below to a root
  664. */
  665. if (!parent) {
  666. struct extent_buffer *child;
  667. if (btrfs_header_nritems(mid) != 1)
  668. return 0;
  669. /* promote the child to a root */
  670. child = read_node_slot(root, mid, 0);
  671. BUG_ON(!child);
  672. ret = btrfs_cow_block(trans, root, child, mid, 0, &child);
  673. BUG_ON(ret);
  674. root->node = child;
  675. add_root_to_dirty_list(root);
  676. path->nodes[level] = NULL;
  677. clean_tree_block(trans, root, mid);
  678. wait_on_tree_block_writeback(root, mid);
  679. /* once for the path */
  680. free_extent_buffer(mid);
  681. ret = btrfs_free_extent(trans, root, mid->start, mid->len,
  682. root->root_key.objectid,
  683. btrfs_header_generation(mid), 0, 0, 1);
  684. /* once for the root ptr */
  685. free_extent_buffer(mid);
  686. return ret;
  687. }
  688. if (btrfs_header_nritems(mid) >
  689. BTRFS_NODEPTRS_PER_BLOCK(root) / 4)
  690. return 0;
  691. if (btrfs_header_nritems(mid) < 2)
  692. err_on_enospc = 1;
  693. left = read_node_slot(root, parent, pslot - 1);
  694. if (left) {
  695. wret = btrfs_cow_block(trans, root, left,
  696. parent, pslot - 1, &left);
  697. if (wret) {
  698. ret = wret;
  699. goto enospc;
  700. }
  701. }
  702. right = read_node_slot(root, parent, pslot + 1);
  703. if (right) {
  704. wret = btrfs_cow_block(trans, root, right,
  705. parent, pslot + 1, &right);
  706. if (wret) {
  707. ret = wret;
  708. goto enospc;
  709. }
  710. }
  711. /* first, try to make some room in the middle buffer */
  712. if (left) {
  713. orig_slot += btrfs_header_nritems(left);
  714. wret = push_node_left(trans, root, left, mid);
  715. if (wret < 0)
  716. ret = wret;
  717. if (btrfs_header_nritems(mid) < 2)
  718. err_on_enospc = 1;
  719. }
  720. /*
  721. * then try to empty the right most buffer into the middle
  722. */
  723. if (right) {
  724. wret = push_node_left(trans, root, mid, right);
  725. if (wret < 0 && wret != -ENOSPC)
  726. ret = wret;
  727. if (btrfs_header_nritems(right) == 0) {
  728. u64 bytenr = right->start;
  729. u64 generation = btrfs_header_generation(parent);
  730. u32 blocksize = right->len;
  731. clean_tree_block(trans, root, right);
  732. wait_on_tree_block_writeback(root, right);
  733. free_extent_buffer(right);
  734. right = NULL;
  735. wret = del_ptr(trans, root, path, level + 1, pslot +
  736. 1);
  737. if (wret)
  738. ret = wret;
  739. wret = btrfs_free_extent(trans, root, bytenr,
  740. blocksize,
  741. btrfs_header_owner(parent),
  742. generation, 0, 0, 1);
  743. if (wret)
  744. ret = wret;
  745. } else {
  746. struct btrfs_disk_key right_key;
  747. btrfs_node_key(right, &right_key, 0);
  748. btrfs_set_node_key(parent, &right_key, pslot + 1);
  749. btrfs_mark_buffer_dirty(parent);
  750. }
  751. }
  752. if (btrfs_header_nritems(mid) == 1) {
  753. /*
  754. * we're not allowed to leave a node with one item in the
  755. * tree during a delete. A deletion from lower in the tree
  756. * could try to delete the only pointer in this node.
  757. * So, pull some keys from the left.
  758. * There has to be a left pointer at this point because
  759. * otherwise we would have pulled some pointers from the
  760. * right
  761. */
  762. BUG_ON(!left);
  763. wret = balance_node_right(trans, root, mid, left);
  764. if (wret < 0) {
  765. ret = wret;
  766. goto enospc;
  767. }
  768. BUG_ON(wret == 1);
  769. }
  770. if (btrfs_header_nritems(mid) == 0) {
  771. /* we've managed to empty the middle node, drop it */
  772. u64 root_gen = btrfs_header_generation(parent);
  773. u64 bytenr = mid->start;
  774. u32 blocksize = mid->len;
  775. clean_tree_block(trans, root, mid);
  776. wait_on_tree_block_writeback(root, mid);
  777. free_extent_buffer(mid);
  778. mid = NULL;
  779. wret = del_ptr(trans, root, path, level + 1, pslot);
  780. if (wret)
  781. ret = wret;
  782. wret = btrfs_free_extent(trans, root, bytenr, blocksize,
  783. btrfs_header_owner(parent),
  784. root_gen, 0, 0, 1);
  785. if (wret)
  786. ret = wret;
  787. } else {
  788. /* update the parent key to reflect our changes */
  789. struct btrfs_disk_key mid_key;
  790. btrfs_node_key(mid, &mid_key, 0);
  791. btrfs_set_node_key(parent, &mid_key, pslot);
  792. btrfs_mark_buffer_dirty(parent);
  793. }
  794. /* update the path */
  795. if (left) {
  796. if (btrfs_header_nritems(left) > orig_slot) {
  797. extent_buffer_get(left);
  798. path->nodes[level] = left;
  799. path->slots[level + 1] -= 1;
  800. path->slots[level] = orig_slot;
  801. if (mid)
  802. free_extent_buffer(mid);
  803. } else {
  804. orig_slot -= btrfs_header_nritems(left);
  805. path->slots[level] = orig_slot;
  806. }
  807. }
  808. /* double check we haven't messed things up */
  809. check_block(root, path, level);
  810. if (orig_ptr !=
  811. btrfs_node_blockptr(path->nodes[level], path->slots[level]))
  812. BUG();
  813. enospc:
  814. if (right)
  815. free_extent_buffer(right);
  816. if (left)
  817. free_extent_buffer(left);
  818. return ret;
  819. }
  820. /* returns zero if the push worked, non-zero otherwise */
  821. static int noinline push_nodes_for_insert(struct btrfs_trans_handle *trans,
  822. struct btrfs_root *root,
  823. struct btrfs_path *path, int level)
  824. {
  825. struct extent_buffer *right = NULL;
  826. struct extent_buffer *mid;
  827. struct extent_buffer *left = NULL;
  828. struct extent_buffer *parent = NULL;
  829. int ret = 0;
  830. int wret;
  831. int pslot;
  832. int orig_slot = path->slots[level];
  833. u64 orig_ptr;
  834. if (level == 0)
  835. return 1;
  836. mid = path->nodes[level];
  837. WARN_ON(btrfs_header_generation(mid) != trans->transid);
  838. orig_ptr = btrfs_node_blockptr(mid, orig_slot);
  839. if (level < BTRFS_MAX_LEVEL - 1)
  840. parent = path->nodes[level + 1];
  841. pslot = path->slots[level + 1];
  842. if (!parent)
  843. return 1;
  844. left = read_node_slot(root, parent, pslot - 1);
  845. /* first, try to make some room in the middle buffer */
  846. if (left) {
  847. u32 left_nr;
  848. left_nr = btrfs_header_nritems(left);
  849. if (left_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) {
  850. wret = 1;
  851. } else {
  852. ret = btrfs_cow_block(trans, root, left, parent,
  853. pslot - 1, &left);
  854. if (ret)
  855. wret = 1;
  856. else {
  857. wret = push_node_left(trans, root,
  858. left, mid);
  859. }
  860. }
  861. if (wret < 0)
  862. ret = wret;
  863. if (wret == 0) {
  864. struct btrfs_disk_key disk_key;
  865. orig_slot += left_nr;
  866. btrfs_node_key(mid, &disk_key, 0);
  867. btrfs_set_node_key(parent, &disk_key, pslot);
  868. btrfs_mark_buffer_dirty(parent);
  869. if (btrfs_header_nritems(left) > orig_slot) {
  870. path->nodes[level] = left;
  871. path->slots[level + 1] -= 1;
  872. path->slots[level] = orig_slot;
  873. free_extent_buffer(mid);
  874. } else {
  875. orig_slot -=
  876. btrfs_header_nritems(left);
  877. path->slots[level] = orig_slot;
  878. free_extent_buffer(left);
  879. }
  880. return 0;
  881. }
  882. free_extent_buffer(left);
  883. }
  884. right= read_node_slot(root, parent, pslot + 1);
  885. /*
  886. * then try to empty the right most buffer into the middle
  887. */
  888. if (right) {
  889. u32 right_nr;
  890. right_nr = btrfs_header_nritems(right);
  891. if (right_nr >= BTRFS_NODEPTRS_PER_BLOCK(root) - 1) {
  892. wret = 1;
  893. } else {
  894. ret = btrfs_cow_block(trans, root, right,
  895. parent, pslot + 1,
  896. &right);
  897. if (ret)
  898. wret = 1;
  899. else {
  900. wret = balance_node_right(trans, root,
  901. right, mid);
  902. }
  903. }
  904. if (wret < 0)
  905. ret = wret;
  906. if (wret == 0) {
  907. struct btrfs_disk_key disk_key;
  908. btrfs_node_key(right, &disk_key, 0);
  909. btrfs_set_node_key(parent, &disk_key, pslot + 1);
  910. btrfs_mark_buffer_dirty(parent);
  911. if (btrfs_header_nritems(mid) <= orig_slot) {
  912. path->nodes[level] = right;
  913. path->slots[level + 1] += 1;
  914. path->slots[level] = orig_slot -
  915. btrfs_header_nritems(mid);
  916. free_extent_buffer(mid);
  917. } else {
  918. free_extent_buffer(right);
  919. }
  920. return 0;
  921. }
  922. free_extent_buffer(right);
  923. }
  924. return 1;
  925. }
  926. /*
  927. * readahead one full node of leaves
  928. */
  929. static void reada_for_search(struct btrfs_root *root, struct btrfs_path *path,
  930. int level, int slot, u64 objectid)
  931. {
  932. struct extent_buffer *node;
  933. struct btrfs_disk_key disk_key;
  934. u32 nritems;
  935. u64 search;
  936. u64 lowest_read;
  937. u64 highest_read;
  938. u64 nread = 0;
  939. int direction = path->reada;
  940. struct extent_buffer *eb;
  941. u32 nr;
  942. u32 blocksize;
  943. u32 nscan = 0;
  944. if (level != 1)
  945. return;
  946. if (!path->nodes[level])
  947. return;
  948. node = path->nodes[level];
  949. search = btrfs_node_blockptr(node, slot);
  950. blocksize = btrfs_level_size(root, level - 1);
  951. eb = btrfs_find_tree_block(root, search, blocksize);
  952. if (eb) {
  953. free_extent_buffer(eb);
  954. return;
  955. }
  956. highest_read = search;
  957. lowest_read = search;
  958. nritems = btrfs_header_nritems(node);
  959. nr = slot;
  960. while(1) {
  961. if (direction < 0) {
  962. if (nr == 0)
  963. break;
  964. nr--;
  965. } else if (direction > 0) {
  966. nr++;
  967. if (nr >= nritems)
  968. break;
  969. }
  970. if (path->reada < 0 && objectid) {
  971. btrfs_node_key(node, &disk_key, nr);
  972. if (btrfs_disk_key_objectid(&disk_key) != objectid)
  973. break;
  974. }
  975. search = btrfs_node_blockptr(node, nr);
  976. if ((search >= lowest_read && search <= highest_read) ||
  977. (search < lowest_read && lowest_read - search <= 32768) ||
  978. (search > highest_read && search - highest_read <= 32768)) {
  979. readahead_tree_block(root, search, blocksize);
  980. nread += blocksize;
  981. }
  982. nscan++;
  983. if (path->reada < 2 && (nread > (256 * 1024) || nscan > 32))
  984. break;
  985. if(nread > (1024 * 1024) || nscan > 128)
  986. break;
  987. if (search < lowest_read)
  988. lowest_read = search;
  989. if (search > highest_read)
  990. highest_read = search;
  991. }
  992. }
  993. /*
  994. * look for key in the tree. path is filled in with nodes along the way
  995. * if key is found, we return zero and you can find the item in the leaf
  996. * level of the path (level 0)
  997. *
  998. * If the key isn't found, the path points to the slot where it should
  999. * be inserted, and 1 is returned. If there are other errors during the
  1000. * search a negative error number is returned.
  1001. *
  1002. * if ins_len > 0, nodes and leaves will be split as we walk down the
  1003. * tree. if ins_len < 0, nodes will be merged as we walk down the tree (if
  1004. * possible)
  1005. */
  1006. int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root
  1007. *root, struct btrfs_key *key, struct btrfs_path *p, int
  1008. ins_len, int cow)
  1009. {
  1010. struct extent_buffer *b;
  1011. u64 bytenr;
  1012. u64 ptr_gen;
  1013. int slot;
  1014. int ret;
  1015. int level;
  1016. int should_reada = p->reada;
  1017. u8 lowest_level = 0;
  1018. lowest_level = p->lowest_level;
  1019. WARN_ON(lowest_level && ins_len);
  1020. WARN_ON(p->nodes[0] != NULL);
  1021. WARN_ON(!mutex_is_locked(&root->fs_info->fs_mutex));
  1022. again:
  1023. b = root->node;
  1024. extent_buffer_get(b);
  1025. while (b) {
  1026. level = btrfs_header_level(b);
  1027. if (cow) {
  1028. int wret;
  1029. wret = btrfs_cow_block(trans, root, b,
  1030. p->nodes[level + 1],
  1031. p->slots[level + 1],
  1032. &b);
  1033. if (wret) {
  1034. free_extent_buffer(b);
  1035. return wret;
  1036. }
  1037. }
  1038. BUG_ON(!cow && ins_len);
  1039. if (level != btrfs_header_level(b))
  1040. WARN_ON(1);
  1041. level = btrfs_header_level(b);
  1042. p->nodes[level] = b;
  1043. ret = check_block(root, p, level);
  1044. if (ret)
  1045. return -1;
  1046. ret = bin_search(b, key, level, &slot);
  1047. if (level != 0) {
  1048. if (ret && slot > 0)
  1049. slot -= 1;
  1050. p->slots[level] = slot;
  1051. if (ins_len > 0 && btrfs_header_nritems(b) >=
  1052. BTRFS_NODEPTRS_PER_BLOCK(root) - 1) {
  1053. int sret = split_node(trans, root, p, level);
  1054. BUG_ON(sret > 0);
  1055. if (sret)
  1056. return sret;
  1057. b = p->nodes[level];
  1058. slot = p->slots[level];
  1059. } else if (ins_len < 0) {
  1060. int sret = balance_level(trans, root, p,
  1061. level);
  1062. if (sret)
  1063. return sret;
  1064. b = p->nodes[level];
  1065. if (!b) {
  1066. btrfs_release_path(NULL, p);
  1067. goto again;
  1068. }
  1069. slot = p->slots[level];
  1070. BUG_ON(btrfs_header_nritems(b) == 1);
  1071. }
  1072. /* this is only true while dropping a snapshot */
  1073. if (level == lowest_level)
  1074. break;
  1075. bytenr = btrfs_node_blockptr(b, slot);
  1076. ptr_gen = btrfs_node_ptr_generation(b, slot);
  1077. if (should_reada)
  1078. reada_for_search(root, p, level, slot,
  1079. key->objectid);
  1080. b = read_tree_block(root, bytenr,
  1081. btrfs_level_size(root, level - 1));
  1082. if (ptr_gen != btrfs_header_generation(b)) {
  1083. printk("block %llu bad gen wanted %llu "
  1084. "found %llu\n",
  1085. (unsigned long long)b->start,
  1086. (unsigned long long)ptr_gen,
  1087. (unsigned long long)btrfs_header_generation(b));
  1088. }
  1089. } else {
  1090. p->slots[level] = slot;
  1091. if (ins_len > 0 && btrfs_leaf_free_space(root, b) <
  1092. sizeof(struct btrfs_item) + ins_len) {
  1093. int sret = split_leaf(trans, root, key,
  1094. p, ins_len, ret == 0);
  1095. BUG_ON(sret > 0);
  1096. if (sret)
  1097. return sret;
  1098. }
  1099. return ret;
  1100. }
  1101. }
  1102. return 1;
  1103. }
  1104. /*
  1105. * adjust the pointers going up the tree, starting at level
  1106. * making sure the right key of each node is points to 'key'.
  1107. * This is used after shifting pointers to the left, so it stops
  1108. * fixing up pointers when a given leaf/node is not in slot 0 of the
  1109. * higher levels
  1110. *
  1111. * If this fails to write a tree block, it returns -1, but continues
  1112. * fixing up the blocks in ram so the tree is consistent.
  1113. */
  1114. static int fixup_low_keys(struct btrfs_trans_handle *trans,
  1115. struct btrfs_root *root, struct btrfs_path *path,
  1116. struct btrfs_disk_key *key, int level)
  1117. {
  1118. int i;
  1119. int ret = 0;
  1120. struct extent_buffer *t;
  1121. for (i = level; i < BTRFS_MAX_LEVEL; i++) {
  1122. int tslot = path->slots[i];
  1123. if (!path->nodes[i])
  1124. break;
  1125. t = path->nodes[i];
  1126. btrfs_set_node_key(t, key, tslot);
  1127. btrfs_mark_buffer_dirty(path->nodes[i]);
  1128. if (tslot != 0)
  1129. break;
  1130. }
  1131. return ret;
  1132. }
  1133. /*
  1134. * try to push data from one node into the next node left in the
  1135. * tree.
  1136. *
  1137. * returns 0 if some ptrs were pushed left, < 0 if there was some horrible
  1138. * error, and > 0 if there was no room in the left hand block.
  1139. */
  1140. static int push_node_left(struct btrfs_trans_handle *trans,
  1141. struct btrfs_root *root, struct extent_buffer *dst,
  1142. struct extent_buffer *src)
  1143. {
  1144. int push_items = 0;
  1145. int src_nritems;
  1146. int dst_nritems;
  1147. int ret = 0;
  1148. src_nritems = btrfs_header_nritems(src);
  1149. dst_nritems = btrfs_header_nritems(dst);
  1150. push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems;
  1151. WARN_ON(btrfs_header_generation(src) != trans->transid);
  1152. WARN_ON(btrfs_header_generation(dst) != trans->transid);
  1153. if (push_items <= 0) {
  1154. return 1;
  1155. }
  1156. if (src_nritems < push_items)
  1157. push_items = src_nritems;
  1158. copy_extent_buffer(dst, src,
  1159. btrfs_node_key_ptr_offset(dst_nritems),
  1160. btrfs_node_key_ptr_offset(0),
  1161. push_items * sizeof(struct btrfs_key_ptr));
  1162. if (push_items < src_nritems) {
  1163. memmove_extent_buffer(src, btrfs_node_key_ptr_offset(0),
  1164. btrfs_node_key_ptr_offset(push_items),
  1165. (src_nritems - push_items) *
  1166. sizeof(struct btrfs_key_ptr));
  1167. }
  1168. btrfs_set_header_nritems(src, src_nritems - push_items);
  1169. btrfs_set_header_nritems(dst, dst_nritems + push_items);
  1170. btrfs_mark_buffer_dirty(src);
  1171. btrfs_mark_buffer_dirty(dst);
  1172. return ret;
  1173. }
  1174. /*
  1175. * try to push data from one node into the next node right in the
  1176. * tree.
  1177. *
  1178. * returns 0 if some ptrs were pushed, < 0 if there was some horrible
  1179. * error, and > 0 if there was no room in the right hand block.
  1180. *
  1181. * this will only push up to 1/2 the contents of the left node over
  1182. */
  1183. static int balance_node_right(struct btrfs_trans_handle *trans,
  1184. struct btrfs_root *root,
  1185. struct extent_buffer *dst,
  1186. struct extent_buffer *src)
  1187. {
  1188. int push_items = 0;
  1189. int max_push;
  1190. int src_nritems;
  1191. int dst_nritems;
  1192. int ret = 0;
  1193. WARN_ON(btrfs_header_generation(src) != trans->transid);
  1194. WARN_ON(btrfs_header_generation(dst) != trans->transid);
  1195. src_nritems = btrfs_header_nritems(src);
  1196. dst_nritems = btrfs_header_nritems(dst);
  1197. push_items = BTRFS_NODEPTRS_PER_BLOCK(root) - dst_nritems;
  1198. if (push_items <= 0)
  1199. return 1;
  1200. max_push = src_nritems / 2 + 1;
  1201. /* don't try to empty the node */
  1202. if (max_push >= src_nritems)
  1203. return 1;
  1204. if (max_push < push_items)
  1205. push_items = max_push;
  1206. memmove_extent_buffer(dst, btrfs_node_key_ptr_offset(push_items),
  1207. btrfs_node_key_ptr_offset(0),
  1208. (dst_nritems) *
  1209. sizeof(struct btrfs_key_ptr));
  1210. copy_extent_buffer(dst, src,
  1211. btrfs_node_key_ptr_offset(0),
  1212. btrfs_node_key_ptr_offset(src_nritems - push_items),
  1213. push_items * sizeof(struct btrfs_key_ptr));
  1214. btrfs_set_header_nritems(src, src_nritems - push_items);
  1215. btrfs_set_header_nritems(dst, dst_nritems + push_items);
  1216. btrfs_mark_buffer_dirty(src);
  1217. btrfs_mark_buffer_dirty(dst);
  1218. return ret;
  1219. }
  1220. /*
  1221. * helper function to insert a new root level in the tree.
  1222. * A new node is allocated, and a single item is inserted to
  1223. * point to the existing root
  1224. *
  1225. * returns zero on success or < 0 on failure.
  1226. */
  1227. static int noinline insert_new_root(struct btrfs_trans_handle *trans,
  1228. struct btrfs_root *root,
  1229. struct btrfs_path *path, int level)
  1230. {
  1231. u64 root_gen;
  1232. u64 lower_gen;
  1233. struct extent_buffer *lower;
  1234. struct extent_buffer *c;
  1235. struct btrfs_disk_key lower_key;
  1236. BUG_ON(path->nodes[level]);
  1237. BUG_ON(path->nodes[level-1] != root->node);
  1238. if (root->ref_cows)
  1239. root_gen = trans->transid;
  1240. else
  1241. root_gen = 0;
  1242. lower = path->nodes[level-1];
  1243. if (level == 1)
  1244. btrfs_item_key(lower, &lower_key, 0);
  1245. else
  1246. btrfs_node_key(lower, &lower_key, 0);
  1247. c = __btrfs_alloc_free_block(trans, root, root->nodesize,
  1248. root->root_key.objectid,
  1249. root_gen, lower_key.objectid, level,
  1250. root->node->start, 0);
  1251. if (IS_ERR(c))
  1252. return PTR_ERR(c);
  1253. memset_extent_buffer(c, 0, 0, root->nodesize);
  1254. btrfs_set_header_nritems(c, 1);
  1255. btrfs_set_header_level(c, level);
  1256. btrfs_set_header_bytenr(c, c->start);
  1257. btrfs_set_header_generation(c, trans->transid);
  1258. btrfs_set_header_owner(c, root->root_key.objectid);
  1259. write_extent_buffer(c, root->fs_info->fsid,
  1260. (unsigned long)btrfs_header_fsid(c),
  1261. BTRFS_FSID_SIZE);
  1262. btrfs_set_node_key(c, &lower_key, 0);
  1263. btrfs_set_node_blockptr(c, 0, lower->start);
  1264. lower_gen = btrfs_header_generation(lower);
  1265. WARN_ON(lower_gen == 0);
  1266. btrfs_set_node_ptr_generation(c, 0, lower_gen);
  1267. btrfs_mark_buffer_dirty(c);
  1268. /* the super has an extra ref to root->node */
  1269. free_extent_buffer(root->node);
  1270. root->node = c;
  1271. add_root_to_dirty_list(root);
  1272. extent_buffer_get(c);
  1273. path->nodes[level] = c;
  1274. path->slots[level] = 0;
  1275. if (root->ref_cows && lower_gen != trans->transid) {
  1276. struct btrfs_path *back_path = btrfs_alloc_path();
  1277. int ret;
  1278. ret = btrfs_insert_extent_backref(trans,
  1279. root->fs_info->extent_root,
  1280. path, lower->start,
  1281. root->root_key.objectid,
  1282. trans->transid, 0, 0);
  1283. BUG_ON(ret);
  1284. btrfs_free_path(back_path);
  1285. }
  1286. return 0;
  1287. }
  1288. /*
  1289. * worker function to insert a single pointer in a node.
  1290. * the node should have enough room for the pointer already
  1291. *
  1292. * slot and level indicate where you want the key to go, and
  1293. * blocknr is the block the key points to.
  1294. *
  1295. * returns zero on success and < 0 on any error
  1296. */
  1297. static int insert_ptr(struct btrfs_trans_handle *trans, struct btrfs_root
  1298. *root, struct btrfs_path *path, struct btrfs_disk_key
  1299. *key, u64 bytenr, int slot, int level)
  1300. {
  1301. struct extent_buffer *lower;
  1302. int nritems;
  1303. BUG_ON(!path->nodes[level]);
  1304. lower = path->nodes[level];
  1305. nritems = btrfs_header_nritems(lower);
  1306. if (slot > nritems)
  1307. BUG();
  1308. if (nritems == BTRFS_NODEPTRS_PER_BLOCK(root))
  1309. BUG();
  1310. if (slot != nritems) {
  1311. memmove_extent_buffer(lower,
  1312. btrfs_node_key_ptr_offset(slot + 1),
  1313. btrfs_node_key_ptr_offset(slot),
  1314. (nritems - slot) * sizeof(struct btrfs_key_ptr));
  1315. }
  1316. btrfs_set_node_key(lower, key, slot);
  1317. btrfs_set_node_blockptr(lower, slot, bytenr);
  1318. WARN_ON(trans->transid == 0);
  1319. btrfs_set_node_ptr_generation(lower, slot, trans->transid);
  1320. btrfs_set_header_nritems(lower, nritems + 1);
  1321. btrfs_mark_buffer_dirty(lower);
  1322. return 0;
  1323. }
  1324. /*
  1325. * split the node at the specified level in path in two.
  1326. * The path is corrected to point to the appropriate node after the split
  1327. *
  1328. * Before splitting this tries to make some room in the node by pushing
  1329. * left and right, if either one works, it returns right away.
  1330. *
  1331. * returns 0 on success and < 0 on failure
  1332. */
  1333. static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root
  1334. *root, struct btrfs_path *path, int level)
  1335. {
  1336. u64 root_gen;
  1337. struct extent_buffer *c;
  1338. struct extent_buffer *split;
  1339. struct btrfs_disk_key disk_key;
  1340. int mid;
  1341. int ret;
  1342. int wret;
  1343. u32 c_nritems;
  1344. c = path->nodes[level];
  1345. WARN_ON(btrfs_header_generation(c) != trans->transid);
  1346. if (c == root->node) {
  1347. /* trying to split the root, lets make a new one */
  1348. ret = insert_new_root(trans, root, path, level + 1);
  1349. if (ret)
  1350. return ret;
  1351. } else {
  1352. ret = push_nodes_for_insert(trans, root, path, level);
  1353. c = path->nodes[level];
  1354. if (!ret && btrfs_header_nritems(c) <
  1355. BTRFS_NODEPTRS_PER_BLOCK(root) - 1)
  1356. return 0;
  1357. if (ret < 0)
  1358. return ret;
  1359. }
  1360. c_nritems = btrfs_header_nritems(c);
  1361. if (root->ref_cows)
  1362. root_gen = trans->transid;
  1363. else
  1364. root_gen = 0;
  1365. btrfs_node_key(c, &disk_key, 0);
  1366. split = __btrfs_alloc_free_block(trans, root, root->nodesize,
  1367. root->root_key.objectid,
  1368. root_gen,
  1369. btrfs_disk_key_objectid(&disk_key),
  1370. level, c->start, 0);
  1371. if (IS_ERR(split))
  1372. return PTR_ERR(split);
  1373. btrfs_set_header_flags(split, btrfs_header_flags(c));
  1374. btrfs_set_header_level(split, btrfs_header_level(c));
  1375. btrfs_set_header_bytenr(split, split->start);
  1376. btrfs_set_header_generation(split, trans->transid);
  1377. btrfs_set_header_owner(split, root->root_key.objectid);
  1378. btrfs_set_header_flags(split, 0);
  1379. write_extent_buffer(split, root->fs_info->fsid,
  1380. (unsigned long)btrfs_header_fsid(split),
  1381. BTRFS_FSID_SIZE);
  1382. mid = (c_nritems + 1) / 2;
  1383. copy_extent_buffer(split, c,
  1384. btrfs_node_key_ptr_offset(0),
  1385. btrfs_node_key_ptr_offset(mid),
  1386. (c_nritems - mid) * sizeof(struct btrfs_key_ptr));
  1387. btrfs_set_header_nritems(split, c_nritems - mid);
  1388. btrfs_set_header_nritems(c, mid);
  1389. ret = 0;
  1390. btrfs_mark_buffer_dirty(c);
  1391. btrfs_mark_buffer_dirty(split);
  1392. btrfs_node_key(split, &disk_key, 0);
  1393. wret = insert_ptr(trans, root, path, &disk_key, split->start,
  1394. path->slots[level + 1] + 1,
  1395. level + 1);
  1396. if (wret)
  1397. ret = wret;
  1398. if (path->slots[level] >= mid) {
  1399. path->slots[level] -= mid;
  1400. free_extent_buffer(c);
  1401. path->nodes[level] = split;
  1402. path->slots[level + 1] += 1;
  1403. } else {
  1404. free_extent_buffer(split);
  1405. }
  1406. return ret;
  1407. }
  1408. /*
  1409. * how many bytes are required to store the items in a leaf. start
  1410. * and nr indicate which items in the leaf to check. This totals up the
  1411. * space used both by the item structs and the item data
  1412. */
  1413. static int leaf_space_used(struct extent_buffer *l, int start, int nr)
  1414. {
  1415. int data_len;
  1416. int nritems = btrfs_header_nritems(l);
  1417. int end = min(nritems, start + nr) - 1;
  1418. if (!nr)
  1419. return 0;
  1420. data_len = btrfs_item_end_nr(l, start);
  1421. data_len = data_len - btrfs_item_offset_nr(l, end);
  1422. data_len += sizeof(struct btrfs_item) * nr;
  1423. WARN_ON(data_len < 0);
  1424. return data_len;
  1425. }
  1426. /*
  1427. * The space between the end of the leaf items and
  1428. * the start of the leaf data. IOW, how much room
  1429. * the leaf has left for both items and data
  1430. */
  1431. int btrfs_leaf_free_space(struct btrfs_root *root, struct extent_buffer *leaf)
  1432. {
  1433. int nritems = btrfs_header_nritems(leaf);
  1434. int ret;
  1435. ret = BTRFS_LEAF_DATA_SIZE(root) - leaf_space_used(leaf, 0, nritems);
  1436. if (ret < 0) {
  1437. printk("leaf free space ret %d, leaf data size %lu, used %d nritems %d\n",
  1438. ret, (unsigned long) BTRFS_LEAF_DATA_SIZE(root),
  1439. leaf_space_used(leaf, 0, nritems), nritems);
  1440. }
  1441. return ret;
  1442. }
  1443. /*
  1444. * push some data in the path leaf to the right, trying to free up at
  1445. * least data_size bytes. returns zero if the push worked, nonzero otherwise
  1446. *
  1447. * returns 1 if the push failed because the other node didn't have enough
  1448. * room, 0 if everything worked out and < 0 if there were major errors.
  1449. */
  1450. static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root
  1451. *root, struct btrfs_path *path, int data_size,
  1452. int empty)
  1453. {
  1454. struct extent_buffer *left = path->nodes[0];
  1455. struct extent_buffer *right;
  1456. struct extent_buffer *upper;
  1457. struct btrfs_disk_key disk_key;
  1458. int slot;
  1459. u32 i;
  1460. int free_space;
  1461. int push_space = 0;
  1462. int push_items = 0;
  1463. struct btrfs_item *item;
  1464. u32 left_nritems;
  1465. u32 nr;
  1466. u32 right_nritems;
  1467. u32 data_end;
  1468. u32 this_item_size;
  1469. int ret;
  1470. slot = path->slots[1];
  1471. if (!path->nodes[1]) {
  1472. return 1;
  1473. }
  1474. upper = path->nodes[1];
  1475. if (slot >= btrfs_header_nritems(upper) - 1)
  1476. return 1;
  1477. right = read_tree_block(root, btrfs_node_blockptr(upper, slot + 1),
  1478. root->leafsize);
  1479. free_space = btrfs_leaf_free_space(root, right);
  1480. if (free_space < data_size + sizeof(struct btrfs_item)) {
  1481. free_extent_buffer(right);
  1482. return 1;
  1483. }
  1484. /* cow and double check */
  1485. ret = btrfs_cow_block(trans, root, right, upper,
  1486. slot + 1, &right);
  1487. if (ret) {
  1488. free_extent_buffer(right);
  1489. return 1;
  1490. }
  1491. free_space = btrfs_leaf_free_space(root, right);
  1492. if (free_space < data_size + sizeof(struct btrfs_item)) {
  1493. free_extent_buffer(right);
  1494. return 1;
  1495. }
  1496. left_nritems = btrfs_header_nritems(left);
  1497. if (left_nritems == 0) {
  1498. free_extent_buffer(right);
  1499. return 1;
  1500. }
  1501. if (empty)
  1502. nr = 0;
  1503. else
  1504. nr = 1;
  1505. i = left_nritems - 1;
  1506. while (i >= nr) {
  1507. item = btrfs_item_nr(left, i);
  1508. if (path->slots[0] == i)
  1509. push_space += data_size + sizeof(*item);
  1510. if (!left->map_token) {
  1511. map_extent_buffer(left, (unsigned long)item,
  1512. sizeof(struct btrfs_item),
  1513. &left->map_token, &left->kaddr,
  1514. &left->map_start, &left->map_len,
  1515. KM_USER1);
  1516. }
  1517. this_item_size = btrfs_item_size(left, item);
  1518. if (this_item_size + sizeof(*item) + push_space > free_space)
  1519. break;
  1520. push_items++;
  1521. push_space += this_item_size + sizeof(*item);
  1522. if (i == 0)
  1523. break;
  1524. i--;
  1525. }
  1526. if (left->map_token) {
  1527. unmap_extent_buffer(left, left->map_token, KM_USER1);
  1528. left->map_token = NULL;
  1529. }
  1530. if (push_items == 0) {
  1531. free_extent_buffer(right);
  1532. return 1;
  1533. }
  1534. if (!empty && push_items == left_nritems)
  1535. WARN_ON(1);
  1536. /* push left to right */
  1537. right_nritems = btrfs_header_nritems(right);
  1538. push_space = btrfs_item_end_nr(left, left_nritems - push_items);
  1539. push_space -= leaf_data_end(root, left);
  1540. /* make room in the right data area */
  1541. data_end = leaf_data_end(root, right);
  1542. memmove_extent_buffer(right,
  1543. btrfs_leaf_data(right) + data_end - push_space,
  1544. btrfs_leaf_data(right) + data_end,
  1545. BTRFS_LEAF_DATA_SIZE(root) - data_end);
  1546. /* copy from the left data area */
  1547. copy_extent_buffer(right, left, btrfs_leaf_data(right) +
  1548. BTRFS_LEAF_DATA_SIZE(root) - push_space,
  1549. btrfs_leaf_data(left) + leaf_data_end(root, left),
  1550. push_space);
  1551. memmove_extent_buffer(right, btrfs_item_nr_offset(push_items),
  1552. btrfs_item_nr_offset(0),
  1553. right_nritems * sizeof(struct btrfs_item));
  1554. /* copy the items from left to right */
  1555. copy_extent_buffer(right, left, btrfs_item_nr_offset(0),
  1556. btrfs_item_nr_offset(left_nritems - push_items),
  1557. push_items * sizeof(struct btrfs_item));
  1558. /* update the item pointers */
  1559. right_nritems += push_items;
  1560. btrfs_set_header_nritems(right, right_nritems);
  1561. push_space = BTRFS_LEAF_DATA_SIZE(root);
  1562. for (i = 0; i < right_nritems; i++) {
  1563. item = btrfs_item_nr(right, i);
  1564. if (!right->map_token) {
  1565. map_extent_buffer(right, (unsigned long)item,
  1566. sizeof(struct btrfs_item),
  1567. &right->map_token, &right->kaddr,
  1568. &right->map_start, &right->map_len,
  1569. KM_USER1);
  1570. }
  1571. push_space -= btrfs_item_size(right, item);
  1572. btrfs_set_item_offset(right, item, push_space);
  1573. }
  1574. if (right->map_token) {
  1575. unmap_extent_buffer(right, right->map_token, KM_USER1);
  1576. right->map_token = NULL;
  1577. }
  1578. left_nritems -= push_items;
  1579. btrfs_set_header_nritems(left, left_nritems);
  1580. if (left_nritems)
  1581. btrfs_mark_buffer_dirty(left);
  1582. btrfs_mark_buffer_dirty(right);
  1583. btrfs_item_key(right, &disk_key, 0);
  1584. btrfs_set_node_key(upper, &disk_key, slot + 1);
  1585. btrfs_mark_buffer_dirty(upper);
  1586. /* then fixup the leaf pointer in the path */
  1587. if (path->slots[0] >= left_nritems) {
  1588. path->slots[0] -= left_nritems;
  1589. free_extent_buffer(path->nodes[0]);
  1590. path->nodes[0] = right;
  1591. path->slots[1] += 1;
  1592. } else {
  1593. free_extent_buffer(right);
  1594. }
  1595. return 0;
  1596. }
  1597. /*
  1598. * push some data in the path leaf to the left, trying to free up at
  1599. * least data_size bytes. returns zero if the push worked, nonzero otherwise
  1600. */
  1601. static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root
  1602. *root, struct btrfs_path *path, int data_size,
  1603. int empty)
  1604. {
  1605. struct btrfs_disk_key disk_key;
  1606. struct extent_buffer *right = path->nodes[0];
  1607. struct extent_buffer *left;
  1608. int slot;
  1609. int i;
  1610. int free_space;
  1611. int push_space = 0;
  1612. int push_items = 0;
  1613. struct btrfs_item *item;
  1614. u32 old_left_nritems;
  1615. u32 right_nritems;
  1616. u32 nr;
  1617. int ret = 0;
  1618. int wret;
  1619. u32 this_item_size;
  1620. u32 old_left_item_size;
  1621. slot = path->slots[1];
  1622. if (slot == 0)
  1623. return 1;
  1624. if (!path->nodes[1])
  1625. return 1;
  1626. right_nritems = btrfs_header_nritems(right);
  1627. if (right_nritems == 0) {
  1628. return 1;
  1629. }
  1630. left = read_tree_block(root, btrfs_node_blockptr(path->nodes[1],
  1631. slot - 1), root->leafsize);
  1632. free_space = btrfs_leaf_free_space(root, left);
  1633. if (free_space < data_size + sizeof(struct btrfs_item)) {
  1634. free_extent_buffer(left);
  1635. return 1;
  1636. }
  1637. /* cow and double check */
  1638. ret = btrfs_cow_block(trans, root, left,
  1639. path->nodes[1], slot - 1, &left);
  1640. if (ret) {
  1641. /* we hit -ENOSPC, but it isn't fatal here */
  1642. free_extent_buffer(left);
  1643. return 1;
  1644. }
  1645. free_space = btrfs_leaf_free_space(root, left);
  1646. if (free_space < data_size + sizeof(struct btrfs_item)) {
  1647. free_extent_buffer(left);
  1648. return 1;
  1649. }
  1650. if (empty)
  1651. nr = right_nritems;
  1652. else
  1653. nr = right_nritems - 1;
  1654. for (i = 0; i < nr; i++) {
  1655. item = btrfs_item_nr(right, i);
  1656. if (!right->map_token) {
  1657. map_extent_buffer(right, (unsigned long)item,
  1658. sizeof(struct btrfs_item),
  1659. &right->map_token, &right->kaddr,
  1660. &right->map_start, &right->map_len,
  1661. KM_USER1);
  1662. }
  1663. if (path->slots[0] == i)
  1664. push_space += data_size + sizeof(*item);
  1665. this_item_size = btrfs_item_size(right, item);
  1666. if (this_item_size + sizeof(*item) + push_space > free_space)
  1667. break;
  1668. push_items++;
  1669. push_space += this_item_size + sizeof(*item);
  1670. }
  1671. if (right->map_token) {
  1672. unmap_extent_buffer(right, right->map_token, KM_USER1);
  1673. right->map_token = NULL;
  1674. }
  1675. if (push_items == 0) {
  1676. free_extent_buffer(left);
  1677. return 1;
  1678. }
  1679. if (!empty && push_items == btrfs_header_nritems(right))
  1680. WARN_ON(1);
  1681. /* push data from right to left */
  1682. copy_extent_buffer(left, right,
  1683. btrfs_item_nr_offset(btrfs_header_nritems(left)),
  1684. btrfs_item_nr_offset(0),
  1685. push_items * sizeof(struct btrfs_item));
  1686. push_space = BTRFS_LEAF_DATA_SIZE(root) -
  1687. btrfs_item_offset_nr(right, push_items -1);
  1688. copy_extent_buffer(left, right, btrfs_leaf_data(left) +
  1689. leaf_data_end(root, left) - push_space,
  1690. btrfs_leaf_data(right) +
  1691. btrfs_item_offset_nr(right, push_items - 1),
  1692. push_space);
  1693. old_left_nritems = btrfs_header_nritems(left);
  1694. BUG_ON(old_left_nritems < 0);
  1695. old_left_item_size = btrfs_item_offset_nr(left, old_left_nritems - 1);
  1696. for (i = old_left_nritems; i < old_left_nritems + push_items; i++) {
  1697. u32 ioff;
  1698. item = btrfs_item_nr(left, i);
  1699. if (!left->map_token) {
  1700. map_extent_buffer(left, (unsigned long)item,
  1701. sizeof(struct btrfs_item),
  1702. &left->map_token, &left->kaddr,
  1703. &left->map_start, &left->map_len,
  1704. KM_USER1);
  1705. }
  1706. ioff = btrfs_item_offset(left, item);
  1707. btrfs_set_item_offset(left, item,
  1708. ioff - (BTRFS_LEAF_DATA_SIZE(root) - old_left_item_size));
  1709. }
  1710. btrfs_set_header_nritems(left, old_left_nritems + push_items);
  1711. if (left->map_token) {
  1712. unmap_extent_buffer(left, left->map_token, KM_USER1);
  1713. left->map_token = NULL;
  1714. }
  1715. /* fixup right node */
  1716. if (push_items > right_nritems) {
  1717. printk("push items %d nr %u\n", push_items, right_nritems);
  1718. WARN_ON(1);
  1719. }
  1720. if (push_items < right_nritems) {
  1721. push_space = btrfs_item_offset_nr(right, push_items - 1) -
  1722. leaf_data_end(root, right);
  1723. memmove_extent_buffer(right, btrfs_leaf_data(right) +
  1724. BTRFS_LEAF_DATA_SIZE(root) - push_space,
  1725. btrfs_leaf_data(right) +
  1726. leaf_data_end(root, right), push_space);
  1727. memmove_extent_buffer(right, btrfs_item_nr_offset(0),
  1728. btrfs_item_nr_offset(push_items),
  1729. (btrfs_header_nritems(right) - push_items) *
  1730. sizeof(struct btrfs_item));
  1731. }
  1732. right_nritems -= push_items;
  1733. btrfs_set_header_nritems(right, right_nritems);
  1734. push_space = BTRFS_LEAF_DATA_SIZE(root);
  1735. for (i = 0; i < right_nritems; i++) {
  1736. item = btrfs_item_nr(right, i);
  1737. if (!right->map_token) {
  1738. map_extent_buffer(right, (unsigned long)item,
  1739. sizeof(struct btrfs_item),
  1740. &right->map_token, &right->kaddr,
  1741. &right->map_start, &right->map_len,
  1742. KM_USER1);
  1743. }
  1744. push_space = push_space - btrfs_item_size(right, item);
  1745. btrfs_set_item_offset(right, item, push_space);
  1746. }
  1747. if (right->map_token) {
  1748. unmap_extent_buffer(right, right->map_token, KM_USER1);
  1749. right->map_token = NULL;
  1750. }
  1751. btrfs_mark_buffer_dirty(left);
  1752. if (right_nritems)
  1753. btrfs_mark_buffer_dirty(right);
  1754. btrfs_item_key(right, &disk_key, 0);
  1755. wret = fixup_low_keys(trans, root, path, &disk_key, 1);
  1756. if (wret)
  1757. ret = wret;
  1758. /* then fixup the leaf pointer in the path */
  1759. if (path->slots[0] < push_items) {
  1760. path->slots[0] += old_left_nritems;
  1761. free_extent_buffer(path->nodes[0]);
  1762. path->nodes[0] = left;
  1763. path->slots[1] -= 1;
  1764. } else {
  1765. free_extent_buffer(left);
  1766. path->slots[0] -= push_items;
  1767. }
  1768. BUG_ON(path->slots[0] < 0);
  1769. return ret;
  1770. }
  1771. /*
  1772. * split the path's leaf in two, making sure there is at least data_size
  1773. * available for the resulting leaf level of the path.
  1774. *
  1775. * returns 0 if all went well and < 0 on failure.
  1776. */
  1777. static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root
  1778. *root, struct btrfs_key *ins_key,
  1779. struct btrfs_path *path, int data_size, int extend)
  1780. {
  1781. u64 root_gen;
  1782. struct extent_buffer *l;
  1783. u32 nritems;
  1784. int mid;
  1785. int slot;
  1786. struct extent_buffer *right;
  1787. int space_needed = data_size + sizeof(struct btrfs_item);
  1788. int data_copy_size;
  1789. int rt_data_off;
  1790. int i;
  1791. int ret = 0;
  1792. int wret;
  1793. int double_split;
  1794. int num_doubles = 0;
  1795. struct btrfs_disk_key disk_key;
  1796. if (extend)
  1797. space_needed = data_size;
  1798. if (root->ref_cows)
  1799. root_gen = trans->transid;
  1800. else
  1801. root_gen = 0;
  1802. /* first try to make some room by pushing left and right */
  1803. if (ins_key->type != BTRFS_DIR_ITEM_KEY) {
  1804. wret = push_leaf_right(trans, root, path, data_size, 0);
  1805. if (wret < 0) {
  1806. return wret;
  1807. }
  1808. if (wret) {
  1809. wret = push_leaf_left(trans, root, path, data_size, 0);
  1810. if (wret < 0)
  1811. return wret;
  1812. }
  1813. l = path->nodes[0];
  1814. /* did the pushes work? */
  1815. if (btrfs_leaf_free_space(root, l) >= space_needed)
  1816. return 0;
  1817. }
  1818. if (!path->nodes[1]) {
  1819. ret = insert_new_root(trans, root, path, 1);
  1820. if (ret)
  1821. return ret;
  1822. }
  1823. again:
  1824. double_split = 0;
  1825. l = path->nodes[0];
  1826. slot = path->slots[0];
  1827. nritems = btrfs_header_nritems(l);
  1828. mid = (nritems + 1)/ 2;
  1829. btrfs_item_key(l, &disk_key, 0);
  1830. right = __btrfs_alloc_free_block(trans, root, root->leafsize,
  1831. root->root_key.objectid,
  1832. root_gen, disk_key.objectid, 0,
  1833. l->start, 0);
  1834. if (IS_ERR(right)) {
  1835. BUG_ON(1);
  1836. return PTR_ERR(right);
  1837. }
  1838. memset_extent_buffer(right, 0, 0, sizeof(struct btrfs_header));
  1839. btrfs_set_header_bytenr(right, right->start);
  1840. btrfs_set_header_generation(right, trans->transid);
  1841. btrfs_set_header_owner(right, root->root_key.objectid);
  1842. btrfs_set_header_level(right, 0);
  1843. write_extent_buffer(right, root->fs_info->fsid,
  1844. (unsigned long)btrfs_header_fsid(right),
  1845. BTRFS_FSID_SIZE);
  1846. if (mid <= slot) {
  1847. if (nritems == 1 ||
  1848. leaf_space_used(l, mid, nritems - mid) + space_needed >
  1849. BTRFS_LEAF_DATA_SIZE(root)) {
  1850. if (slot >= nritems) {
  1851. btrfs_cpu_key_to_disk(&disk_key, ins_key);
  1852. btrfs_set_header_nritems(right, 0);
  1853. wret = insert_ptr(trans, root, path,
  1854. &disk_key, right->start,
  1855. path->slots[1] + 1, 1);
  1856. if (wret)
  1857. ret = wret;
  1858. free_extent_buffer(path->nodes[0]);
  1859. path->nodes[0] = right;
  1860. path->slots[0] = 0;
  1861. path->slots[1] += 1;
  1862. btrfs_mark_buffer_dirty(right);
  1863. return ret;
  1864. }
  1865. mid = slot;
  1866. if (mid != nritems &&
  1867. leaf_space_used(l, mid, nritems - mid) +
  1868. space_needed > BTRFS_LEAF_DATA_SIZE(root)) {
  1869. double_split = 1;
  1870. }
  1871. }
  1872. } else {
  1873. if (leaf_space_used(l, 0, mid + 1) + space_needed >
  1874. BTRFS_LEAF_DATA_SIZE(root)) {
  1875. if (!extend && slot == 0) {
  1876. btrfs_cpu_key_to_disk(&disk_key, ins_key);
  1877. btrfs_set_header_nritems(right, 0);
  1878. wret = insert_ptr(trans, root, path,
  1879. &disk_key,
  1880. right->start,
  1881. path->slots[1], 1);
  1882. if (wret)
  1883. ret = wret;
  1884. free_extent_buffer(path->nodes[0]);
  1885. path->nodes[0] = right;
  1886. path->slots[0] = 0;
  1887. if (path->slots[1] == 0) {
  1888. wret = fixup_low_keys(trans, root,
  1889. path, &disk_key, 1);
  1890. if (wret)
  1891. ret = wret;
  1892. }
  1893. btrfs_mark_buffer_dirty(right);
  1894. return ret;
  1895. } else if (extend && slot == 0) {
  1896. mid = 1;
  1897. } else {
  1898. mid = slot;
  1899. if (mid != nritems &&
  1900. leaf_space_used(l, mid, nritems - mid) +
  1901. space_needed > BTRFS_LEAF_DATA_SIZE(root)) {
  1902. double_split = 1;
  1903. }
  1904. }
  1905. }
  1906. }
  1907. nritems = nritems - mid;
  1908. btrfs_set_header_nritems(right, nritems);
  1909. data_copy_size = btrfs_item_end_nr(l, mid) - leaf_data_end(root, l);
  1910. copy_extent_buffer(right, l, btrfs_item_nr_offset(0),
  1911. btrfs_item_nr_offset(mid),
  1912. nritems * sizeof(struct btrfs_item));
  1913. copy_extent_buffer(right, l,
  1914. btrfs_leaf_data(right) + BTRFS_LEAF_DATA_SIZE(root) -
  1915. data_copy_size, btrfs_leaf_data(l) +
  1916. leaf_data_end(root, l), data_copy_size);
  1917. rt_data_off = BTRFS_LEAF_DATA_SIZE(root) -
  1918. btrfs_item_end_nr(l, mid);
  1919. for (i = 0; i < nritems; i++) {
  1920. struct btrfs_item *item = btrfs_item_nr(right, i);
  1921. u32 ioff;
  1922. if (!right->map_token) {
  1923. map_extent_buffer(right, (unsigned long)item,
  1924. sizeof(struct btrfs_item),
  1925. &right->map_token, &right->kaddr,
  1926. &right->map_start, &right->map_len,
  1927. KM_USER1);
  1928. }
  1929. ioff = btrfs_item_offset(right, item);
  1930. btrfs_set_item_offset(right, item, ioff + rt_data_off);
  1931. }
  1932. if (right->map_token) {
  1933. unmap_extent_buffer(right, right->map_token, KM_USER1);
  1934. right->map_token = NULL;
  1935. }
  1936. btrfs_set_header_nritems(l, mid);
  1937. ret = 0;
  1938. btrfs_item_key(right, &disk_key, 0);
  1939. wret = insert_ptr(trans, root, path, &disk_key, right->start,
  1940. path->slots[1] + 1, 1);
  1941. if (wret)
  1942. ret = wret;
  1943. btrfs_mark_buffer_dirty(right);
  1944. btrfs_mark_buffer_dirty(l);
  1945. BUG_ON(path->slots[0] != slot);
  1946. if (mid <= slot) {
  1947. free_extent_buffer(path->nodes[0]);
  1948. path->nodes[0] = right;
  1949. path->slots[0] -= mid;
  1950. path->slots[1] += 1;
  1951. } else
  1952. free_extent_buffer(right);
  1953. BUG_ON(path->slots[0] < 0);
  1954. if (double_split) {
  1955. BUG_ON(num_doubles != 0);
  1956. num_doubles++;
  1957. goto again;
  1958. }
  1959. return ret;
  1960. }
  1961. int btrfs_truncate_item(struct btrfs_trans_handle *trans,
  1962. struct btrfs_root *root,
  1963. struct btrfs_path *path,
  1964. u32 new_size, int from_end)
  1965. {
  1966. int ret = 0;
  1967. int slot;
  1968. int slot_orig;
  1969. struct extent_buffer *leaf;
  1970. struct btrfs_item *item;
  1971. u32 nritems;
  1972. unsigned int data_end;
  1973. unsigned int old_data_start;
  1974. unsigned int old_size;
  1975. unsigned int size_diff;
  1976. int i;
  1977. slot_orig = path->slots[0];
  1978. leaf = path->nodes[0];
  1979. slot = path->slots[0];
  1980. old_size = btrfs_item_size_nr(leaf, slot);
  1981. if (old_size == new_size)
  1982. return 0;
  1983. nritems = btrfs_header_nritems(leaf);
  1984. data_end = leaf_data_end(root, leaf);
  1985. old_data_start = btrfs_item_offset_nr(leaf, slot);
  1986. size_diff = old_size - new_size;
  1987. BUG_ON(slot < 0);
  1988. BUG_ON(slot >= nritems);
  1989. /*
  1990. * item0..itemN ... dataN.offset..dataN.size .. data0.size
  1991. */
  1992. /* first correct the data pointers */
  1993. for (i = slot; i < nritems; i++) {
  1994. u32 ioff;
  1995. item = btrfs_item_nr(leaf, i);
  1996. if (!leaf->map_token) {
  1997. map_extent_buffer(leaf, (unsigned long)item,
  1998. sizeof(struct btrfs_item),
  1999. &leaf->map_token, &leaf->kaddr,
  2000. &leaf->map_start, &leaf->map_len,
  2001. KM_USER1);
  2002. }
  2003. ioff = btrfs_item_offset(leaf, item);
  2004. btrfs_set_item_offset(leaf, item, ioff + size_diff);
  2005. }
  2006. if (leaf->map_token) {
  2007. unmap_extent_buffer(leaf, leaf->map_token, KM_USER1);
  2008. leaf->map_token = NULL;
  2009. }
  2010. /* shift the data */
  2011. if (from_end) {
  2012. memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
  2013. data_end + size_diff, btrfs_leaf_data(leaf) +
  2014. data_end, old_data_start + new_size - data_end);
  2015. } else {
  2016. struct btrfs_disk_key disk_key;
  2017. u64 offset;
  2018. btrfs_item_key(leaf, &disk_key, slot);
  2019. if (btrfs_disk_key_type(&disk_key) == BTRFS_EXTENT_DATA_KEY) {
  2020. unsigned long ptr;
  2021. struct btrfs_file_extent_item *fi;
  2022. fi = btrfs_item_ptr(leaf, slot,
  2023. struct btrfs_file_extent_item);
  2024. fi = (struct btrfs_file_extent_item *)(
  2025. (unsigned long)fi - size_diff);
  2026. if (btrfs_file_extent_type(leaf, fi) ==
  2027. BTRFS_FILE_EXTENT_INLINE) {
  2028. ptr = btrfs_item_ptr_offset(leaf, slot);
  2029. memmove_extent_buffer(leaf, ptr,
  2030. (unsigned long)fi,
  2031. offsetof(struct btrfs_file_extent_item,
  2032. disk_bytenr));
  2033. }
  2034. }
  2035. memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
  2036. data_end + size_diff, btrfs_leaf_data(leaf) +
  2037. data_end, old_data_start - data_end);
  2038. offset = btrfs_disk_key_offset(&disk_key);
  2039. btrfs_set_disk_key_offset(&disk_key, offset + size_diff);
  2040. btrfs_set_item_key(leaf, &disk_key, slot);
  2041. if (slot == 0)
  2042. fixup_low_keys(trans, root, path, &disk_key, 1);
  2043. }
  2044. item = btrfs_item_nr(leaf, slot);
  2045. btrfs_set_item_size(leaf, item, new_size);
  2046. btrfs_mark_buffer_dirty(leaf);
  2047. ret = 0;
  2048. if (btrfs_leaf_free_space(root, leaf) < 0) {
  2049. btrfs_print_leaf(root, leaf);
  2050. BUG();
  2051. }
  2052. return ret;
  2053. }
  2054. int btrfs_extend_item(struct btrfs_trans_handle *trans,
  2055. struct btrfs_root *root, struct btrfs_path *path,
  2056. u32 data_size)
  2057. {
  2058. int ret = 0;
  2059. int slot;
  2060. int slot_orig;
  2061. struct extent_buffer *leaf;
  2062. struct btrfs_item *item;
  2063. u32 nritems;
  2064. unsigned int data_end;
  2065. unsigned int old_data;
  2066. unsigned int old_size;
  2067. int i;
  2068. slot_orig = path->slots[0];
  2069. leaf = path->nodes[0];
  2070. nritems = btrfs_header_nritems(leaf);
  2071. data_end = leaf_data_end(root, leaf);
  2072. if (btrfs_leaf_free_space(root, leaf) < data_size) {
  2073. btrfs_print_leaf(root, leaf);
  2074. BUG();
  2075. }
  2076. slot = path->slots[0];
  2077. old_data = btrfs_item_end_nr(leaf, slot);
  2078. BUG_ON(slot < 0);
  2079. if (slot >= nritems) {
  2080. btrfs_print_leaf(root, leaf);
  2081. printk("slot %d too large, nritems %d\n", slot, nritems);
  2082. BUG_ON(1);
  2083. }
  2084. /*
  2085. * item0..itemN ... dataN.offset..dataN.size .. data0.size
  2086. */
  2087. /* first correct the data pointers */
  2088. for (i = slot; i < nritems; i++) {
  2089. u32 ioff;
  2090. item = btrfs_item_nr(leaf, i);
  2091. if (!leaf->map_token) {
  2092. map_extent_buffer(leaf, (unsigned long)item,
  2093. sizeof(struct btrfs_item),
  2094. &leaf->map_token, &leaf->kaddr,
  2095. &leaf->map_start, &leaf->map_len,
  2096. KM_USER1);
  2097. }
  2098. ioff = btrfs_item_offset(leaf, item);
  2099. btrfs_set_item_offset(leaf, item, ioff - data_size);
  2100. }
  2101. if (leaf->map_token) {
  2102. unmap_extent_buffer(leaf, leaf->map_token, KM_USER1);
  2103. leaf->map_token = NULL;
  2104. }
  2105. /* shift the data */
  2106. memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
  2107. data_end - data_size, btrfs_leaf_data(leaf) +
  2108. data_end, old_data - data_end);
  2109. data_end = old_data;
  2110. old_size = btrfs_item_size_nr(leaf, slot);
  2111. item = btrfs_item_nr(leaf, slot);
  2112. btrfs_set_item_size(leaf, item, old_size + data_size);
  2113. btrfs_mark_buffer_dirty(leaf);
  2114. ret = 0;
  2115. if (btrfs_leaf_free_space(root, leaf) < 0) {
  2116. btrfs_print_leaf(root, leaf);
  2117. BUG();
  2118. }
  2119. return ret;
  2120. }
  2121. /*
  2122. * Given a key and some data, insert an item into the tree.
  2123. * This does all the path init required, making room in the tree if needed.
  2124. */
  2125. int btrfs_insert_empty_items(struct btrfs_trans_handle *trans,
  2126. struct btrfs_root *root,
  2127. struct btrfs_path *path,
  2128. struct btrfs_key *cpu_key, u32 *data_size,
  2129. int nr)
  2130. {
  2131. struct extent_buffer *leaf;
  2132. struct btrfs_item *item;
  2133. int ret = 0;
  2134. int slot;
  2135. int slot_orig;
  2136. int i;
  2137. u32 nritems;
  2138. u32 total_size = 0;
  2139. u32 total_data = 0;
  2140. unsigned int data_end;
  2141. struct btrfs_disk_key disk_key;
  2142. for (i = 0; i < nr; i++) {
  2143. total_data += data_size[i];
  2144. }
  2145. /* create a root if there isn't one */
  2146. if (!root->node)
  2147. BUG();
  2148. total_size = total_data + (nr - 1) * sizeof(struct btrfs_item);
  2149. ret = btrfs_search_slot(trans, root, cpu_key, path, total_size, 1);
  2150. if (ret == 0) {
  2151. return -EEXIST;
  2152. }
  2153. if (ret < 0)
  2154. goto out;
  2155. slot_orig = path->slots[0];
  2156. leaf = path->nodes[0];
  2157. nritems = btrfs_header_nritems(leaf);
  2158. data_end = leaf_data_end(root, leaf);
  2159. if (btrfs_leaf_free_space(root, leaf) <
  2160. sizeof(struct btrfs_item) + total_size) {
  2161. btrfs_print_leaf(root, leaf);
  2162. printk("not enough freespace need %u have %d\n",
  2163. total_size, btrfs_leaf_free_space(root, leaf));
  2164. BUG();
  2165. }
  2166. slot = path->slots[0];
  2167. BUG_ON(slot < 0);
  2168. if (slot != nritems) {
  2169. int i;
  2170. unsigned int old_data = btrfs_item_end_nr(leaf, slot);
  2171. if (old_data < data_end) {
  2172. btrfs_print_leaf(root, leaf);
  2173. printk("slot %d old_data %d data_end %d\n",
  2174. slot, old_data, data_end);
  2175. BUG_ON(1);
  2176. }
  2177. /*
  2178. * item0..itemN ... dataN.offset..dataN.size .. data0.size
  2179. */
  2180. /* first correct the data pointers */
  2181. WARN_ON(leaf->map_token);
  2182. for (i = slot; i < nritems; i++) {
  2183. u32 ioff;
  2184. item = btrfs_item_nr(leaf, i);
  2185. if (!leaf->map_token) {
  2186. map_extent_buffer(leaf, (unsigned long)item,
  2187. sizeof(struct btrfs_item),
  2188. &leaf->map_token, &leaf->kaddr,
  2189. &leaf->map_start, &leaf->map_len,
  2190. KM_USER1);
  2191. }
  2192. ioff = btrfs_item_offset(leaf, item);
  2193. btrfs_set_item_offset(leaf, item, ioff - total_data);
  2194. }
  2195. if (leaf->map_token) {
  2196. unmap_extent_buffer(leaf, leaf->map_token, KM_USER1);
  2197. leaf->map_token = NULL;
  2198. }
  2199. /* shift the items */
  2200. memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + nr),
  2201. btrfs_item_nr_offset(slot),
  2202. (nritems - slot) * sizeof(struct btrfs_item));
  2203. /* shift the data */
  2204. memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
  2205. data_end - total_data, btrfs_leaf_data(leaf) +
  2206. data_end, old_data - data_end);
  2207. data_end = old_data;
  2208. }
  2209. /* setup the item for the new data */
  2210. for (i = 0; i < nr; i++) {
  2211. btrfs_cpu_key_to_disk(&disk_key, cpu_key + i);
  2212. btrfs_set_item_key(leaf, &disk_key, slot + i);
  2213. item = btrfs_item_nr(leaf, slot + i);
  2214. btrfs_set_item_offset(leaf, item, data_end - data_size[i]);
  2215. data_end -= data_size[i];
  2216. btrfs_set_item_size(leaf, item, data_size[i]);
  2217. }
  2218. btrfs_set_header_nritems(leaf, nritems + nr);
  2219. btrfs_mark_buffer_dirty(leaf);
  2220. ret = 0;
  2221. if (slot == 0) {
  2222. btrfs_cpu_key_to_disk(&disk_key, cpu_key);
  2223. ret = fixup_low_keys(trans, root, path, &disk_key, 1);
  2224. }
  2225. if (btrfs_leaf_free_space(root, leaf) < 0) {
  2226. btrfs_print_leaf(root, leaf);
  2227. BUG();
  2228. }
  2229. out:
  2230. return ret;
  2231. }
  2232. /*
  2233. * Given a key and some data, insert an item into the tree.
  2234. * This does all the path init required, making room in the tree if needed.
  2235. */
  2236. int btrfs_insert_item(struct btrfs_trans_handle *trans, struct btrfs_root
  2237. *root, struct btrfs_key *cpu_key, void *data, u32
  2238. data_size)
  2239. {
  2240. int ret = 0;
  2241. struct btrfs_path *path;
  2242. struct extent_buffer *leaf;
  2243. unsigned long ptr;
  2244. path = btrfs_alloc_path();
  2245. BUG_ON(!path);
  2246. ret = btrfs_insert_empty_item(trans, root, path, cpu_key, data_size);
  2247. if (!ret) {
  2248. leaf = path->nodes[0];
  2249. ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
  2250. write_extent_buffer(leaf, data, ptr, data_size);
  2251. btrfs_mark_buffer_dirty(leaf);
  2252. }
  2253. btrfs_free_path(path);
  2254. return ret;
  2255. }
  2256. /*
  2257. * delete the pointer from a given node.
  2258. *
  2259. * If the delete empties a node, the node is removed from the tree,
  2260. * continuing all the way the root if required. The root is converted into
  2261. * a leaf if all the nodes are emptied.
  2262. */
  2263. static int del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root,
  2264. struct btrfs_path *path, int level, int slot)
  2265. {
  2266. struct extent_buffer *parent = path->nodes[level];
  2267. u32 nritems;
  2268. int ret = 0;
  2269. int wret;
  2270. nritems = btrfs_header_nritems(parent);
  2271. if (slot != nritems -1) {
  2272. memmove_extent_buffer(parent,
  2273. btrfs_node_key_ptr_offset(slot),
  2274. btrfs_node_key_ptr_offset(slot + 1),
  2275. sizeof(struct btrfs_key_ptr) *
  2276. (nritems - slot - 1));
  2277. }
  2278. nritems--;
  2279. btrfs_set_header_nritems(parent, nritems);
  2280. if (nritems == 0 && parent == root->node) {
  2281. BUG_ON(btrfs_header_level(root->node) != 1);
  2282. /* just turn the root into a leaf and break */
  2283. btrfs_set_header_level(root->node, 0);
  2284. } else if (slot == 0) {
  2285. struct btrfs_disk_key disk_key;
  2286. btrfs_node_key(parent, &disk_key, 0);
  2287. wret = fixup_low_keys(trans, root, path, &disk_key, level + 1);
  2288. if (wret)
  2289. ret = wret;
  2290. }
  2291. btrfs_mark_buffer_dirty(parent);
  2292. return ret;
  2293. }
  2294. /*
  2295. * delete the item at the leaf level in path. If that empties
  2296. * the leaf, remove it from the tree
  2297. */
  2298. int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root,
  2299. struct btrfs_path *path, int slot, int nr)
  2300. {
  2301. struct extent_buffer *leaf;
  2302. struct btrfs_item *item;
  2303. int last_off;
  2304. int dsize = 0;
  2305. int ret = 0;
  2306. int wret;
  2307. int i;
  2308. u32 nritems;
  2309. leaf = path->nodes[0];
  2310. last_off = btrfs_item_offset_nr(leaf, slot + nr - 1);
  2311. for (i = 0; i < nr; i++)
  2312. dsize += btrfs_item_size_nr(leaf, slot + i);
  2313. nritems = btrfs_header_nritems(leaf);
  2314. if (slot + nr != nritems) {
  2315. int i;
  2316. int data_end = leaf_data_end(root, leaf);
  2317. memmove_extent_buffer(leaf, btrfs_leaf_data(leaf) +
  2318. data_end + dsize,
  2319. btrfs_leaf_data(leaf) + data_end,
  2320. last_off - data_end);
  2321. for (i = slot + nr; i < nritems; i++) {
  2322. u32 ioff;
  2323. item = btrfs_item_nr(leaf, i);
  2324. if (!leaf->map_token) {
  2325. map_extent_buffer(leaf, (unsigned long)item,
  2326. sizeof(struct btrfs_item),
  2327. &leaf->map_token, &leaf->kaddr,
  2328. &leaf->map_start, &leaf->map_len,
  2329. KM_USER1);
  2330. }
  2331. ioff = btrfs_item_offset(leaf, item);
  2332. btrfs_set_item_offset(leaf, item, ioff + dsize);
  2333. }
  2334. if (leaf->map_token) {
  2335. unmap_extent_buffer(leaf, leaf->map_token, KM_USER1);
  2336. leaf->map_token = NULL;
  2337. }
  2338. memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot),
  2339. btrfs_item_nr_offset(slot + nr),
  2340. sizeof(struct btrfs_item) *
  2341. (nritems - slot - nr));
  2342. }
  2343. btrfs_set_header_nritems(leaf, nritems - nr);
  2344. nritems -= nr;
  2345. /* delete the leaf if we've emptied it */
  2346. if (nritems == 0) {
  2347. if (leaf == root->node) {
  2348. btrfs_set_header_level(leaf, 0);
  2349. } else {
  2350. u64 root_gen = btrfs_header_generation(path->nodes[1]);
  2351. clean_tree_block(trans, root, leaf);
  2352. wait_on_tree_block_writeback(root, leaf);
  2353. wret = del_ptr(trans, root, path, 1, path->slots[1]);
  2354. if (wret)
  2355. ret = wret;
  2356. wret = btrfs_free_extent(trans, root,
  2357. leaf->start, leaf->len,
  2358. btrfs_header_owner(path->nodes[1]),
  2359. root_gen, 0, 0, 1);
  2360. if (wret)
  2361. ret = wret;
  2362. }
  2363. } else {
  2364. int used = leaf_space_used(leaf, 0, nritems);
  2365. if (slot == 0) {
  2366. struct btrfs_disk_key disk_key;
  2367. btrfs_item_key(leaf, &disk_key, 0);
  2368. wret = fixup_low_keys(trans, root, path,
  2369. &disk_key, 1);
  2370. if (wret)
  2371. ret = wret;
  2372. }
  2373. /* delete the leaf if it is mostly empty */
  2374. if (used < BTRFS_LEAF_DATA_SIZE(root) / 4) {
  2375. /* push_leaf_left fixes the path.
  2376. * make sure the path still points to our leaf
  2377. * for possible call to del_ptr below
  2378. */
  2379. slot = path->slots[1];
  2380. extent_buffer_get(leaf);
  2381. wret = push_leaf_left(trans, root, path, 1, 1);
  2382. if (wret < 0 && wret != -ENOSPC)
  2383. ret = wret;
  2384. if (path->nodes[0] == leaf &&
  2385. btrfs_header_nritems(leaf)) {
  2386. wret = push_leaf_right(trans, root, path, 1, 1);
  2387. if (wret < 0 && wret != -ENOSPC)
  2388. ret = wret;
  2389. }
  2390. if (btrfs_header_nritems(leaf) == 0) {
  2391. u64 root_gen;
  2392. u64 bytenr = leaf->start;
  2393. u32 blocksize = leaf->len;
  2394. root_gen = btrfs_header_generation(
  2395. path->nodes[1]);
  2396. clean_tree_block(trans, root, leaf);
  2397. wait_on_tree_block_writeback(root, leaf);
  2398. wret = del_ptr(trans, root, path, 1, slot);
  2399. if (wret)
  2400. ret = wret;
  2401. free_extent_buffer(leaf);
  2402. wret = btrfs_free_extent(trans, root, bytenr,
  2403. blocksize,
  2404. btrfs_header_owner(path->nodes[1]),
  2405. root_gen, 0, 0, 1);
  2406. if (wret)
  2407. ret = wret;
  2408. } else {
  2409. btrfs_mark_buffer_dirty(leaf);
  2410. free_extent_buffer(leaf);
  2411. }
  2412. } else {
  2413. btrfs_mark_buffer_dirty(leaf);
  2414. }
  2415. }
  2416. return ret;
  2417. }
  2418. /*
  2419. * walk up the tree as far as required to find the previous leaf.
  2420. * returns 0 if it found something or 1 if there are no lesser leaves.
  2421. * returns < 0 on io errors.
  2422. */
  2423. int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path)
  2424. {
  2425. u64 bytenr;
  2426. int slot;
  2427. int level = 1;
  2428. struct extent_buffer *c;
  2429. struct extent_buffer *next = NULL;
  2430. while(level < BTRFS_MAX_LEVEL) {
  2431. if (!path->nodes[level])
  2432. return 1;
  2433. slot = path->slots[level];
  2434. c = path->nodes[level];
  2435. if (slot == 0) {
  2436. level++;
  2437. if (level == BTRFS_MAX_LEVEL)
  2438. return 1;
  2439. continue;
  2440. }
  2441. slot--;
  2442. bytenr = btrfs_node_blockptr(c, slot);
  2443. if (next)
  2444. free_extent_buffer(next);
  2445. next = read_tree_block(root, bytenr,
  2446. btrfs_level_size(root, level - 1));
  2447. break;
  2448. }
  2449. path->slots[level] = slot;
  2450. while(1) {
  2451. level--;
  2452. c = path->nodes[level];
  2453. free_extent_buffer(c);
  2454. slot = btrfs_header_nritems(next);
  2455. if (slot != 0)
  2456. slot--;
  2457. path->nodes[level] = next;
  2458. path->slots[level] = slot;
  2459. if (!level)
  2460. break;
  2461. next = read_tree_block(root, btrfs_node_blockptr(next, slot),
  2462. btrfs_level_size(root, level - 1));
  2463. }
  2464. return 0;
  2465. }
  2466. /*
  2467. * walk up the tree as far as required to find the next leaf.
  2468. * returns 0 if it found something or 1 if there are no greater leaves.
  2469. * returns < 0 on io errors.
  2470. */
  2471. int btrfs_next_leaf(struct btrfs_root *root, struct btrfs_path *path)
  2472. {
  2473. int slot;
  2474. int level = 1;
  2475. u64 bytenr;
  2476. struct extent_buffer *c;
  2477. struct extent_buffer *next = NULL;
  2478. while(level < BTRFS_MAX_LEVEL) {
  2479. if (!path->nodes[level])
  2480. return 1;
  2481. slot = path->slots[level] + 1;
  2482. c = path->nodes[level];
  2483. if (slot >= btrfs_header_nritems(c)) {
  2484. level++;
  2485. if (level == BTRFS_MAX_LEVEL)
  2486. return 1;
  2487. continue;
  2488. }
  2489. bytenr = btrfs_node_blockptr(c, slot);
  2490. if (next)
  2491. free_extent_buffer(next);
  2492. if (path->reada)
  2493. reada_for_search(root, path, level, slot, 0);
  2494. next = read_tree_block(root, bytenr,
  2495. btrfs_level_size(root, level -1));
  2496. break;
  2497. }
  2498. path->slots[level] = slot;
  2499. while(1) {
  2500. level--;
  2501. c = path->nodes[level];
  2502. free_extent_buffer(c);
  2503. path->nodes[level] = next;
  2504. path->slots[level] = 0;
  2505. if (!level)
  2506. break;
  2507. if (path->reada)
  2508. reada_for_search(root, path, level, 0, 0);
  2509. next = read_tree_block(root, btrfs_node_blockptr(next, 0),
  2510. btrfs_level_size(root, level - 1));
  2511. }
  2512. return 0;
  2513. }
  2514. int btrfs_previous_item(struct btrfs_root *root,
  2515. struct btrfs_path *path, u64 min_objectid,
  2516. int type)
  2517. {
  2518. struct btrfs_key found_key;
  2519. struct extent_buffer *leaf;
  2520. int ret;
  2521. while(1) {
  2522. if (path->slots[0] == 0) {
  2523. ret = btrfs_prev_leaf(root, path);
  2524. if (ret != 0)
  2525. return ret;
  2526. } else {
  2527. path->slots[0]--;
  2528. }
  2529. leaf = path->nodes[0];
  2530. btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
  2531. if (found_key.type == type)
  2532. return 0;
  2533. }
  2534. return 1;
  2535. }