ctree.c 73 KB

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