node.c 41 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764
  1. /*
  2. * fs/f2fs/node.c
  3. *
  4. * Copyright (c) 2012 Samsung Electronics Co., Ltd.
  5. * http://www.samsung.com/
  6. *
  7. * This program is free software; you can redistribute it and/or modify
  8. * it under the terms of the GNU General Public License version 2 as
  9. * published by the Free Software Foundation.
  10. */
  11. #include <linux/fs.h>
  12. #include <linux/f2fs_fs.h>
  13. #include <linux/mpage.h>
  14. #include <linux/backing-dev.h>
  15. #include <linux/blkdev.h>
  16. #include <linux/pagevec.h>
  17. #include <linux/swap.h>
  18. #include "f2fs.h"
  19. #include "node.h"
  20. #include "segment.h"
  21. static struct kmem_cache *nat_entry_slab;
  22. static struct kmem_cache *free_nid_slab;
  23. static void clear_node_page_dirty(struct page *page)
  24. {
  25. struct address_space *mapping = page->mapping;
  26. struct f2fs_sb_info *sbi = F2FS_SB(mapping->host->i_sb);
  27. unsigned int long flags;
  28. if (PageDirty(page)) {
  29. spin_lock_irqsave(&mapping->tree_lock, flags);
  30. radix_tree_tag_clear(&mapping->page_tree,
  31. page_index(page),
  32. PAGECACHE_TAG_DIRTY);
  33. spin_unlock_irqrestore(&mapping->tree_lock, flags);
  34. clear_page_dirty_for_io(page);
  35. dec_page_count(sbi, F2FS_DIRTY_NODES);
  36. }
  37. ClearPageUptodate(page);
  38. }
  39. static struct page *get_current_nat_page(struct f2fs_sb_info *sbi, nid_t nid)
  40. {
  41. pgoff_t index = current_nat_addr(sbi, nid);
  42. return get_meta_page(sbi, index);
  43. }
  44. static struct page *get_next_nat_page(struct f2fs_sb_info *sbi, nid_t nid)
  45. {
  46. struct page *src_page;
  47. struct page *dst_page;
  48. pgoff_t src_off;
  49. pgoff_t dst_off;
  50. void *src_addr;
  51. void *dst_addr;
  52. struct f2fs_nm_info *nm_i = NM_I(sbi);
  53. src_off = current_nat_addr(sbi, nid);
  54. dst_off = next_nat_addr(sbi, src_off);
  55. /* get current nat block page with lock */
  56. src_page = get_meta_page(sbi, src_off);
  57. /* Dirty src_page means that it is already the new target NAT page. */
  58. if (PageDirty(src_page))
  59. return src_page;
  60. dst_page = grab_meta_page(sbi, dst_off);
  61. src_addr = page_address(src_page);
  62. dst_addr = page_address(dst_page);
  63. memcpy(dst_addr, src_addr, PAGE_CACHE_SIZE);
  64. set_page_dirty(dst_page);
  65. f2fs_put_page(src_page, 1);
  66. set_to_next_nat(nm_i, nid);
  67. return dst_page;
  68. }
  69. /*
  70. * Readahead NAT pages
  71. */
  72. static void ra_nat_pages(struct f2fs_sb_info *sbi, int nid)
  73. {
  74. struct address_space *mapping = sbi->meta_inode->i_mapping;
  75. struct f2fs_nm_info *nm_i = NM_I(sbi);
  76. struct page *page;
  77. pgoff_t index;
  78. int i;
  79. for (i = 0; i < FREE_NID_PAGES; i++, nid += NAT_ENTRY_PER_BLOCK) {
  80. if (nid >= nm_i->max_nid)
  81. nid = 0;
  82. index = current_nat_addr(sbi, nid);
  83. page = grab_cache_page(mapping, index);
  84. if (!page)
  85. continue;
  86. if (f2fs_readpage(sbi, page, index, READ)) {
  87. f2fs_put_page(page, 1);
  88. continue;
  89. }
  90. page_cache_release(page);
  91. }
  92. }
  93. static struct nat_entry *__lookup_nat_cache(struct f2fs_nm_info *nm_i, nid_t n)
  94. {
  95. return radix_tree_lookup(&nm_i->nat_root, n);
  96. }
  97. static unsigned int __gang_lookup_nat_cache(struct f2fs_nm_info *nm_i,
  98. nid_t start, unsigned int nr, struct nat_entry **ep)
  99. {
  100. return radix_tree_gang_lookup(&nm_i->nat_root, (void **)ep, start, nr);
  101. }
  102. static void __del_from_nat_cache(struct f2fs_nm_info *nm_i, struct nat_entry *e)
  103. {
  104. list_del(&e->list);
  105. radix_tree_delete(&nm_i->nat_root, nat_get_nid(e));
  106. nm_i->nat_cnt--;
  107. kmem_cache_free(nat_entry_slab, e);
  108. }
  109. int is_checkpointed_node(struct f2fs_sb_info *sbi, nid_t nid)
  110. {
  111. struct f2fs_nm_info *nm_i = NM_I(sbi);
  112. struct nat_entry *e;
  113. int is_cp = 1;
  114. read_lock(&nm_i->nat_tree_lock);
  115. e = __lookup_nat_cache(nm_i, nid);
  116. if (e && !e->checkpointed)
  117. is_cp = 0;
  118. read_unlock(&nm_i->nat_tree_lock);
  119. return is_cp;
  120. }
  121. static struct nat_entry *grab_nat_entry(struct f2fs_nm_info *nm_i, nid_t nid)
  122. {
  123. struct nat_entry *new;
  124. new = kmem_cache_alloc(nat_entry_slab, GFP_ATOMIC);
  125. if (!new)
  126. return NULL;
  127. if (radix_tree_insert(&nm_i->nat_root, nid, new)) {
  128. kmem_cache_free(nat_entry_slab, new);
  129. return NULL;
  130. }
  131. memset(new, 0, sizeof(struct nat_entry));
  132. nat_set_nid(new, nid);
  133. list_add_tail(&new->list, &nm_i->nat_entries);
  134. nm_i->nat_cnt++;
  135. return new;
  136. }
  137. static void cache_nat_entry(struct f2fs_nm_info *nm_i, nid_t nid,
  138. struct f2fs_nat_entry *ne)
  139. {
  140. struct nat_entry *e;
  141. retry:
  142. write_lock(&nm_i->nat_tree_lock);
  143. e = __lookup_nat_cache(nm_i, nid);
  144. if (!e) {
  145. e = grab_nat_entry(nm_i, nid);
  146. if (!e) {
  147. write_unlock(&nm_i->nat_tree_lock);
  148. goto retry;
  149. }
  150. nat_set_blkaddr(e, le32_to_cpu(ne->block_addr));
  151. nat_set_ino(e, le32_to_cpu(ne->ino));
  152. nat_set_version(e, ne->version);
  153. e->checkpointed = true;
  154. }
  155. write_unlock(&nm_i->nat_tree_lock);
  156. }
  157. static void set_node_addr(struct f2fs_sb_info *sbi, struct node_info *ni,
  158. block_t new_blkaddr)
  159. {
  160. struct f2fs_nm_info *nm_i = NM_I(sbi);
  161. struct nat_entry *e;
  162. retry:
  163. write_lock(&nm_i->nat_tree_lock);
  164. e = __lookup_nat_cache(nm_i, ni->nid);
  165. if (!e) {
  166. e = grab_nat_entry(nm_i, ni->nid);
  167. if (!e) {
  168. write_unlock(&nm_i->nat_tree_lock);
  169. goto retry;
  170. }
  171. e->ni = *ni;
  172. e->checkpointed = true;
  173. BUG_ON(ni->blk_addr == NEW_ADDR);
  174. } else if (new_blkaddr == NEW_ADDR) {
  175. /*
  176. * when nid is reallocated,
  177. * previous nat entry can be remained in nat cache.
  178. * So, reinitialize it with new information.
  179. */
  180. e->ni = *ni;
  181. BUG_ON(ni->blk_addr != NULL_ADDR);
  182. }
  183. if (new_blkaddr == NEW_ADDR)
  184. e->checkpointed = false;
  185. /* sanity check */
  186. BUG_ON(nat_get_blkaddr(e) != ni->blk_addr);
  187. BUG_ON(nat_get_blkaddr(e) == NULL_ADDR &&
  188. new_blkaddr == NULL_ADDR);
  189. BUG_ON(nat_get_blkaddr(e) == NEW_ADDR &&
  190. new_blkaddr == NEW_ADDR);
  191. BUG_ON(nat_get_blkaddr(e) != NEW_ADDR &&
  192. nat_get_blkaddr(e) != NULL_ADDR &&
  193. new_blkaddr == NEW_ADDR);
  194. /* increament version no as node is removed */
  195. if (nat_get_blkaddr(e) != NEW_ADDR && new_blkaddr == NULL_ADDR) {
  196. unsigned char version = nat_get_version(e);
  197. nat_set_version(e, inc_node_version(version));
  198. }
  199. /* change address */
  200. nat_set_blkaddr(e, new_blkaddr);
  201. __set_nat_cache_dirty(nm_i, e);
  202. write_unlock(&nm_i->nat_tree_lock);
  203. }
  204. static int try_to_free_nats(struct f2fs_sb_info *sbi, int nr_shrink)
  205. {
  206. struct f2fs_nm_info *nm_i = NM_I(sbi);
  207. if (nm_i->nat_cnt < 2 * NM_WOUT_THRESHOLD)
  208. return 0;
  209. write_lock(&nm_i->nat_tree_lock);
  210. while (nr_shrink && !list_empty(&nm_i->nat_entries)) {
  211. struct nat_entry *ne;
  212. ne = list_first_entry(&nm_i->nat_entries,
  213. struct nat_entry, list);
  214. __del_from_nat_cache(nm_i, ne);
  215. nr_shrink--;
  216. }
  217. write_unlock(&nm_i->nat_tree_lock);
  218. return nr_shrink;
  219. }
  220. /*
  221. * This function returns always success
  222. */
  223. void get_node_info(struct f2fs_sb_info *sbi, nid_t nid, struct node_info *ni)
  224. {
  225. struct f2fs_nm_info *nm_i = NM_I(sbi);
  226. struct curseg_info *curseg = CURSEG_I(sbi, CURSEG_HOT_DATA);
  227. struct f2fs_summary_block *sum = curseg->sum_blk;
  228. nid_t start_nid = START_NID(nid);
  229. struct f2fs_nat_block *nat_blk;
  230. struct page *page = NULL;
  231. struct f2fs_nat_entry ne;
  232. struct nat_entry *e;
  233. int i;
  234. memset(&ne, 0, sizeof(struct f2fs_nat_entry));
  235. ni->nid = nid;
  236. /* Check nat cache */
  237. read_lock(&nm_i->nat_tree_lock);
  238. e = __lookup_nat_cache(nm_i, nid);
  239. if (e) {
  240. ni->ino = nat_get_ino(e);
  241. ni->blk_addr = nat_get_blkaddr(e);
  242. ni->version = nat_get_version(e);
  243. }
  244. read_unlock(&nm_i->nat_tree_lock);
  245. if (e)
  246. return;
  247. /* Check current segment summary */
  248. mutex_lock(&curseg->curseg_mutex);
  249. i = lookup_journal_in_cursum(sum, NAT_JOURNAL, nid, 0);
  250. if (i >= 0) {
  251. ne = nat_in_journal(sum, i);
  252. node_info_from_raw_nat(ni, &ne);
  253. }
  254. mutex_unlock(&curseg->curseg_mutex);
  255. if (i >= 0)
  256. goto cache;
  257. /* Fill node_info from nat page */
  258. page = get_current_nat_page(sbi, start_nid);
  259. nat_blk = (struct f2fs_nat_block *)page_address(page);
  260. ne = nat_blk->entries[nid - start_nid];
  261. node_info_from_raw_nat(ni, &ne);
  262. f2fs_put_page(page, 1);
  263. cache:
  264. /* cache nat entry */
  265. cache_nat_entry(NM_I(sbi), nid, &ne);
  266. }
  267. /*
  268. * The maximum depth is four.
  269. * Offset[0] will have raw inode offset.
  270. */
  271. static int get_node_path(long block, int offset[4], unsigned int noffset[4])
  272. {
  273. const long direct_index = ADDRS_PER_INODE;
  274. const long direct_blks = ADDRS_PER_BLOCK;
  275. const long dptrs_per_blk = NIDS_PER_BLOCK;
  276. const long indirect_blks = ADDRS_PER_BLOCK * NIDS_PER_BLOCK;
  277. const long dindirect_blks = indirect_blks * NIDS_PER_BLOCK;
  278. int n = 0;
  279. int level = 0;
  280. noffset[0] = 0;
  281. if (block < direct_index) {
  282. offset[n++] = block;
  283. level = 0;
  284. goto got;
  285. }
  286. block -= direct_index;
  287. if (block < direct_blks) {
  288. offset[n++] = NODE_DIR1_BLOCK;
  289. noffset[n] = 1;
  290. offset[n++] = block;
  291. level = 1;
  292. goto got;
  293. }
  294. block -= direct_blks;
  295. if (block < direct_blks) {
  296. offset[n++] = NODE_DIR2_BLOCK;
  297. noffset[n] = 2;
  298. offset[n++] = block;
  299. level = 1;
  300. goto got;
  301. }
  302. block -= direct_blks;
  303. if (block < indirect_blks) {
  304. offset[n++] = NODE_IND1_BLOCK;
  305. noffset[n] = 3;
  306. offset[n++] = block / direct_blks;
  307. noffset[n] = 4 + offset[n - 1];
  308. offset[n++] = block % direct_blks;
  309. level = 2;
  310. goto got;
  311. }
  312. block -= indirect_blks;
  313. if (block < indirect_blks) {
  314. offset[n++] = NODE_IND2_BLOCK;
  315. noffset[n] = 4 + dptrs_per_blk;
  316. offset[n++] = block / direct_blks;
  317. noffset[n] = 5 + dptrs_per_blk + offset[n - 1];
  318. offset[n++] = block % direct_blks;
  319. level = 2;
  320. goto got;
  321. }
  322. block -= indirect_blks;
  323. if (block < dindirect_blks) {
  324. offset[n++] = NODE_DIND_BLOCK;
  325. noffset[n] = 5 + (dptrs_per_blk * 2);
  326. offset[n++] = block / indirect_blks;
  327. noffset[n] = 6 + (dptrs_per_blk * 2) +
  328. offset[n - 1] * (dptrs_per_blk + 1);
  329. offset[n++] = (block / direct_blks) % dptrs_per_blk;
  330. noffset[n] = 7 + (dptrs_per_blk * 2) +
  331. offset[n - 2] * (dptrs_per_blk + 1) +
  332. offset[n - 1];
  333. offset[n++] = block % direct_blks;
  334. level = 3;
  335. goto got;
  336. } else {
  337. BUG();
  338. }
  339. got:
  340. return level;
  341. }
  342. /*
  343. * Caller should call f2fs_put_dnode(dn).
  344. */
  345. int get_dnode_of_data(struct dnode_of_data *dn, pgoff_t index, int ro)
  346. {
  347. struct f2fs_sb_info *sbi = F2FS_SB(dn->inode->i_sb);
  348. struct page *npage[4];
  349. struct page *parent;
  350. int offset[4];
  351. unsigned int noffset[4];
  352. nid_t nids[4];
  353. int level, i;
  354. int err = 0;
  355. level = get_node_path(index, offset, noffset);
  356. nids[0] = dn->inode->i_ino;
  357. npage[0] = get_node_page(sbi, nids[0]);
  358. if (IS_ERR(npage[0]))
  359. return PTR_ERR(npage[0]);
  360. parent = npage[0];
  361. nids[1] = get_nid(parent, offset[0], true);
  362. dn->inode_page = npage[0];
  363. dn->inode_page_locked = true;
  364. /* get indirect or direct nodes */
  365. for (i = 1; i <= level; i++) {
  366. bool done = false;
  367. if (!nids[i] && !ro) {
  368. mutex_lock_op(sbi, NODE_NEW);
  369. /* alloc new node */
  370. if (!alloc_nid(sbi, &(nids[i]))) {
  371. mutex_unlock_op(sbi, NODE_NEW);
  372. err = -ENOSPC;
  373. goto release_pages;
  374. }
  375. dn->nid = nids[i];
  376. npage[i] = new_node_page(dn, noffset[i]);
  377. if (IS_ERR(npage[i])) {
  378. alloc_nid_failed(sbi, nids[i]);
  379. mutex_unlock_op(sbi, NODE_NEW);
  380. err = PTR_ERR(npage[i]);
  381. goto release_pages;
  382. }
  383. set_nid(parent, offset[i - 1], nids[i], i == 1);
  384. alloc_nid_done(sbi, nids[i]);
  385. mutex_unlock_op(sbi, NODE_NEW);
  386. done = true;
  387. } else if (ro && i == level && level > 1) {
  388. npage[i] = get_node_page_ra(parent, offset[i - 1]);
  389. if (IS_ERR(npage[i])) {
  390. err = PTR_ERR(npage[i]);
  391. goto release_pages;
  392. }
  393. done = true;
  394. }
  395. if (i == 1) {
  396. dn->inode_page_locked = false;
  397. unlock_page(parent);
  398. } else {
  399. f2fs_put_page(parent, 1);
  400. }
  401. if (!done) {
  402. npage[i] = get_node_page(sbi, nids[i]);
  403. if (IS_ERR(npage[i])) {
  404. err = PTR_ERR(npage[i]);
  405. f2fs_put_page(npage[0], 0);
  406. goto release_out;
  407. }
  408. }
  409. if (i < level) {
  410. parent = npage[i];
  411. nids[i + 1] = get_nid(parent, offset[i], false);
  412. }
  413. }
  414. dn->nid = nids[level];
  415. dn->ofs_in_node = offset[level];
  416. dn->node_page = npage[level];
  417. dn->data_blkaddr = datablock_addr(dn->node_page, dn->ofs_in_node);
  418. return 0;
  419. release_pages:
  420. f2fs_put_page(parent, 1);
  421. if (i > 1)
  422. f2fs_put_page(npage[0], 0);
  423. release_out:
  424. dn->inode_page = NULL;
  425. dn->node_page = NULL;
  426. return err;
  427. }
  428. static void truncate_node(struct dnode_of_data *dn)
  429. {
  430. struct f2fs_sb_info *sbi = F2FS_SB(dn->inode->i_sb);
  431. struct node_info ni;
  432. get_node_info(sbi, dn->nid, &ni);
  433. BUG_ON(ni.blk_addr == NULL_ADDR);
  434. if (ni.blk_addr != NULL_ADDR)
  435. invalidate_blocks(sbi, ni.blk_addr);
  436. /* Deallocate node address */
  437. dec_valid_node_count(sbi, dn->inode, 1);
  438. set_node_addr(sbi, &ni, NULL_ADDR);
  439. if (dn->nid == dn->inode->i_ino) {
  440. remove_orphan_inode(sbi, dn->nid);
  441. dec_valid_inode_count(sbi);
  442. } else {
  443. sync_inode_page(dn);
  444. }
  445. clear_node_page_dirty(dn->node_page);
  446. F2FS_SET_SB_DIRT(sbi);
  447. f2fs_put_page(dn->node_page, 1);
  448. dn->node_page = NULL;
  449. }
  450. static int truncate_dnode(struct dnode_of_data *dn)
  451. {
  452. struct f2fs_sb_info *sbi = F2FS_SB(dn->inode->i_sb);
  453. struct page *page;
  454. if (dn->nid == 0)
  455. return 1;
  456. /* get direct node */
  457. page = get_node_page(sbi, dn->nid);
  458. if (IS_ERR(page) && PTR_ERR(page) == -ENOENT)
  459. return 1;
  460. else if (IS_ERR(page))
  461. return PTR_ERR(page);
  462. /* Make dnode_of_data for parameter */
  463. dn->node_page = page;
  464. dn->ofs_in_node = 0;
  465. truncate_data_blocks(dn);
  466. truncate_node(dn);
  467. return 1;
  468. }
  469. static int truncate_nodes(struct dnode_of_data *dn, unsigned int nofs,
  470. int ofs, int depth)
  471. {
  472. struct f2fs_sb_info *sbi = F2FS_SB(dn->inode->i_sb);
  473. struct dnode_of_data rdn = *dn;
  474. struct page *page;
  475. struct f2fs_node *rn;
  476. nid_t child_nid;
  477. unsigned int child_nofs;
  478. int freed = 0;
  479. int i, ret;
  480. if (dn->nid == 0)
  481. return NIDS_PER_BLOCK + 1;
  482. page = get_node_page(sbi, dn->nid);
  483. if (IS_ERR(page))
  484. return PTR_ERR(page);
  485. rn = (struct f2fs_node *)page_address(page);
  486. if (depth < 3) {
  487. for (i = ofs; i < NIDS_PER_BLOCK; i++, freed++) {
  488. child_nid = le32_to_cpu(rn->in.nid[i]);
  489. if (child_nid == 0)
  490. continue;
  491. rdn.nid = child_nid;
  492. ret = truncate_dnode(&rdn);
  493. if (ret < 0)
  494. goto out_err;
  495. set_nid(page, i, 0, false);
  496. }
  497. } else {
  498. child_nofs = nofs + ofs * (NIDS_PER_BLOCK + 1) + 1;
  499. for (i = ofs; i < NIDS_PER_BLOCK; i++) {
  500. child_nid = le32_to_cpu(rn->in.nid[i]);
  501. if (child_nid == 0) {
  502. child_nofs += NIDS_PER_BLOCK + 1;
  503. continue;
  504. }
  505. rdn.nid = child_nid;
  506. ret = truncate_nodes(&rdn, child_nofs, 0, depth - 1);
  507. if (ret == (NIDS_PER_BLOCK + 1)) {
  508. set_nid(page, i, 0, false);
  509. child_nofs += ret;
  510. } else if (ret < 0 && ret != -ENOENT) {
  511. goto out_err;
  512. }
  513. }
  514. freed = child_nofs;
  515. }
  516. if (!ofs) {
  517. /* remove current indirect node */
  518. dn->node_page = page;
  519. truncate_node(dn);
  520. freed++;
  521. } else {
  522. f2fs_put_page(page, 1);
  523. }
  524. return freed;
  525. out_err:
  526. f2fs_put_page(page, 1);
  527. return ret;
  528. }
  529. static int truncate_partial_nodes(struct dnode_of_data *dn,
  530. struct f2fs_inode *ri, int *offset, int depth)
  531. {
  532. struct f2fs_sb_info *sbi = F2FS_SB(dn->inode->i_sb);
  533. struct page *pages[2];
  534. nid_t nid[3];
  535. nid_t child_nid;
  536. int err = 0;
  537. int i;
  538. int idx = depth - 2;
  539. nid[0] = le32_to_cpu(ri->i_nid[offset[0] - NODE_DIR1_BLOCK]);
  540. if (!nid[0])
  541. return 0;
  542. /* get indirect nodes in the path */
  543. for (i = 0; i < depth - 1; i++) {
  544. /* refernece count'll be increased */
  545. pages[i] = get_node_page(sbi, nid[i]);
  546. if (IS_ERR(pages[i])) {
  547. depth = i + 1;
  548. err = PTR_ERR(pages[i]);
  549. goto fail;
  550. }
  551. nid[i + 1] = get_nid(pages[i], offset[i + 1], false);
  552. }
  553. /* free direct nodes linked to a partial indirect node */
  554. for (i = offset[depth - 1]; i < NIDS_PER_BLOCK; i++) {
  555. child_nid = get_nid(pages[idx], i, false);
  556. if (!child_nid)
  557. continue;
  558. dn->nid = child_nid;
  559. err = truncate_dnode(dn);
  560. if (err < 0)
  561. goto fail;
  562. set_nid(pages[idx], i, 0, false);
  563. }
  564. if (offset[depth - 1] == 0) {
  565. dn->node_page = pages[idx];
  566. dn->nid = nid[idx];
  567. truncate_node(dn);
  568. } else {
  569. f2fs_put_page(pages[idx], 1);
  570. }
  571. offset[idx]++;
  572. offset[depth - 1] = 0;
  573. fail:
  574. for (i = depth - 3; i >= 0; i--)
  575. f2fs_put_page(pages[i], 1);
  576. return err;
  577. }
  578. /*
  579. * All the block addresses of data and nodes should be nullified.
  580. */
  581. int truncate_inode_blocks(struct inode *inode, pgoff_t from)
  582. {
  583. struct f2fs_sb_info *sbi = F2FS_SB(inode->i_sb);
  584. int err = 0, cont = 1;
  585. int level, offset[4], noffset[4];
  586. unsigned int nofs;
  587. struct f2fs_node *rn;
  588. struct dnode_of_data dn;
  589. struct page *page;
  590. level = get_node_path(from, offset, noffset);
  591. page = get_node_page(sbi, inode->i_ino);
  592. if (IS_ERR(page))
  593. return PTR_ERR(page);
  594. set_new_dnode(&dn, inode, page, NULL, 0);
  595. unlock_page(page);
  596. rn = page_address(page);
  597. switch (level) {
  598. case 0:
  599. case 1:
  600. nofs = noffset[1];
  601. break;
  602. case 2:
  603. nofs = noffset[1];
  604. if (!offset[level - 1])
  605. goto skip_partial;
  606. err = truncate_partial_nodes(&dn, &rn->i, offset, level);
  607. if (err < 0 && err != -ENOENT)
  608. goto fail;
  609. nofs += 1 + NIDS_PER_BLOCK;
  610. break;
  611. case 3:
  612. nofs = 5 + 2 * NIDS_PER_BLOCK;
  613. if (!offset[level - 1])
  614. goto skip_partial;
  615. err = truncate_partial_nodes(&dn, &rn->i, offset, level);
  616. if (err < 0 && err != -ENOENT)
  617. goto fail;
  618. break;
  619. default:
  620. BUG();
  621. }
  622. skip_partial:
  623. while (cont) {
  624. dn.nid = le32_to_cpu(rn->i.i_nid[offset[0] - NODE_DIR1_BLOCK]);
  625. switch (offset[0]) {
  626. case NODE_DIR1_BLOCK:
  627. case NODE_DIR2_BLOCK:
  628. err = truncate_dnode(&dn);
  629. break;
  630. case NODE_IND1_BLOCK:
  631. case NODE_IND2_BLOCK:
  632. err = truncate_nodes(&dn, nofs, offset[1], 2);
  633. break;
  634. case NODE_DIND_BLOCK:
  635. err = truncate_nodes(&dn, nofs, offset[1], 3);
  636. cont = 0;
  637. break;
  638. default:
  639. BUG();
  640. }
  641. if (err < 0 && err != -ENOENT)
  642. goto fail;
  643. if (offset[1] == 0 &&
  644. rn->i.i_nid[offset[0] - NODE_DIR1_BLOCK]) {
  645. lock_page(page);
  646. wait_on_page_writeback(page);
  647. rn->i.i_nid[offset[0] - NODE_DIR1_BLOCK] = 0;
  648. set_page_dirty(page);
  649. unlock_page(page);
  650. }
  651. offset[1] = 0;
  652. offset[0]++;
  653. nofs += err;
  654. }
  655. fail:
  656. f2fs_put_page(page, 0);
  657. return err > 0 ? 0 : err;
  658. }
  659. int remove_inode_page(struct inode *inode)
  660. {
  661. struct f2fs_sb_info *sbi = F2FS_SB(inode->i_sb);
  662. struct page *page;
  663. nid_t ino = inode->i_ino;
  664. struct dnode_of_data dn;
  665. mutex_lock_op(sbi, NODE_TRUNC);
  666. page = get_node_page(sbi, ino);
  667. if (IS_ERR(page)) {
  668. mutex_unlock_op(sbi, NODE_TRUNC);
  669. return PTR_ERR(page);
  670. }
  671. if (F2FS_I(inode)->i_xattr_nid) {
  672. nid_t nid = F2FS_I(inode)->i_xattr_nid;
  673. struct page *npage = get_node_page(sbi, nid);
  674. if (IS_ERR(npage)) {
  675. mutex_unlock_op(sbi, NODE_TRUNC);
  676. return PTR_ERR(npage);
  677. }
  678. F2FS_I(inode)->i_xattr_nid = 0;
  679. set_new_dnode(&dn, inode, page, npage, nid);
  680. dn.inode_page_locked = 1;
  681. truncate_node(&dn);
  682. }
  683. if (inode->i_blocks == 1) {
  684. /* inernally call f2fs_put_page() */
  685. set_new_dnode(&dn, inode, page, page, ino);
  686. truncate_node(&dn);
  687. } else if (inode->i_blocks == 0) {
  688. struct node_info ni;
  689. get_node_info(sbi, inode->i_ino, &ni);
  690. /* called after f2fs_new_inode() is failed */
  691. BUG_ON(ni.blk_addr != NULL_ADDR);
  692. f2fs_put_page(page, 1);
  693. } else {
  694. BUG();
  695. }
  696. mutex_unlock_op(sbi, NODE_TRUNC);
  697. return 0;
  698. }
  699. int new_inode_page(struct inode *inode, struct dentry *dentry)
  700. {
  701. struct f2fs_sb_info *sbi = F2FS_SB(inode->i_sb);
  702. struct page *page;
  703. struct dnode_of_data dn;
  704. /* allocate inode page for new inode */
  705. set_new_dnode(&dn, inode, NULL, NULL, inode->i_ino);
  706. mutex_lock_op(sbi, NODE_NEW);
  707. page = new_node_page(&dn, 0);
  708. init_dent_inode(dentry, page);
  709. mutex_unlock_op(sbi, NODE_NEW);
  710. if (IS_ERR(page))
  711. return PTR_ERR(page);
  712. f2fs_put_page(page, 1);
  713. return 0;
  714. }
  715. struct page *new_node_page(struct dnode_of_data *dn, unsigned int ofs)
  716. {
  717. struct f2fs_sb_info *sbi = F2FS_SB(dn->inode->i_sb);
  718. struct address_space *mapping = sbi->node_inode->i_mapping;
  719. struct node_info old_ni, new_ni;
  720. struct page *page;
  721. int err;
  722. if (is_inode_flag_set(F2FS_I(dn->inode), FI_NO_ALLOC))
  723. return ERR_PTR(-EPERM);
  724. page = grab_cache_page(mapping, dn->nid);
  725. if (!page)
  726. return ERR_PTR(-ENOMEM);
  727. get_node_info(sbi, dn->nid, &old_ni);
  728. SetPageUptodate(page);
  729. fill_node_footer(page, dn->nid, dn->inode->i_ino, ofs, true);
  730. /* Reinitialize old_ni with new node page */
  731. BUG_ON(old_ni.blk_addr != NULL_ADDR);
  732. new_ni = old_ni;
  733. new_ni.ino = dn->inode->i_ino;
  734. if (!inc_valid_node_count(sbi, dn->inode, 1)) {
  735. err = -ENOSPC;
  736. goto fail;
  737. }
  738. set_node_addr(sbi, &new_ni, NEW_ADDR);
  739. dn->node_page = page;
  740. sync_inode_page(dn);
  741. set_page_dirty(page);
  742. set_cold_node(dn->inode, page);
  743. if (ofs == 0)
  744. inc_valid_inode_count(sbi);
  745. return page;
  746. fail:
  747. f2fs_put_page(page, 1);
  748. return ERR_PTR(err);
  749. }
  750. static int read_node_page(struct page *page, int type)
  751. {
  752. struct f2fs_sb_info *sbi = F2FS_SB(page->mapping->host->i_sb);
  753. struct node_info ni;
  754. get_node_info(sbi, page->index, &ni);
  755. if (ni.blk_addr == NULL_ADDR)
  756. return -ENOENT;
  757. return f2fs_readpage(sbi, page, ni.blk_addr, type);
  758. }
  759. /*
  760. * Readahead a node page
  761. */
  762. void ra_node_page(struct f2fs_sb_info *sbi, nid_t nid)
  763. {
  764. struct address_space *mapping = sbi->node_inode->i_mapping;
  765. struct page *apage;
  766. apage = find_get_page(mapping, nid);
  767. if (apage && PageUptodate(apage))
  768. goto release_out;
  769. f2fs_put_page(apage, 0);
  770. apage = grab_cache_page(mapping, nid);
  771. if (!apage)
  772. return;
  773. if (read_node_page(apage, READA))
  774. goto unlock_out;
  775. page_cache_release(apage);
  776. return;
  777. unlock_out:
  778. unlock_page(apage);
  779. release_out:
  780. page_cache_release(apage);
  781. }
  782. struct page *get_node_page(struct f2fs_sb_info *sbi, pgoff_t nid)
  783. {
  784. int err;
  785. struct page *page;
  786. struct address_space *mapping = sbi->node_inode->i_mapping;
  787. page = grab_cache_page(mapping, nid);
  788. if (!page)
  789. return ERR_PTR(-ENOMEM);
  790. err = read_node_page(page, READ_SYNC);
  791. if (err) {
  792. f2fs_put_page(page, 1);
  793. return ERR_PTR(err);
  794. }
  795. BUG_ON(nid != nid_of_node(page));
  796. mark_page_accessed(page);
  797. return page;
  798. }
  799. /*
  800. * Return a locked page for the desired node page.
  801. * And, readahead MAX_RA_NODE number of node pages.
  802. */
  803. struct page *get_node_page_ra(struct page *parent, int start)
  804. {
  805. struct f2fs_sb_info *sbi = F2FS_SB(parent->mapping->host->i_sb);
  806. struct address_space *mapping = sbi->node_inode->i_mapping;
  807. int i, end;
  808. int err = 0;
  809. nid_t nid;
  810. struct page *page;
  811. /* First, try getting the desired direct node. */
  812. nid = get_nid(parent, start, false);
  813. if (!nid)
  814. return ERR_PTR(-ENOENT);
  815. page = find_get_page(mapping, nid);
  816. if (page && PageUptodate(page))
  817. goto page_hit;
  818. f2fs_put_page(page, 0);
  819. repeat:
  820. page = grab_cache_page(mapping, nid);
  821. if (!page)
  822. return ERR_PTR(-ENOMEM);
  823. err = read_node_page(page, READA);
  824. if (err) {
  825. f2fs_put_page(page, 1);
  826. return ERR_PTR(err);
  827. }
  828. /* Then, try readahead for siblings of the desired node */
  829. end = start + MAX_RA_NODE;
  830. end = min(end, NIDS_PER_BLOCK);
  831. for (i = start + 1; i < end; i++) {
  832. nid = get_nid(parent, i, false);
  833. if (!nid)
  834. continue;
  835. ra_node_page(sbi, nid);
  836. }
  837. page_hit:
  838. lock_page(page);
  839. if (PageError(page)) {
  840. f2fs_put_page(page, 1);
  841. return ERR_PTR(-EIO);
  842. }
  843. /* Has the page been truncated? */
  844. if (page->mapping != mapping) {
  845. f2fs_put_page(page, 1);
  846. goto repeat;
  847. }
  848. return page;
  849. }
  850. void sync_inode_page(struct dnode_of_data *dn)
  851. {
  852. if (IS_INODE(dn->node_page) || dn->inode_page == dn->node_page) {
  853. update_inode(dn->inode, dn->node_page);
  854. } else if (dn->inode_page) {
  855. if (!dn->inode_page_locked)
  856. lock_page(dn->inode_page);
  857. update_inode(dn->inode, dn->inode_page);
  858. if (!dn->inode_page_locked)
  859. unlock_page(dn->inode_page);
  860. } else {
  861. f2fs_write_inode(dn->inode, NULL);
  862. }
  863. }
  864. int sync_node_pages(struct f2fs_sb_info *sbi, nid_t ino,
  865. struct writeback_control *wbc)
  866. {
  867. struct address_space *mapping = sbi->node_inode->i_mapping;
  868. pgoff_t index, end;
  869. struct pagevec pvec;
  870. int step = ino ? 2 : 0;
  871. int nwritten = 0, wrote = 0;
  872. pagevec_init(&pvec, 0);
  873. next_step:
  874. index = 0;
  875. end = LONG_MAX;
  876. while (index <= end) {
  877. int i, nr_pages;
  878. nr_pages = pagevec_lookup_tag(&pvec, mapping, &index,
  879. PAGECACHE_TAG_DIRTY,
  880. min(end - index, (pgoff_t)PAGEVEC_SIZE-1) + 1);
  881. if (nr_pages == 0)
  882. break;
  883. for (i = 0; i < nr_pages; i++) {
  884. struct page *page = pvec.pages[i];
  885. /*
  886. * flushing sequence with step:
  887. * 0. indirect nodes
  888. * 1. dentry dnodes
  889. * 2. file dnodes
  890. */
  891. if (step == 0 && IS_DNODE(page))
  892. continue;
  893. if (step == 1 && (!IS_DNODE(page) ||
  894. is_cold_node(page)))
  895. continue;
  896. if (step == 2 && (!IS_DNODE(page) ||
  897. !is_cold_node(page)))
  898. continue;
  899. /*
  900. * If an fsync mode,
  901. * we should not skip writing node pages.
  902. */
  903. if (ino && ino_of_node(page) == ino)
  904. lock_page(page);
  905. else if (!trylock_page(page))
  906. continue;
  907. if (unlikely(page->mapping != mapping)) {
  908. continue_unlock:
  909. unlock_page(page);
  910. continue;
  911. }
  912. if (ino && ino_of_node(page) != ino)
  913. goto continue_unlock;
  914. if (!PageDirty(page)) {
  915. /* someone wrote it for us */
  916. goto continue_unlock;
  917. }
  918. if (!clear_page_dirty_for_io(page))
  919. goto continue_unlock;
  920. /* called by fsync() */
  921. if (ino && IS_DNODE(page)) {
  922. int mark = !is_checkpointed_node(sbi, ino);
  923. set_fsync_mark(page, 1);
  924. if (IS_INODE(page))
  925. set_dentry_mark(page, mark);
  926. nwritten++;
  927. } else {
  928. set_fsync_mark(page, 0);
  929. set_dentry_mark(page, 0);
  930. }
  931. mapping->a_ops->writepage(page, wbc);
  932. wrote++;
  933. if (--wbc->nr_to_write == 0)
  934. break;
  935. }
  936. pagevec_release(&pvec);
  937. cond_resched();
  938. if (wbc->nr_to_write == 0) {
  939. step = 2;
  940. break;
  941. }
  942. }
  943. if (step < 2) {
  944. step++;
  945. goto next_step;
  946. }
  947. if (wrote)
  948. f2fs_submit_bio(sbi, NODE, wbc->sync_mode == WB_SYNC_ALL);
  949. return nwritten;
  950. }
  951. static int f2fs_write_node_page(struct page *page,
  952. struct writeback_control *wbc)
  953. {
  954. struct f2fs_sb_info *sbi = F2FS_SB(page->mapping->host->i_sb);
  955. nid_t nid;
  956. unsigned int nofs;
  957. block_t new_addr;
  958. struct node_info ni;
  959. if (wbc->for_reclaim) {
  960. dec_page_count(sbi, F2FS_DIRTY_NODES);
  961. wbc->pages_skipped++;
  962. set_page_dirty(page);
  963. return AOP_WRITEPAGE_ACTIVATE;
  964. }
  965. wait_on_page_writeback(page);
  966. mutex_lock_op(sbi, NODE_WRITE);
  967. /* get old block addr of this node page */
  968. nid = nid_of_node(page);
  969. nofs = ofs_of_node(page);
  970. BUG_ON(page->index != nid);
  971. get_node_info(sbi, nid, &ni);
  972. /* This page is already truncated */
  973. if (ni.blk_addr == NULL_ADDR)
  974. return 0;
  975. set_page_writeback(page);
  976. /* insert node offset */
  977. write_node_page(sbi, page, nid, ni.blk_addr, &new_addr);
  978. set_node_addr(sbi, &ni, new_addr);
  979. dec_page_count(sbi, F2FS_DIRTY_NODES);
  980. mutex_unlock_op(sbi, NODE_WRITE);
  981. unlock_page(page);
  982. return 0;
  983. }
  984. static int f2fs_write_node_pages(struct address_space *mapping,
  985. struct writeback_control *wbc)
  986. {
  987. struct f2fs_sb_info *sbi = F2FS_SB(mapping->host->i_sb);
  988. struct block_device *bdev = sbi->sb->s_bdev;
  989. long nr_to_write = wbc->nr_to_write;
  990. if (wbc->for_kupdate)
  991. return 0;
  992. if (get_pages(sbi, F2FS_DIRTY_NODES) == 0)
  993. return 0;
  994. if (try_to_free_nats(sbi, NAT_ENTRY_PER_BLOCK)) {
  995. write_checkpoint(sbi, false, false);
  996. return 0;
  997. }
  998. /* if mounting is failed, skip writing node pages */
  999. wbc->nr_to_write = bio_get_nr_vecs(bdev);
  1000. sync_node_pages(sbi, 0, wbc);
  1001. wbc->nr_to_write = nr_to_write -
  1002. (bio_get_nr_vecs(bdev) - wbc->nr_to_write);
  1003. return 0;
  1004. }
  1005. static int f2fs_set_node_page_dirty(struct page *page)
  1006. {
  1007. struct address_space *mapping = page->mapping;
  1008. struct f2fs_sb_info *sbi = F2FS_SB(mapping->host->i_sb);
  1009. SetPageUptodate(page);
  1010. if (!PageDirty(page)) {
  1011. __set_page_dirty_nobuffers(page);
  1012. inc_page_count(sbi, F2FS_DIRTY_NODES);
  1013. SetPagePrivate(page);
  1014. return 1;
  1015. }
  1016. return 0;
  1017. }
  1018. static void f2fs_invalidate_node_page(struct page *page, unsigned long offset)
  1019. {
  1020. struct inode *inode = page->mapping->host;
  1021. struct f2fs_sb_info *sbi = F2FS_SB(inode->i_sb);
  1022. if (PageDirty(page))
  1023. dec_page_count(sbi, F2FS_DIRTY_NODES);
  1024. ClearPagePrivate(page);
  1025. }
  1026. static int f2fs_release_node_page(struct page *page, gfp_t wait)
  1027. {
  1028. ClearPagePrivate(page);
  1029. return 0;
  1030. }
  1031. /*
  1032. * Structure of the f2fs node operations
  1033. */
  1034. const struct address_space_operations f2fs_node_aops = {
  1035. .writepage = f2fs_write_node_page,
  1036. .writepages = f2fs_write_node_pages,
  1037. .set_page_dirty = f2fs_set_node_page_dirty,
  1038. .invalidatepage = f2fs_invalidate_node_page,
  1039. .releasepage = f2fs_release_node_page,
  1040. };
  1041. static struct free_nid *__lookup_free_nid_list(nid_t n, struct list_head *head)
  1042. {
  1043. struct list_head *this;
  1044. struct free_nid *i = NULL;
  1045. list_for_each(this, head) {
  1046. i = list_entry(this, struct free_nid, list);
  1047. if (i->nid == n)
  1048. break;
  1049. i = NULL;
  1050. }
  1051. return i;
  1052. }
  1053. static void __del_from_free_nid_list(struct free_nid *i)
  1054. {
  1055. list_del(&i->list);
  1056. kmem_cache_free(free_nid_slab, i);
  1057. }
  1058. static int add_free_nid(struct f2fs_nm_info *nm_i, nid_t nid)
  1059. {
  1060. struct free_nid *i;
  1061. if (nm_i->fcnt > 2 * MAX_FREE_NIDS)
  1062. return 0;
  1063. retry:
  1064. i = kmem_cache_alloc(free_nid_slab, GFP_NOFS);
  1065. if (!i) {
  1066. cond_resched();
  1067. goto retry;
  1068. }
  1069. i->nid = nid;
  1070. i->state = NID_NEW;
  1071. spin_lock(&nm_i->free_nid_list_lock);
  1072. if (__lookup_free_nid_list(nid, &nm_i->free_nid_list)) {
  1073. spin_unlock(&nm_i->free_nid_list_lock);
  1074. kmem_cache_free(free_nid_slab, i);
  1075. return 0;
  1076. }
  1077. list_add_tail(&i->list, &nm_i->free_nid_list);
  1078. nm_i->fcnt++;
  1079. spin_unlock(&nm_i->free_nid_list_lock);
  1080. return 1;
  1081. }
  1082. static void remove_free_nid(struct f2fs_nm_info *nm_i, nid_t nid)
  1083. {
  1084. struct free_nid *i;
  1085. spin_lock(&nm_i->free_nid_list_lock);
  1086. i = __lookup_free_nid_list(nid, &nm_i->free_nid_list);
  1087. if (i && i->state == NID_NEW) {
  1088. __del_from_free_nid_list(i);
  1089. nm_i->fcnt--;
  1090. }
  1091. spin_unlock(&nm_i->free_nid_list_lock);
  1092. }
  1093. static int scan_nat_page(struct f2fs_nm_info *nm_i,
  1094. struct page *nat_page, nid_t start_nid)
  1095. {
  1096. struct f2fs_nat_block *nat_blk = page_address(nat_page);
  1097. block_t blk_addr;
  1098. int fcnt = 0;
  1099. int i;
  1100. /* 0 nid should not be used */
  1101. if (start_nid == 0)
  1102. ++start_nid;
  1103. i = start_nid % NAT_ENTRY_PER_BLOCK;
  1104. for (; i < NAT_ENTRY_PER_BLOCK; i++, start_nid++) {
  1105. blk_addr = le32_to_cpu(nat_blk->entries[i].block_addr);
  1106. BUG_ON(blk_addr == NEW_ADDR);
  1107. if (blk_addr == NULL_ADDR)
  1108. fcnt += add_free_nid(nm_i, start_nid);
  1109. }
  1110. return fcnt;
  1111. }
  1112. static void build_free_nids(struct f2fs_sb_info *sbi)
  1113. {
  1114. struct free_nid *fnid, *next_fnid;
  1115. struct f2fs_nm_info *nm_i = NM_I(sbi);
  1116. struct curseg_info *curseg = CURSEG_I(sbi, CURSEG_HOT_DATA);
  1117. struct f2fs_summary_block *sum = curseg->sum_blk;
  1118. nid_t nid = 0;
  1119. bool is_cycled = false;
  1120. int fcnt = 0;
  1121. int i;
  1122. nid = nm_i->next_scan_nid;
  1123. nm_i->init_scan_nid = nid;
  1124. ra_nat_pages(sbi, nid);
  1125. while (1) {
  1126. struct page *page = get_current_nat_page(sbi, nid);
  1127. fcnt += scan_nat_page(nm_i, page, nid);
  1128. f2fs_put_page(page, 1);
  1129. nid += (NAT_ENTRY_PER_BLOCK - (nid % NAT_ENTRY_PER_BLOCK));
  1130. if (nid >= nm_i->max_nid) {
  1131. nid = 0;
  1132. is_cycled = true;
  1133. }
  1134. if (fcnt > MAX_FREE_NIDS)
  1135. break;
  1136. if (is_cycled && nm_i->init_scan_nid <= nid)
  1137. break;
  1138. }
  1139. nm_i->next_scan_nid = nid;
  1140. /* find free nids from current sum_pages */
  1141. mutex_lock(&curseg->curseg_mutex);
  1142. for (i = 0; i < nats_in_cursum(sum); i++) {
  1143. block_t addr = le32_to_cpu(nat_in_journal(sum, i).block_addr);
  1144. nid = le32_to_cpu(nid_in_journal(sum, i));
  1145. if (addr == NULL_ADDR)
  1146. add_free_nid(nm_i, nid);
  1147. else
  1148. remove_free_nid(nm_i, nid);
  1149. }
  1150. mutex_unlock(&curseg->curseg_mutex);
  1151. /* remove the free nids from current allocated nids */
  1152. list_for_each_entry_safe(fnid, next_fnid, &nm_i->free_nid_list, list) {
  1153. struct nat_entry *ne;
  1154. read_lock(&nm_i->nat_tree_lock);
  1155. ne = __lookup_nat_cache(nm_i, fnid->nid);
  1156. if (ne && nat_get_blkaddr(ne) != NULL_ADDR)
  1157. remove_free_nid(nm_i, fnid->nid);
  1158. read_unlock(&nm_i->nat_tree_lock);
  1159. }
  1160. }
  1161. /*
  1162. * If this function returns success, caller can obtain a new nid
  1163. * from second parameter of this function.
  1164. * The returned nid could be used ino as well as nid when inode is created.
  1165. */
  1166. bool alloc_nid(struct f2fs_sb_info *sbi, nid_t *nid)
  1167. {
  1168. struct f2fs_nm_info *nm_i = NM_I(sbi);
  1169. struct free_nid *i = NULL;
  1170. struct list_head *this;
  1171. retry:
  1172. mutex_lock(&nm_i->build_lock);
  1173. if (!nm_i->fcnt) {
  1174. /* scan NAT in order to build free nid list */
  1175. build_free_nids(sbi);
  1176. if (!nm_i->fcnt) {
  1177. mutex_unlock(&nm_i->build_lock);
  1178. return false;
  1179. }
  1180. }
  1181. mutex_unlock(&nm_i->build_lock);
  1182. /*
  1183. * We check fcnt again since previous check is racy as
  1184. * we didn't hold free_nid_list_lock. So other thread
  1185. * could consume all of free nids.
  1186. */
  1187. spin_lock(&nm_i->free_nid_list_lock);
  1188. if (!nm_i->fcnt) {
  1189. spin_unlock(&nm_i->free_nid_list_lock);
  1190. goto retry;
  1191. }
  1192. BUG_ON(list_empty(&nm_i->free_nid_list));
  1193. list_for_each(this, &nm_i->free_nid_list) {
  1194. i = list_entry(this, struct free_nid, list);
  1195. if (i->state == NID_NEW)
  1196. break;
  1197. }
  1198. BUG_ON(i->state != NID_NEW);
  1199. *nid = i->nid;
  1200. i->state = NID_ALLOC;
  1201. nm_i->fcnt--;
  1202. spin_unlock(&nm_i->free_nid_list_lock);
  1203. return true;
  1204. }
  1205. /*
  1206. * alloc_nid() should be called prior to this function.
  1207. */
  1208. void alloc_nid_done(struct f2fs_sb_info *sbi, nid_t nid)
  1209. {
  1210. struct f2fs_nm_info *nm_i = NM_I(sbi);
  1211. struct free_nid *i;
  1212. spin_lock(&nm_i->free_nid_list_lock);
  1213. i = __lookup_free_nid_list(nid, &nm_i->free_nid_list);
  1214. if (i) {
  1215. BUG_ON(i->state != NID_ALLOC);
  1216. __del_from_free_nid_list(i);
  1217. }
  1218. spin_unlock(&nm_i->free_nid_list_lock);
  1219. }
  1220. /*
  1221. * alloc_nid() should be called prior to this function.
  1222. */
  1223. void alloc_nid_failed(struct f2fs_sb_info *sbi, nid_t nid)
  1224. {
  1225. alloc_nid_done(sbi, nid);
  1226. add_free_nid(NM_I(sbi), nid);
  1227. }
  1228. void recover_node_page(struct f2fs_sb_info *sbi, struct page *page,
  1229. struct f2fs_summary *sum, struct node_info *ni,
  1230. block_t new_blkaddr)
  1231. {
  1232. rewrite_node_page(sbi, page, sum, ni->blk_addr, new_blkaddr);
  1233. set_node_addr(sbi, ni, new_blkaddr);
  1234. clear_node_page_dirty(page);
  1235. }
  1236. int recover_inode_page(struct f2fs_sb_info *sbi, struct page *page)
  1237. {
  1238. struct address_space *mapping = sbi->node_inode->i_mapping;
  1239. struct f2fs_node *src, *dst;
  1240. nid_t ino = ino_of_node(page);
  1241. struct node_info old_ni, new_ni;
  1242. struct page *ipage;
  1243. ipage = grab_cache_page(mapping, ino);
  1244. if (!ipage)
  1245. return -ENOMEM;
  1246. /* Should not use this inode from free nid list */
  1247. remove_free_nid(NM_I(sbi), ino);
  1248. get_node_info(sbi, ino, &old_ni);
  1249. SetPageUptodate(ipage);
  1250. fill_node_footer(ipage, ino, ino, 0, true);
  1251. src = (struct f2fs_node *)page_address(page);
  1252. dst = (struct f2fs_node *)page_address(ipage);
  1253. memcpy(dst, src, (unsigned long)&src->i.i_ext - (unsigned long)&src->i);
  1254. dst->i.i_size = 0;
  1255. dst->i.i_blocks = cpu_to_le64(1);
  1256. dst->i.i_links = cpu_to_le32(1);
  1257. dst->i.i_xattr_nid = 0;
  1258. new_ni = old_ni;
  1259. new_ni.ino = ino;
  1260. set_node_addr(sbi, &new_ni, NEW_ADDR);
  1261. inc_valid_inode_count(sbi);
  1262. f2fs_put_page(ipage, 1);
  1263. return 0;
  1264. }
  1265. int restore_node_summary(struct f2fs_sb_info *sbi,
  1266. unsigned int segno, struct f2fs_summary_block *sum)
  1267. {
  1268. struct f2fs_node *rn;
  1269. struct f2fs_summary *sum_entry;
  1270. struct page *page;
  1271. block_t addr;
  1272. int i, last_offset;
  1273. /* alloc temporal page for read node */
  1274. page = alloc_page(GFP_NOFS | __GFP_ZERO);
  1275. if (IS_ERR(page))
  1276. return PTR_ERR(page);
  1277. lock_page(page);
  1278. /* scan the node segment */
  1279. last_offset = sbi->blocks_per_seg;
  1280. addr = START_BLOCK(sbi, segno);
  1281. sum_entry = &sum->entries[0];
  1282. for (i = 0; i < last_offset; i++, sum_entry++) {
  1283. if (f2fs_readpage(sbi, page, addr, READ_SYNC))
  1284. goto out;
  1285. rn = (struct f2fs_node *)page_address(page);
  1286. sum_entry->nid = rn->footer.nid;
  1287. sum_entry->version = 0;
  1288. sum_entry->ofs_in_node = 0;
  1289. addr++;
  1290. /*
  1291. * In order to read next node page,
  1292. * we must clear PageUptodate flag.
  1293. */
  1294. ClearPageUptodate(page);
  1295. }
  1296. out:
  1297. unlock_page(page);
  1298. __free_pages(page, 0);
  1299. return 0;
  1300. }
  1301. static bool flush_nats_in_journal(struct f2fs_sb_info *sbi)
  1302. {
  1303. struct f2fs_nm_info *nm_i = NM_I(sbi);
  1304. struct curseg_info *curseg = CURSEG_I(sbi, CURSEG_HOT_DATA);
  1305. struct f2fs_summary_block *sum = curseg->sum_blk;
  1306. int i;
  1307. mutex_lock(&curseg->curseg_mutex);
  1308. if (nats_in_cursum(sum) < NAT_JOURNAL_ENTRIES) {
  1309. mutex_unlock(&curseg->curseg_mutex);
  1310. return false;
  1311. }
  1312. for (i = 0; i < nats_in_cursum(sum); i++) {
  1313. struct nat_entry *ne;
  1314. struct f2fs_nat_entry raw_ne;
  1315. nid_t nid = le32_to_cpu(nid_in_journal(sum, i));
  1316. raw_ne = nat_in_journal(sum, i);
  1317. retry:
  1318. write_lock(&nm_i->nat_tree_lock);
  1319. ne = __lookup_nat_cache(nm_i, nid);
  1320. if (ne) {
  1321. __set_nat_cache_dirty(nm_i, ne);
  1322. write_unlock(&nm_i->nat_tree_lock);
  1323. continue;
  1324. }
  1325. ne = grab_nat_entry(nm_i, nid);
  1326. if (!ne) {
  1327. write_unlock(&nm_i->nat_tree_lock);
  1328. goto retry;
  1329. }
  1330. nat_set_blkaddr(ne, le32_to_cpu(raw_ne.block_addr));
  1331. nat_set_ino(ne, le32_to_cpu(raw_ne.ino));
  1332. nat_set_version(ne, raw_ne.version);
  1333. __set_nat_cache_dirty(nm_i, ne);
  1334. write_unlock(&nm_i->nat_tree_lock);
  1335. }
  1336. update_nats_in_cursum(sum, -i);
  1337. mutex_unlock(&curseg->curseg_mutex);
  1338. return true;
  1339. }
  1340. /*
  1341. * This function is called during the checkpointing process.
  1342. */
  1343. void flush_nat_entries(struct f2fs_sb_info *sbi)
  1344. {
  1345. struct f2fs_nm_info *nm_i = NM_I(sbi);
  1346. struct curseg_info *curseg = CURSEG_I(sbi, CURSEG_HOT_DATA);
  1347. struct f2fs_summary_block *sum = curseg->sum_blk;
  1348. struct list_head *cur, *n;
  1349. struct page *page = NULL;
  1350. struct f2fs_nat_block *nat_blk = NULL;
  1351. nid_t start_nid = 0, end_nid = 0;
  1352. bool flushed;
  1353. flushed = flush_nats_in_journal(sbi);
  1354. if (!flushed)
  1355. mutex_lock(&curseg->curseg_mutex);
  1356. /* 1) flush dirty nat caches */
  1357. list_for_each_safe(cur, n, &nm_i->dirty_nat_entries) {
  1358. struct nat_entry *ne;
  1359. nid_t nid;
  1360. struct f2fs_nat_entry raw_ne;
  1361. int offset = -1;
  1362. block_t old_blkaddr, new_blkaddr;
  1363. ne = list_entry(cur, struct nat_entry, list);
  1364. nid = nat_get_nid(ne);
  1365. if (nat_get_blkaddr(ne) == NEW_ADDR)
  1366. continue;
  1367. if (flushed)
  1368. goto to_nat_page;
  1369. /* if there is room for nat enries in curseg->sumpage */
  1370. offset = lookup_journal_in_cursum(sum, NAT_JOURNAL, nid, 1);
  1371. if (offset >= 0) {
  1372. raw_ne = nat_in_journal(sum, offset);
  1373. old_blkaddr = le32_to_cpu(raw_ne.block_addr);
  1374. goto flush_now;
  1375. }
  1376. to_nat_page:
  1377. if (!page || (start_nid > nid || nid > end_nid)) {
  1378. if (page) {
  1379. f2fs_put_page(page, 1);
  1380. page = NULL;
  1381. }
  1382. start_nid = START_NID(nid);
  1383. end_nid = start_nid + NAT_ENTRY_PER_BLOCK - 1;
  1384. /*
  1385. * get nat block with dirty flag, increased reference
  1386. * count, mapped and lock
  1387. */
  1388. page = get_next_nat_page(sbi, start_nid);
  1389. nat_blk = page_address(page);
  1390. }
  1391. BUG_ON(!nat_blk);
  1392. raw_ne = nat_blk->entries[nid - start_nid];
  1393. old_blkaddr = le32_to_cpu(raw_ne.block_addr);
  1394. flush_now:
  1395. new_blkaddr = nat_get_blkaddr(ne);
  1396. raw_ne.ino = cpu_to_le32(nat_get_ino(ne));
  1397. raw_ne.block_addr = cpu_to_le32(new_blkaddr);
  1398. raw_ne.version = nat_get_version(ne);
  1399. if (offset < 0) {
  1400. nat_blk->entries[nid - start_nid] = raw_ne;
  1401. } else {
  1402. nat_in_journal(sum, offset) = raw_ne;
  1403. nid_in_journal(sum, offset) = cpu_to_le32(nid);
  1404. }
  1405. if (nat_get_blkaddr(ne) == NULL_ADDR) {
  1406. write_lock(&nm_i->nat_tree_lock);
  1407. __del_from_nat_cache(nm_i, ne);
  1408. write_unlock(&nm_i->nat_tree_lock);
  1409. /* We can reuse this freed nid at this point */
  1410. add_free_nid(NM_I(sbi), nid);
  1411. } else {
  1412. write_lock(&nm_i->nat_tree_lock);
  1413. __clear_nat_cache_dirty(nm_i, ne);
  1414. ne->checkpointed = true;
  1415. write_unlock(&nm_i->nat_tree_lock);
  1416. }
  1417. }
  1418. if (!flushed)
  1419. mutex_unlock(&curseg->curseg_mutex);
  1420. f2fs_put_page(page, 1);
  1421. /* 2) shrink nat caches if necessary */
  1422. try_to_free_nats(sbi, nm_i->nat_cnt - NM_WOUT_THRESHOLD);
  1423. }
  1424. static int init_node_manager(struct f2fs_sb_info *sbi)
  1425. {
  1426. struct f2fs_super_block *sb_raw = F2FS_RAW_SUPER(sbi);
  1427. struct f2fs_nm_info *nm_i = NM_I(sbi);
  1428. unsigned char *version_bitmap;
  1429. unsigned int nat_segs, nat_blocks;
  1430. nm_i->nat_blkaddr = le32_to_cpu(sb_raw->nat_blkaddr);
  1431. /* segment_count_nat includes pair segment so divide to 2. */
  1432. nat_segs = le32_to_cpu(sb_raw->segment_count_nat) >> 1;
  1433. nat_blocks = nat_segs << le32_to_cpu(sb_raw->log_blocks_per_seg);
  1434. nm_i->max_nid = NAT_ENTRY_PER_BLOCK * nat_blocks;
  1435. nm_i->fcnt = 0;
  1436. nm_i->nat_cnt = 0;
  1437. INIT_LIST_HEAD(&nm_i->free_nid_list);
  1438. INIT_RADIX_TREE(&nm_i->nat_root, GFP_ATOMIC);
  1439. INIT_LIST_HEAD(&nm_i->nat_entries);
  1440. INIT_LIST_HEAD(&nm_i->dirty_nat_entries);
  1441. mutex_init(&nm_i->build_lock);
  1442. spin_lock_init(&nm_i->free_nid_list_lock);
  1443. rwlock_init(&nm_i->nat_tree_lock);
  1444. nm_i->bitmap_size = __bitmap_size(sbi, NAT_BITMAP);
  1445. nm_i->init_scan_nid = le32_to_cpu(sbi->ckpt->next_free_nid);
  1446. nm_i->next_scan_nid = le32_to_cpu(sbi->ckpt->next_free_nid);
  1447. nm_i->nat_bitmap = kzalloc(nm_i->bitmap_size, GFP_KERNEL);
  1448. if (!nm_i->nat_bitmap)
  1449. return -ENOMEM;
  1450. version_bitmap = __bitmap_ptr(sbi, NAT_BITMAP);
  1451. if (!version_bitmap)
  1452. return -EFAULT;
  1453. /* copy version bitmap */
  1454. memcpy(nm_i->nat_bitmap, version_bitmap, nm_i->bitmap_size);
  1455. return 0;
  1456. }
  1457. int build_node_manager(struct f2fs_sb_info *sbi)
  1458. {
  1459. int err;
  1460. sbi->nm_info = kzalloc(sizeof(struct f2fs_nm_info), GFP_KERNEL);
  1461. if (!sbi->nm_info)
  1462. return -ENOMEM;
  1463. err = init_node_manager(sbi);
  1464. if (err)
  1465. return err;
  1466. build_free_nids(sbi);
  1467. return 0;
  1468. }
  1469. void destroy_node_manager(struct f2fs_sb_info *sbi)
  1470. {
  1471. struct f2fs_nm_info *nm_i = NM_I(sbi);
  1472. struct free_nid *i, *next_i;
  1473. struct nat_entry *natvec[NATVEC_SIZE];
  1474. nid_t nid = 0;
  1475. unsigned int found;
  1476. if (!nm_i)
  1477. return;
  1478. /* destroy free nid list */
  1479. spin_lock(&nm_i->free_nid_list_lock);
  1480. list_for_each_entry_safe(i, next_i, &nm_i->free_nid_list, list) {
  1481. BUG_ON(i->state == NID_ALLOC);
  1482. __del_from_free_nid_list(i);
  1483. nm_i->fcnt--;
  1484. }
  1485. BUG_ON(nm_i->fcnt);
  1486. spin_unlock(&nm_i->free_nid_list_lock);
  1487. /* destroy nat cache */
  1488. write_lock(&nm_i->nat_tree_lock);
  1489. while ((found = __gang_lookup_nat_cache(nm_i,
  1490. nid, NATVEC_SIZE, natvec))) {
  1491. unsigned idx;
  1492. for (idx = 0; idx < found; idx++) {
  1493. struct nat_entry *e = natvec[idx];
  1494. nid = nat_get_nid(e) + 1;
  1495. __del_from_nat_cache(nm_i, e);
  1496. }
  1497. }
  1498. BUG_ON(nm_i->nat_cnt);
  1499. write_unlock(&nm_i->nat_tree_lock);
  1500. kfree(nm_i->nat_bitmap);
  1501. sbi->nm_info = NULL;
  1502. kfree(nm_i);
  1503. }
  1504. int create_node_manager_caches(void)
  1505. {
  1506. nat_entry_slab = f2fs_kmem_cache_create("nat_entry",
  1507. sizeof(struct nat_entry), NULL);
  1508. if (!nat_entry_slab)
  1509. return -ENOMEM;
  1510. free_nid_slab = f2fs_kmem_cache_create("free_nid",
  1511. sizeof(struct free_nid), NULL);
  1512. if (!free_nid_slab) {
  1513. kmem_cache_destroy(nat_entry_slab);
  1514. return -ENOMEM;
  1515. }
  1516. return 0;
  1517. }
  1518. void destroy_node_manager_caches(void)
  1519. {
  1520. kmem_cache_destroy(free_nid_slab);
  1521. kmem_cache_destroy(nat_entry_slab);
  1522. }