runlist.c 59 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110111111121113111411151116111711181119112011211122112311241125112611271128112911301131113211331134113511361137113811391140114111421143114411451146114711481149115011511152115311541155115611571158115911601161116211631164116511661167116811691170117111721173117411751176117711781179118011811182118311841185118611871188118911901191119211931194119511961197119811991200120112021203120412051206120712081209121012111212121312141215121612171218121912201221122212231224122512261227122812291230123112321233123412351236123712381239124012411242124312441245124612471248124912501251125212531254125512561257125812591260126112621263126412651266126712681269127012711272127312741275127612771278127912801281128212831284128512861287128812891290129112921293129412951296129712981299130013011302130313041305130613071308130913101311131213131314131513161317131813191320132113221323132413251326132713281329133013311332133313341335133613371338133913401341134213431344134513461347134813491350135113521353135413551356135713581359136013611362136313641365136613671368136913701371137213731374137513761377137813791380138113821383138413851386138713881389139013911392139313941395139613971398139914001401140214031404140514061407140814091410141114121413141414151416141714181419142014211422142314241425142614271428142914301431143214331434143514361437143814391440144114421443144414451446144714481449145014511452145314541455145614571458145914601461146214631464146514661467146814691470147114721473147414751476147714781479148014811482148314841485148614871488148914901491149214931494149514961497149814991500150115021503150415051506150715081509151015111512151315141515151615171518151915201521152215231524152515261527152815291530153115321533153415351536153715381539154015411542154315441545154615471548154915501551155215531554155515561557155815591560156115621563156415651566156715681569157015711572157315741575157615771578157915801581158215831584158515861587158815891590159115921593159415951596159715981599160016011602160316041605160616071608160916101611161216131614161516161617161816191620162116221623162416251626162716281629163016311632163316341635163616371638163916401641164216431644164516461647164816491650165116521653165416551656165716581659166016611662166316641665166616671668166916701671167216731674167516761677167816791680168116821683168416851686168716881689169016911692169316941695169616971698169917001701170217031704170517061707170817091710171117121713171417151716171717181719172017211722172317241725172617271728172917301731173217331734173517361737173817391740174117421743174417451746174717481749175017511752175317541755175617571758175917601761176217631764176517661767176817691770177117721773177417751776177717781779178017811782178317841785178617871788178917901791179217931794179517961797179817991800180118021803180418051806180718081809181018111812181318141815181618171818181918201821182218231824182518261827182818291830183118321833183418351836183718381839184018411842184318441845184618471848184918501851185218531854185518561857185818591860186118621863186418651866186718681869187018711872187318741875187618771878187918801881188218831884188518861887188818891890189118921893
  1. // SPDX-License-Identifier: GPL-2.0-or-later
  2. /**
  3. * runlist.c - NTFS runlist handling code. Part of the Linux-NTFS project.
  4. *
  5. * Copyright (c) 2001-2007 Anton Altaparmakov
  6. * Copyright (c) 2002-2005 Richard Russon
  7. */
  8. #include "debug.h"
  9. #include "dir.h"
  10. #include "endian.h"
  11. #include "malloc.h"
  12. #include "ntfs.h"
  13. /**
  14. * ntfs_rl_mm - runlist memmove
  15. *
  16. * It is up to the caller to serialize access to the runlist @base.
  17. */
  18. static inline void ntfs_rl_mm(runlist_element *base, int dst, int src,
  19. int size)
  20. {
  21. if (likely((dst != src) && (size > 0)))
  22. memmove(base + dst, base + src, size * sizeof(*base));
  23. }
  24. /**
  25. * ntfs_rl_mc - runlist memory copy
  26. *
  27. * It is up to the caller to serialize access to the runlists @dstbase and
  28. * @srcbase.
  29. */
  30. static inline void ntfs_rl_mc(runlist_element *dstbase, int dst,
  31. runlist_element *srcbase, int src, int size)
  32. {
  33. if (likely(size > 0))
  34. memcpy(dstbase + dst, srcbase + src, size * sizeof(*dstbase));
  35. }
  36. /**
  37. * ntfs_rl_realloc - Reallocate memory for runlists
  38. * @rl: original runlist
  39. * @old_size: number of runlist elements in the original runlist @rl
  40. * @new_size: number of runlist elements we need space for
  41. *
  42. * As the runlists grow, more memory will be required. To prevent the
  43. * kernel having to allocate and reallocate large numbers of small bits of
  44. * memory, this function returns an entire page of memory.
  45. *
  46. * It is up to the caller to serialize access to the runlist @rl.
  47. *
  48. * N.B. If the new allocation doesn't require a different number of pages in
  49. * memory, the function will return the original pointer.
  50. *
  51. * On success, return a pointer to the newly allocated, or recycled, memory.
  52. * On error, return -errno. The following error codes are defined:
  53. * -ENOMEM - Not enough memory to allocate runlist array.
  54. * -EINVAL - Invalid parameters were passed in.
  55. */
  56. static inline runlist_element *ntfs_rl_realloc(runlist_element *rl,
  57. int old_size, int new_size)
  58. {
  59. runlist_element *new_rl;
  60. old_size = PAGE_ALIGN(old_size * sizeof(*rl));
  61. new_size = PAGE_ALIGN(new_size * sizeof(*rl));
  62. if (old_size == new_size)
  63. return rl;
  64. new_rl = ntfs_malloc_nofs(new_size);
  65. if (unlikely(!new_rl))
  66. return ERR_PTR(-ENOMEM);
  67. if (likely(rl != NULL)) {
  68. if (unlikely(old_size > new_size))
  69. old_size = new_size;
  70. memcpy(new_rl, rl, old_size);
  71. ntfs_free(rl);
  72. }
  73. return new_rl;
  74. }
  75. /**
  76. * ntfs_rl_realloc_nofail - Reallocate memory for runlists
  77. * @rl: original runlist
  78. * @old_size: number of runlist elements in the original runlist @rl
  79. * @new_size: number of runlist elements we need space for
  80. *
  81. * As the runlists grow, more memory will be required. To prevent the
  82. * kernel having to allocate and reallocate large numbers of small bits of
  83. * memory, this function returns an entire page of memory.
  84. *
  85. * This function guarantees that the allocation will succeed. It will sleep
  86. * for as long as it takes to complete the allocation.
  87. *
  88. * It is up to the caller to serialize access to the runlist @rl.
  89. *
  90. * N.B. If the new allocation doesn't require a different number of pages in
  91. * memory, the function will return the original pointer.
  92. *
  93. * On success, return a pointer to the newly allocated, or recycled, memory.
  94. * On error, return -errno. The following error codes are defined:
  95. * -ENOMEM - Not enough memory to allocate runlist array.
  96. * -EINVAL - Invalid parameters were passed in.
  97. */
  98. static inline runlist_element *ntfs_rl_realloc_nofail(runlist_element *rl,
  99. int old_size, int new_size)
  100. {
  101. runlist_element *new_rl;
  102. old_size = PAGE_ALIGN(old_size * sizeof(*rl));
  103. new_size = PAGE_ALIGN(new_size * sizeof(*rl));
  104. if (old_size == new_size)
  105. return rl;
  106. new_rl = ntfs_malloc_nofs_nofail(new_size);
  107. BUG_ON(!new_rl);
  108. if (likely(rl != NULL)) {
  109. if (unlikely(old_size > new_size))
  110. old_size = new_size;
  111. memcpy(new_rl, rl, old_size);
  112. ntfs_free(rl);
  113. }
  114. return new_rl;
  115. }
  116. /**
  117. * ntfs_are_rl_mergeable - test if two runlists can be joined together
  118. * @dst: original runlist
  119. * @src: new runlist to test for mergeability with @dst
  120. *
  121. * Test if two runlists can be joined together. For this, their VCNs and LCNs
  122. * must be adjacent.
  123. *
  124. * It is up to the caller to serialize access to the runlists @dst and @src.
  125. *
  126. * Return: true Success, the runlists can be merged.
  127. * false Failure, the runlists cannot be merged.
  128. */
  129. static inline bool ntfs_are_rl_mergeable(runlist_element *dst,
  130. runlist_element *src)
  131. {
  132. BUG_ON(!dst);
  133. BUG_ON(!src);
  134. /* We can merge unmapped regions even if they are misaligned. */
  135. if ((dst->lcn == LCN_RL_NOT_MAPPED) && (src->lcn == LCN_RL_NOT_MAPPED))
  136. return true;
  137. /* If the runs are misaligned, we cannot merge them. */
  138. if ((dst->vcn + dst->length) != src->vcn)
  139. return false;
  140. /* If both runs are non-sparse and contiguous, we can merge them. */
  141. if ((dst->lcn >= 0) && (src->lcn >= 0) &&
  142. ((dst->lcn + dst->length) == src->lcn))
  143. return true;
  144. /* If we are merging two holes, we can merge them. */
  145. if ((dst->lcn == LCN_HOLE) && (src->lcn == LCN_HOLE))
  146. return true;
  147. /* Cannot merge. */
  148. return false;
  149. }
  150. /**
  151. * __ntfs_rl_merge - merge two runlists without testing if they can be merged
  152. * @dst: original, destination runlist
  153. * @src: new runlist to merge with @dst
  154. *
  155. * Merge the two runlists, writing into the destination runlist @dst. The
  156. * caller must make sure the runlists can be merged or this will corrupt the
  157. * destination runlist.
  158. *
  159. * It is up to the caller to serialize access to the runlists @dst and @src.
  160. */
  161. static inline void __ntfs_rl_merge(runlist_element *dst, runlist_element *src)
  162. {
  163. dst->length += src->length;
  164. }
  165. /**
  166. * ntfs_rl_append - append a runlist after a given element
  167. * @dst: original runlist to be worked on
  168. * @dsize: number of elements in @dst (including end marker)
  169. * @src: runlist to be inserted into @dst
  170. * @ssize: number of elements in @src (excluding end marker)
  171. * @loc: append the new runlist @src after this element in @dst
  172. *
  173. * Append the runlist @src after element @loc in @dst. Merge the right end of
  174. * the new runlist, if necessary. Adjust the size of the hole before the
  175. * appended runlist.
  176. *
  177. * It is up to the caller to serialize access to the runlists @dst and @src.
  178. *
  179. * On success, return a pointer to the new, combined, runlist. Note, both
  180. * runlists @dst and @src are deallocated before returning so you cannot use
  181. * the pointers for anything any more. (Strictly speaking the returned runlist
  182. * may be the same as @dst but this is irrelevant.)
  183. *
  184. * On error, return -errno. Both runlists are left unmodified. The following
  185. * error codes are defined:
  186. * -ENOMEM - Not enough memory to allocate runlist array.
  187. * -EINVAL - Invalid parameters were passed in.
  188. */
  189. static inline runlist_element *ntfs_rl_append(runlist_element *dst,
  190. int dsize, runlist_element *src, int ssize, int loc)
  191. {
  192. bool right = false; /* Right end of @src needs merging. */
  193. int marker; /* End of the inserted runs. */
  194. BUG_ON(!dst);
  195. BUG_ON(!src);
  196. /* First, check if the right hand end needs merging. */
  197. if ((loc + 1) < dsize)
  198. right = ntfs_are_rl_mergeable(src + ssize - 1, dst + loc + 1);
  199. /* Space required: @dst size + @src size, less one if we merged. */
  200. dst = ntfs_rl_realloc(dst, dsize, dsize + ssize - right);
  201. if (IS_ERR(dst))
  202. return dst;
  203. /*
  204. * We are guaranteed to succeed from here so can start modifying the
  205. * original runlists.
  206. */
  207. /* First, merge the right hand end, if necessary. */
  208. if (right)
  209. __ntfs_rl_merge(src + ssize - 1, dst + loc + 1);
  210. /* First run after the @src runs that have been inserted. */
  211. marker = loc + ssize + 1;
  212. /* Move the tail of @dst out of the way, then copy in @src. */
  213. ntfs_rl_mm(dst, marker, loc + 1 + right, dsize - (loc + 1 + right));
  214. ntfs_rl_mc(dst, loc + 1, src, 0, ssize);
  215. /* Adjust the size of the preceding hole. */
  216. dst[loc].length = dst[loc + 1].vcn - dst[loc].vcn;
  217. /* We may have changed the length of the file, so fix the end marker */
  218. if (dst[marker].lcn == LCN_ENOENT)
  219. dst[marker].vcn = dst[marker - 1].vcn + dst[marker - 1].length;
  220. return dst;
  221. }
  222. /**
  223. * ntfs_rl_insert - insert a runlist into another
  224. * @dst: original runlist to be worked on
  225. * @dsize: number of elements in @dst (including end marker)
  226. * @src: new runlist to be inserted
  227. * @ssize: number of elements in @src (excluding end marker)
  228. * @loc: insert the new runlist @src before this element in @dst
  229. *
  230. * Insert the runlist @src before element @loc in the runlist @dst. Merge the
  231. * left end of the new runlist, if necessary. Adjust the size of the hole
  232. * after the inserted runlist.
  233. *
  234. * It is up to the caller to serialize access to the runlists @dst and @src.
  235. *
  236. * On success, return a pointer to the new, combined, runlist. Note, both
  237. * runlists @dst and @src are deallocated before returning so you cannot use
  238. * the pointers for anything any more. (Strictly speaking the returned runlist
  239. * may be the same as @dst but this is irrelevant.)
  240. *
  241. * On error, return -errno. Both runlists are left unmodified. The following
  242. * error codes are defined:
  243. * -ENOMEM - Not enough memory to allocate runlist array.
  244. * -EINVAL - Invalid parameters were passed in.
  245. */
  246. static inline runlist_element *ntfs_rl_insert(runlist_element *dst,
  247. int dsize, runlist_element *src, int ssize, int loc)
  248. {
  249. bool left = false; /* Left end of @src needs merging. */
  250. bool disc = false; /* Discontinuity between @dst and @src. */
  251. int marker; /* End of the inserted runs. */
  252. BUG_ON(!dst);
  253. BUG_ON(!src);
  254. /*
  255. * disc => Discontinuity between the end of @dst and the start of @src.
  256. * This means we might need to insert a "not mapped" run.
  257. */
  258. if (loc == 0)
  259. disc = (src[0].vcn > 0);
  260. else {
  261. s64 merged_length;
  262. left = ntfs_are_rl_mergeable(dst + loc - 1, src);
  263. merged_length = dst[loc - 1].length;
  264. if (left)
  265. merged_length += src->length;
  266. disc = (src[0].vcn > dst[loc - 1].vcn + merged_length);
  267. }
  268. /*
  269. * Space required: @dst size + @src size, less one if we merged, plus
  270. * one if there was a discontinuity.
  271. */
  272. dst = ntfs_rl_realloc(dst, dsize, dsize + ssize - left + disc);
  273. if (IS_ERR(dst))
  274. return dst;
  275. /*
  276. * We are guaranteed to succeed from here so can start modifying the
  277. * original runlist.
  278. */
  279. if (left)
  280. __ntfs_rl_merge(dst + loc - 1, src);
  281. /*
  282. * First run after the @src runs that have been inserted.
  283. * Nominally, @marker equals @loc + @ssize, i.e. location + number of
  284. * runs in @src. However, if @left, then the first run in @src has
  285. * been merged with one in @dst. And if @disc, then @dst and @src do
  286. * not meet and we need an extra run to fill the gap.
  287. */
  288. marker = loc + ssize - left + disc;
  289. /* Move the tail of @dst out of the way, then copy in @src. */
  290. ntfs_rl_mm(dst, marker, loc, dsize - loc);
  291. ntfs_rl_mc(dst, loc + disc, src, left, ssize - left);
  292. /* Adjust the VCN of the first run after the insertion... */
  293. dst[marker].vcn = dst[marker - 1].vcn + dst[marker - 1].length;
  294. /* ... and the length. */
  295. if (dst[marker].lcn == LCN_HOLE || dst[marker].lcn == LCN_RL_NOT_MAPPED)
  296. dst[marker].length = dst[marker + 1].vcn - dst[marker].vcn;
  297. /* Writing beyond the end of the file and there is a discontinuity. */
  298. if (disc) {
  299. if (loc > 0) {
  300. dst[loc].vcn = dst[loc - 1].vcn + dst[loc - 1].length;
  301. dst[loc].length = dst[loc + 1].vcn - dst[loc].vcn;
  302. } else {
  303. dst[loc].vcn = 0;
  304. dst[loc].length = dst[loc + 1].vcn;
  305. }
  306. dst[loc].lcn = LCN_RL_NOT_MAPPED;
  307. }
  308. return dst;
  309. }
  310. /**
  311. * ntfs_rl_replace - overwrite a runlist element with another runlist
  312. * @dst: original runlist to be worked on
  313. * @dsize: number of elements in @dst (including end marker)
  314. * @src: new runlist to be inserted
  315. * @ssize: number of elements in @src (excluding end marker)
  316. * @loc: index in runlist @dst to overwrite with @src
  317. *
  318. * Replace the runlist element @dst at @loc with @src. Merge the left and
  319. * right ends of the inserted runlist, if necessary.
  320. *
  321. * It is up to the caller to serialize access to the runlists @dst and @src.
  322. *
  323. * On success, return a pointer to the new, combined, runlist. Note, both
  324. * runlists @dst and @src are deallocated before returning so you cannot use
  325. * the pointers for anything any more. (Strictly speaking the returned runlist
  326. * may be the same as @dst but this is irrelevant.)
  327. *
  328. * On error, return -errno. Both runlists are left unmodified. The following
  329. * error codes are defined:
  330. * -ENOMEM - Not enough memory to allocate runlist array.
  331. * -EINVAL - Invalid parameters were passed in.
  332. */
  333. static inline runlist_element *ntfs_rl_replace(runlist_element *dst,
  334. int dsize, runlist_element *src, int ssize, int loc)
  335. {
  336. signed delta;
  337. bool left = false; /* Left end of @src needs merging. */
  338. bool right = false; /* Right end of @src needs merging. */
  339. int tail; /* Start of tail of @dst. */
  340. int marker; /* End of the inserted runs. */
  341. BUG_ON(!dst);
  342. BUG_ON(!src);
  343. /* First, see if the left and right ends need merging. */
  344. if ((loc + 1) < dsize)
  345. right = ntfs_are_rl_mergeable(src + ssize - 1, dst + loc + 1);
  346. if (loc > 0)
  347. left = ntfs_are_rl_mergeable(dst + loc - 1, src);
  348. /*
  349. * Allocate some space. We will need less if the left, right, or both
  350. * ends get merged. The -1 accounts for the run being replaced.
  351. */
  352. delta = ssize - 1 - left - right;
  353. if (delta > 0) {
  354. dst = ntfs_rl_realloc(dst, dsize, dsize + delta);
  355. if (IS_ERR(dst))
  356. return dst;
  357. }
  358. /*
  359. * We are guaranteed to succeed from here so can start modifying the
  360. * original runlists.
  361. */
  362. /* First, merge the left and right ends, if necessary. */
  363. if (right)
  364. __ntfs_rl_merge(src + ssize - 1, dst + loc + 1);
  365. if (left)
  366. __ntfs_rl_merge(dst + loc - 1, src);
  367. /*
  368. * Offset of the tail of @dst. This needs to be moved out of the way
  369. * to make space for the runs to be copied from @src, i.e. the first
  370. * run of the tail of @dst.
  371. * Nominally, @tail equals @loc + 1, i.e. location, skipping the
  372. * replaced run. However, if @right, then one of @dst's runs is
  373. * already merged into @src.
  374. */
  375. tail = loc + right + 1;
  376. /*
  377. * First run after the @src runs that have been inserted, i.e. where
  378. * the tail of @dst needs to be moved to.
  379. * Nominally, @marker equals @loc + @ssize, i.e. location + number of
  380. * runs in @src. However, if @left, then the first run in @src has
  381. * been merged with one in @dst.
  382. */
  383. marker = loc + ssize - left;
  384. /* Move the tail of @dst out of the way, then copy in @src. */
  385. ntfs_rl_mm(dst, marker, tail, dsize - tail);
  386. ntfs_rl_mc(dst, loc, src, left, ssize - left);
  387. /* We may have changed the length of the file, so fix the end marker. */
  388. if (dsize - tail > 0 && dst[marker].lcn == LCN_ENOENT)
  389. dst[marker].vcn = dst[marker - 1].vcn + dst[marker - 1].length;
  390. return dst;
  391. }
  392. /**
  393. * ntfs_rl_split - insert a runlist into the centre of a hole
  394. * @dst: original runlist to be worked on
  395. * @dsize: number of elements in @dst (including end marker)
  396. * @src: new runlist to be inserted
  397. * @ssize: number of elements in @src (excluding end marker)
  398. * @loc: index in runlist @dst at which to split and insert @src
  399. *
  400. * Split the runlist @dst at @loc into two and insert @new in between the two
  401. * fragments. No merging of runlists is necessary. Adjust the size of the
  402. * holes either side.
  403. *
  404. * It is up to the caller to serialize access to the runlists @dst and @src.
  405. *
  406. * On success, return a pointer to the new, combined, runlist. Note, both
  407. * runlists @dst and @src are deallocated before returning so you cannot use
  408. * the pointers for anything any more. (Strictly speaking the returned runlist
  409. * may be the same as @dst but this is irrelevant.)
  410. *
  411. * On error, return -errno. Both runlists are left unmodified. The following
  412. * error codes are defined:
  413. * -ENOMEM - Not enough memory to allocate runlist array.
  414. * -EINVAL - Invalid parameters were passed in.
  415. */
  416. static inline runlist_element *ntfs_rl_split(runlist_element *dst, int dsize,
  417. runlist_element *src, int ssize, int loc)
  418. {
  419. BUG_ON(!dst);
  420. BUG_ON(!src);
  421. /* Space required: @dst size + @src size + one new hole. */
  422. dst = ntfs_rl_realloc(dst, dsize, dsize + ssize + 1);
  423. if (IS_ERR(dst))
  424. return dst;
  425. /*
  426. * We are guaranteed to succeed from here so can start modifying the
  427. * original runlists.
  428. */
  429. /* Move the tail of @dst out of the way, then copy in @src. */
  430. ntfs_rl_mm(dst, loc + 1 + ssize, loc, dsize - loc);
  431. ntfs_rl_mc(dst, loc + 1, src, 0, ssize);
  432. /* Adjust the size of the holes either size of @src. */
  433. dst[loc].length = dst[loc+1].vcn - dst[loc].vcn;
  434. dst[loc+ssize+1].vcn = dst[loc+ssize].vcn + dst[loc+ssize].length;
  435. dst[loc+ssize+1].length = dst[loc+ssize+2].vcn - dst[loc+ssize+1].vcn;
  436. return dst;
  437. }
  438. /**
  439. * ntfs_runlists_merge - merge two runlists into one
  440. * @drl: original runlist to be worked on
  441. * @srl: new runlist to be merged into @drl
  442. *
  443. * First we sanity check the two runlists @srl and @drl to make sure that they
  444. * are sensible and can be merged. The runlist @srl must be either after the
  445. * runlist @drl or completely within a hole (or unmapped region) in @drl.
  446. *
  447. * It is up to the caller to serialize access to the runlists @drl and @srl.
  448. *
  449. * Merging of runlists is necessary in two cases:
  450. * 1. When attribute lists are used and a further extent is being mapped.
  451. * 2. When new clusters are allocated to fill a hole or extend a file.
  452. *
  453. * There are four possible ways @srl can be merged. It can:
  454. * - be inserted at the beginning of a hole,
  455. * - split the hole in two and be inserted between the two fragments,
  456. * - be appended at the end of a hole, or it can
  457. * - replace the whole hole.
  458. * It can also be appended to the end of the runlist, which is just a variant
  459. * of the insert case.
  460. *
  461. * On success, return a pointer to the new, combined, runlist. Note, both
  462. * runlists @drl and @srl are deallocated before returning so you cannot use
  463. * the pointers for anything any more. (Strictly speaking the returned runlist
  464. * may be the same as @dst but this is irrelevant.)
  465. *
  466. * On error, return -errno. Both runlists are left unmodified. The following
  467. * error codes are defined:
  468. * -ENOMEM - Not enough memory to allocate runlist array.
  469. * -EINVAL - Invalid parameters were passed in.
  470. * -ERANGE - The runlists overlap and cannot be merged.
  471. */
  472. runlist_element *ntfs_runlists_merge(runlist_element *drl,
  473. runlist_element *srl)
  474. {
  475. int di, si; /* Current index into @[ds]rl. */
  476. int sstart; /* First index with lcn > LCN_RL_NOT_MAPPED. */
  477. int dins; /* Index into @drl at which to insert @srl. */
  478. int dend, send; /* Last index into @[ds]rl. */
  479. int dfinal, sfinal; /* The last index into @[ds]rl with
  480. lcn >= LCN_HOLE. */
  481. int marker = 0;
  482. VCN marker_vcn = 0;
  483. #ifdef DEBUG
  484. ntfs_debug("dst:");
  485. ntfs_debug_dump_runlist(drl);
  486. ntfs_debug("src:");
  487. ntfs_debug_dump_runlist(srl);
  488. #endif
  489. /* Check for silly calling... */
  490. if (unlikely(!srl))
  491. return drl;
  492. if (IS_ERR(srl) || IS_ERR(drl))
  493. return ERR_PTR(-EINVAL);
  494. /* Check for the case where the first mapping is being done now. */
  495. if (unlikely(!drl)) {
  496. drl = srl;
  497. /* Complete the source runlist if necessary. */
  498. if (unlikely(drl[0].vcn)) {
  499. /* Scan to the end of the source runlist. */
  500. for (dend = 0; likely(drl[dend].length); dend++)
  501. ;
  502. dend++;
  503. drl = ntfs_rl_realloc(drl, dend, dend + 1);
  504. if (IS_ERR(drl))
  505. return drl;
  506. /* Insert start element at the front of the runlist. */
  507. ntfs_rl_mm(drl, 1, 0, dend);
  508. drl[0].vcn = 0;
  509. drl[0].lcn = LCN_RL_NOT_MAPPED;
  510. drl[0].length = drl[1].vcn;
  511. }
  512. goto finished;
  513. }
  514. si = di = 0;
  515. /* Skip any unmapped start element(s) in the source runlist. */
  516. while (srl[si].length && srl[si].lcn < LCN_HOLE)
  517. si++;
  518. /* Can't have an entirely unmapped source runlist. */
  519. BUG_ON(!srl[si].length);
  520. /* Record the starting points. */
  521. sstart = si;
  522. /*
  523. * Skip forward in @drl until we reach the position where @srl needs to
  524. * be inserted. If we reach the end of @drl, @srl just needs to be
  525. * appended to @drl.
  526. */
  527. for (; drl[di].length; di++) {
  528. if (drl[di].vcn + drl[di].length > srl[sstart].vcn)
  529. break;
  530. }
  531. dins = di;
  532. /* Sanity check for illegal overlaps. */
  533. if ((drl[di].vcn == srl[si].vcn) && (drl[di].lcn >= 0) &&
  534. (srl[si].lcn >= 0)) {
  535. ntfs_error(NULL, "Run lists overlap. Cannot merge!");
  536. return ERR_PTR(-ERANGE);
  537. }
  538. /* Scan to the end of both runlists in order to know their sizes. */
  539. for (send = si; srl[send].length; send++)
  540. ;
  541. for (dend = di; drl[dend].length; dend++)
  542. ;
  543. if (srl[send].lcn == LCN_ENOENT)
  544. marker_vcn = srl[marker = send].vcn;
  545. /* Scan to the last element with lcn >= LCN_HOLE. */
  546. for (sfinal = send; sfinal >= 0 && srl[sfinal].lcn < LCN_HOLE; sfinal--)
  547. ;
  548. for (dfinal = dend; dfinal >= 0 && drl[dfinal].lcn < LCN_HOLE; dfinal--)
  549. ;
  550. {
  551. bool start;
  552. bool finish;
  553. int ds = dend + 1; /* Number of elements in drl & srl */
  554. int ss = sfinal - sstart + 1;
  555. start = ((drl[dins].lcn < LCN_RL_NOT_MAPPED) || /* End of file */
  556. (drl[dins].vcn == srl[sstart].vcn)); /* Start of hole */
  557. finish = ((drl[dins].lcn >= LCN_RL_NOT_MAPPED) && /* End of file */
  558. ((drl[dins].vcn + drl[dins].length) <= /* End of hole */
  559. (srl[send - 1].vcn + srl[send - 1].length)));
  560. /* Or we will lose an end marker. */
  561. if (finish && !drl[dins].length)
  562. ss++;
  563. if (marker && (drl[dins].vcn + drl[dins].length > srl[send - 1].vcn))
  564. finish = false;
  565. #if 0
  566. ntfs_debug("dfinal = %i, dend = %i", dfinal, dend);
  567. ntfs_debug("sstart = %i, sfinal = %i, send = %i", sstart, sfinal, send);
  568. ntfs_debug("start = %i, finish = %i", start, finish);
  569. ntfs_debug("ds = %i, ss = %i, dins = %i", ds, ss, dins);
  570. #endif
  571. if (start) {
  572. if (finish)
  573. drl = ntfs_rl_replace(drl, ds, srl + sstart, ss, dins);
  574. else
  575. drl = ntfs_rl_insert(drl, ds, srl + sstart, ss, dins);
  576. } else {
  577. if (finish)
  578. drl = ntfs_rl_append(drl, ds, srl + sstart, ss, dins);
  579. else
  580. drl = ntfs_rl_split(drl, ds, srl + sstart, ss, dins);
  581. }
  582. if (IS_ERR(drl)) {
  583. ntfs_error(NULL, "Merge failed.");
  584. return drl;
  585. }
  586. ntfs_free(srl);
  587. if (marker) {
  588. ntfs_debug("Triggering marker code.");
  589. for (ds = dend; drl[ds].length; ds++)
  590. ;
  591. /* We only need to care if @srl ended after @drl. */
  592. if (drl[ds].vcn <= marker_vcn) {
  593. int slots = 0;
  594. if (drl[ds].vcn == marker_vcn) {
  595. ntfs_debug("Old marker = 0x%llx, replacing "
  596. "with LCN_ENOENT.",
  597. (unsigned long long)
  598. drl[ds].lcn);
  599. drl[ds].lcn = LCN_ENOENT;
  600. goto finished;
  601. }
  602. /*
  603. * We need to create an unmapped runlist element in
  604. * @drl or extend an existing one before adding the
  605. * ENOENT terminator.
  606. */
  607. if (drl[ds].lcn == LCN_ENOENT) {
  608. ds--;
  609. slots = 1;
  610. }
  611. if (drl[ds].lcn != LCN_RL_NOT_MAPPED) {
  612. /* Add an unmapped runlist element. */
  613. if (!slots) {
  614. drl = ntfs_rl_realloc_nofail(drl, ds,
  615. ds + 2);
  616. slots = 2;
  617. }
  618. ds++;
  619. /* Need to set vcn if it isn't set already. */
  620. if (slots != 1)
  621. drl[ds].vcn = drl[ds - 1].vcn +
  622. drl[ds - 1].length;
  623. drl[ds].lcn = LCN_RL_NOT_MAPPED;
  624. /* We now used up a slot. */
  625. slots--;
  626. }
  627. drl[ds].length = marker_vcn - drl[ds].vcn;
  628. /* Finally add the ENOENT terminator. */
  629. ds++;
  630. if (!slots)
  631. drl = ntfs_rl_realloc_nofail(drl, ds, ds + 1);
  632. drl[ds].vcn = marker_vcn;
  633. drl[ds].lcn = LCN_ENOENT;
  634. drl[ds].length = (s64)0;
  635. }
  636. }
  637. }
  638. finished:
  639. /* The merge was completed successfully. */
  640. ntfs_debug("Merged runlist:");
  641. ntfs_debug_dump_runlist(drl);
  642. return drl;
  643. }
  644. /**
  645. * ntfs_mapping_pairs_decompress - convert mapping pairs array to runlist
  646. * @vol: ntfs volume on which the attribute resides
  647. * @attr: attribute record whose mapping pairs array to decompress
  648. * @old_rl: optional runlist in which to insert @attr's runlist
  649. *
  650. * It is up to the caller to serialize access to the runlist @old_rl.
  651. *
  652. * Decompress the attribute @attr's mapping pairs array into a runlist. On
  653. * success, return the decompressed runlist.
  654. *
  655. * If @old_rl is not NULL, decompressed runlist is inserted into the
  656. * appropriate place in @old_rl and the resultant, combined runlist is
  657. * returned. The original @old_rl is deallocated.
  658. *
  659. * On error, return -errno. @old_rl is left unmodified in that case.
  660. *
  661. * The following error codes are defined:
  662. * -ENOMEM - Not enough memory to allocate runlist array.
  663. * -EIO - Corrupt runlist.
  664. * -EINVAL - Invalid parameters were passed in.
  665. * -ERANGE - The two runlists overlap.
  666. *
  667. * FIXME: For now we take the conceptionally simplest approach of creating the
  668. * new runlist disregarding the already existing one and then splicing the
  669. * two into one, if that is possible (we check for overlap and discard the new
  670. * runlist if overlap present before returning ERR_PTR(-ERANGE)).
  671. */
  672. runlist_element *ntfs_mapping_pairs_decompress(const ntfs_volume *vol,
  673. const ATTR_RECORD *attr, runlist_element *old_rl)
  674. {
  675. VCN vcn; /* Current vcn. */
  676. LCN lcn; /* Current lcn. */
  677. s64 deltaxcn; /* Change in [vl]cn. */
  678. runlist_element *rl; /* The output runlist. */
  679. u8 *buf; /* Current position in mapping pairs array. */
  680. u8 *attr_end; /* End of attribute. */
  681. int rlsize; /* Size of runlist buffer. */
  682. u16 rlpos; /* Current runlist position in units of
  683. runlist_elements. */
  684. u8 b; /* Current byte offset in buf. */
  685. #ifdef DEBUG
  686. /* Make sure attr exists and is non-resident. */
  687. if (!attr || !attr->non_resident || sle64_to_cpu(
  688. attr->data.non_resident.lowest_vcn) < (VCN)0) {
  689. ntfs_error(vol->sb, "Invalid arguments.");
  690. return ERR_PTR(-EINVAL);
  691. }
  692. #endif
  693. /* Start at vcn = lowest_vcn and lcn 0. */
  694. vcn = sle64_to_cpu(attr->data.non_resident.lowest_vcn);
  695. lcn = 0;
  696. /* Get start of the mapping pairs array. */
  697. buf = (u8*)attr + le16_to_cpu(
  698. attr->data.non_resident.mapping_pairs_offset);
  699. attr_end = (u8*)attr + le32_to_cpu(attr->length);
  700. if (unlikely(buf < (u8*)attr || buf > attr_end)) {
  701. ntfs_error(vol->sb, "Corrupt attribute.");
  702. return ERR_PTR(-EIO);
  703. }
  704. /* If the mapping pairs array is valid but empty, nothing to do. */
  705. if (!vcn && !*buf)
  706. return old_rl;
  707. /* Current position in runlist array. */
  708. rlpos = 0;
  709. /* Allocate first page and set current runlist size to one page. */
  710. rl = ntfs_malloc_nofs(rlsize = PAGE_SIZE);
  711. if (unlikely(!rl))
  712. return ERR_PTR(-ENOMEM);
  713. /* Insert unmapped starting element if necessary. */
  714. if (vcn) {
  715. rl->vcn = 0;
  716. rl->lcn = LCN_RL_NOT_MAPPED;
  717. rl->length = vcn;
  718. rlpos++;
  719. }
  720. while (buf < attr_end && *buf) {
  721. /*
  722. * Allocate more memory if needed, including space for the
  723. * not-mapped and terminator elements. ntfs_malloc_nofs()
  724. * operates on whole pages only.
  725. */
  726. if (((rlpos + 3) * sizeof(*old_rl)) > rlsize) {
  727. runlist_element *rl2;
  728. rl2 = ntfs_malloc_nofs(rlsize + (int)PAGE_SIZE);
  729. if (unlikely(!rl2)) {
  730. ntfs_free(rl);
  731. return ERR_PTR(-ENOMEM);
  732. }
  733. memcpy(rl2, rl, rlsize);
  734. ntfs_free(rl);
  735. rl = rl2;
  736. rlsize += PAGE_SIZE;
  737. }
  738. /* Enter the current vcn into the current runlist element. */
  739. rl[rlpos].vcn = vcn;
  740. /*
  741. * Get the change in vcn, i.e. the run length in clusters.
  742. * Doing it this way ensures that we signextend negative values.
  743. * A negative run length doesn't make any sense, but hey, I
  744. * didn't make up the NTFS specs and Windows NT4 treats the run
  745. * length as a signed value so that's how it is...
  746. */
  747. b = *buf & 0xf;
  748. if (b) {
  749. if (unlikely(buf + b > attr_end))
  750. goto io_error;
  751. for (deltaxcn = (s8)buf[b--]; b; b--)
  752. deltaxcn = (deltaxcn << 8) + buf[b];
  753. } else { /* The length entry is compulsory. */
  754. ntfs_error(vol->sb, "Missing length entry in mapping "
  755. "pairs array.");
  756. deltaxcn = (s64)-1;
  757. }
  758. /*
  759. * Assume a negative length to indicate data corruption and
  760. * hence clean-up and return NULL.
  761. */
  762. if (unlikely(deltaxcn < 0)) {
  763. ntfs_error(vol->sb, "Invalid length in mapping pairs "
  764. "array.");
  765. goto err_out;
  766. }
  767. /*
  768. * Enter the current run length into the current runlist
  769. * element.
  770. */
  771. rl[rlpos].length = deltaxcn;
  772. /* Increment the current vcn by the current run length. */
  773. vcn += deltaxcn;
  774. /*
  775. * There might be no lcn change at all, as is the case for
  776. * sparse clusters on NTFS 3.0+, in which case we set the lcn
  777. * to LCN_HOLE.
  778. */
  779. if (!(*buf & 0xf0))
  780. rl[rlpos].lcn = LCN_HOLE;
  781. else {
  782. /* Get the lcn change which really can be negative. */
  783. u8 b2 = *buf & 0xf;
  784. b = b2 + ((*buf >> 4) & 0xf);
  785. if (buf + b > attr_end)
  786. goto io_error;
  787. for (deltaxcn = (s8)buf[b--]; b > b2; b--)
  788. deltaxcn = (deltaxcn << 8) + buf[b];
  789. /* Change the current lcn to its new value. */
  790. lcn += deltaxcn;
  791. #ifdef DEBUG
  792. /*
  793. * On NTFS 1.2-, apparently can have lcn == -1 to
  794. * indicate a hole. But we haven't verified ourselves
  795. * whether it is really the lcn or the deltaxcn that is
  796. * -1. So if either is found give us a message so we
  797. * can investigate it further!
  798. */
  799. if (vol->major_ver < 3) {
  800. if (unlikely(deltaxcn == (LCN)-1))
  801. ntfs_error(vol->sb, "lcn delta == -1");
  802. if (unlikely(lcn == (LCN)-1))
  803. ntfs_error(vol->sb, "lcn == -1");
  804. }
  805. #endif
  806. /* Check lcn is not below -1. */
  807. if (unlikely(lcn < (LCN)-1)) {
  808. ntfs_error(vol->sb, "Invalid LCN < -1 in "
  809. "mapping pairs array.");
  810. goto err_out;
  811. }
  812. /* Enter the current lcn into the runlist element. */
  813. rl[rlpos].lcn = lcn;
  814. }
  815. /* Get to the next runlist element. */
  816. rlpos++;
  817. /* Increment the buffer position to the next mapping pair. */
  818. buf += (*buf & 0xf) + ((*buf >> 4) & 0xf) + 1;
  819. }
  820. if (unlikely(buf >= attr_end))
  821. goto io_error;
  822. /*
  823. * If there is a highest_vcn specified, it must be equal to the final
  824. * vcn in the runlist - 1, or something has gone badly wrong.
  825. */
  826. deltaxcn = sle64_to_cpu(attr->data.non_resident.highest_vcn);
  827. if (unlikely(deltaxcn && vcn - 1 != deltaxcn)) {
  828. mpa_err:
  829. ntfs_error(vol->sb, "Corrupt mapping pairs array in "
  830. "non-resident attribute.");
  831. goto err_out;
  832. }
  833. /* Setup not mapped runlist element if this is the base extent. */
  834. if (!attr->data.non_resident.lowest_vcn) {
  835. VCN max_cluster;
  836. max_cluster = ((sle64_to_cpu(
  837. attr->data.non_resident.allocated_size) +
  838. vol->cluster_size - 1) >>
  839. vol->cluster_size_bits) - 1;
  840. /*
  841. * A highest_vcn of zero means this is a single extent
  842. * attribute so simply terminate the runlist with LCN_ENOENT).
  843. */
  844. if (deltaxcn) {
  845. /*
  846. * If there is a difference between the highest_vcn and
  847. * the highest cluster, the runlist is either corrupt
  848. * or, more likely, there are more extents following
  849. * this one.
  850. */
  851. if (deltaxcn < max_cluster) {
  852. ntfs_debug("More extents to follow; deltaxcn "
  853. "= 0x%llx, max_cluster = "
  854. "0x%llx",
  855. (unsigned long long)deltaxcn,
  856. (unsigned long long)
  857. max_cluster);
  858. rl[rlpos].vcn = vcn;
  859. vcn += rl[rlpos].length = max_cluster -
  860. deltaxcn;
  861. rl[rlpos].lcn = LCN_RL_NOT_MAPPED;
  862. rlpos++;
  863. } else if (unlikely(deltaxcn > max_cluster)) {
  864. ntfs_error(vol->sb, "Corrupt attribute. "
  865. "deltaxcn = 0x%llx, "
  866. "max_cluster = 0x%llx",
  867. (unsigned long long)deltaxcn,
  868. (unsigned long long)
  869. max_cluster);
  870. goto mpa_err;
  871. }
  872. }
  873. rl[rlpos].lcn = LCN_ENOENT;
  874. } else /* Not the base extent. There may be more extents to follow. */
  875. rl[rlpos].lcn = LCN_RL_NOT_MAPPED;
  876. /* Setup terminating runlist element. */
  877. rl[rlpos].vcn = vcn;
  878. rl[rlpos].length = (s64)0;
  879. /* If no existing runlist was specified, we are done. */
  880. if (!old_rl) {
  881. ntfs_debug("Mapping pairs array successfully decompressed:");
  882. ntfs_debug_dump_runlist(rl);
  883. return rl;
  884. }
  885. /* Now combine the new and old runlists checking for overlaps. */
  886. old_rl = ntfs_runlists_merge(old_rl, rl);
  887. if (!IS_ERR(old_rl))
  888. return old_rl;
  889. ntfs_free(rl);
  890. ntfs_error(vol->sb, "Failed to merge runlists.");
  891. return old_rl;
  892. io_error:
  893. ntfs_error(vol->sb, "Corrupt attribute.");
  894. err_out:
  895. ntfs_free(rl);
  896. return ERR_PTR(-EIO);
  897. }
  898. /**
  899. * ntfs_rl_vcn_to_lcn - convert a vcn into a lcn given a runlist
  900. * @rl: runlist to use for conversion
  901. * @vcn: vcn to convert
  902. *
  903. * Convert the virtual cluster number @vcn of an attribute into a logical
  904. * cluster number (lcn) of a device using the runlist @rl to map vcns to their
  905. * corresponding lcns.
  906. *
  907. * It is up to the caller to serialize access to the runlist @rl.
  908. *
  909. * Since lcns must be >= 0, we use negative return codes with special meaning:
  910. *
  911. * Return code Meaning / Description
  912. * ==================================================
  913. * LCN_HOLE Hole / not allocated on disk.
  914. * LCN_RL_NOT_MAPPED This is part of the runlist which has not been
  915. * inserted into the runlist yet.
  916. * LCN_ENOENT There is no such vcn in the attribute.
  917. *
  918. * Locking: - The caller must have locked the runlist (for reading or writing).
  919. * - This function does not touch the lock, nor does it modify the
  920. * runlist.
  921. */
  922. LCN ntfs_rl_vcn_to_lcn(const runlist_element *rl, const VCN vcn)
  923. {
  924. int i;
  925. BUG_ON(vcn < 0);
  926. /*
  927. * If rl is NULL, assume that we have found an unmapped runlist. The
  928. * caller can then attempt to map it and fail appropriately if
  929. * necessary.
  930. */
  931. if (unlikely(!rl))
  932. return LCN_RL_NOT_MAPPED;
  933. /* Catch out of lower bounds vcn. */
  934. if (unlikely(vcn < rl[0].vcn))
  935. return LCN_ENOENT;
  936. for (i = 0; likely(rl[i].length); i++) {
  937. if (unlikely(vcn < rl[i+1].vcn)) {
  938. if (likely(rl[i].lcn >= (LCN)0))
  939. return rl[i].lcn + (vcn - rl[i].vcn);
  940. return rl[i].lcn;
  941. }
  942. }
  943. /*
  944. * The terminator element is setup to the correct value, i.e. one of
  945. * LCN_HOLE, LCN_RL_NOT_MAPPED, or LCN_ENOENT.
  946. */
  947. if (likely(rl[i].lcn < (LCN)0))
  948. return rl[i].lcn;
  949. /* Just in case... We could replace this with BUG() some day. */
  950. return LCN_ENOENT;
  951. }
  952. #ifdef NTFS_RW
  953. /**
  954. * ntfs_rl_find_vcn_nolock - find a vcn in a runlist
  955. * @rl: runlist to search
  956. * @vcn: vcn to find
  957. *
  958. * Find the virtual cluster number @vcn in the runlist @rl and return the
  959. * address of the runlist element containing the @vcn on success.
  960. *
  961. * Return NULL if @rl is NULL or @vcn is in an unmapped part/out of bounds of
  962. * the runlist.
  963. *
  964. * Locking: The runlist must be locked on entry.
  965. */
  966. runlist_element *ntfs_rl_find_vcn_nolock(runlist_element *rl, const VCN vcn)
  967. {
  968. BUG_ON(vcn < 0);
  969. if (unlikely(!rl || vcn < rl[0].vcn))
  970. return NULL;
  971. while (likely(rl->length)) {
  972. if (unlikely(vcn < rl[1].vcn)) {
  973. if (likely(rl->lcn >= LCN_HOLE))
  974. return rl;
  975. return NULL;
  976. }
  977. rl++;
  978. }
  979. if (likely(rl->lcn == LCN_ENOENT))
  980. return rl;
  981. return NULL;
  982. }
  983. /**
  984. * ntfs_get_nr_significant_bytes - get number of bytes needed to store a number
  985. * @n: number for which to get the number of bytes for
  986. *
  987. * Return the number of bytes required to store @n unambiguously as
  988. * a signed number.
  989. *
  990. * This is used in the context of the mapping pairs array to determine how
  991. * many bytes will be needed in the array to store a given logical cluster
  992. * number (lcn) or a specific run length.
  993. *
  994. * Return the number of bytes written. This function cannot fail.
  995. */
  996. static inline int ntfs_get_nr_significant_bytes(const s64 n)
  997. {
  998. s64 l = n;
  999. int i;
  1000. s8 j;
  1001. i = 0;
  1002. do {
  1003. l >>= 8;
  1004. i++;
  1005. } while (l != 0 && l != -1);
  1006. j = (n >> 8 * (i - 1)) & 0xff;
  1007. /* If the sign bit is wrong, we need an extra byte. */
  1008. if ((n < 0 && j >= 0) || (n > 0 && j < 0))
  1009. i++;
  1010. return i;
  1011. }
  1012. /**
  1013. * ntfs_get_size_for_mapping_pairs - get bytes needed for mapping pairs array
  1014. * @vol: ntfs volume (needed for the ntfs version)
  1015. * @rl: locked runlist to determine the size of the mapping pairs of
  1016. * @first_vcn: first vcn which to include in the mapping pairs array
  1017. * @last_vcn: last vcn which to include in the mapping pairs array
  1018. *
  1019. * Walk the locked runlist @rl and calculate the size in bytes of the mapping
  1020. * pairs array corresponding to the runlist @rl, starting at vcn @first_vcn and
  1021. * finishing with vcn @last_vcn.
  1022. *
  1023. * A @last_vcn of -1 means end of runlist and in that case the size of the
  1024. * mapping pairs array corresponding to the runlist starting at vcn @first_vcn
  1025. * and finishing at the end of the runlist is determined.
  1026. *
  1027. * This for example allows us to allocate a buffer of the right size when
  1028. * building the mapping pairs array.
  1029. *
  1030. * If @rl is NULL, just return 1 (for the single terminator byte).
  1031. *
  1032. * Return the calculated size in bytes on success. On error, return -errno.
  1033. * The following error codes are defined:
  1034. * -EINVAL - Run list contains unmapped elements. Make sure to only pass
  1035. * fully mapped runlists to this function.
  1036. * -EIO - The runlist is corrupt.
  1037. *
  1038. * Locking: @rl must be locked on entry (either for reading or writing), it
  1039. * remains locked throughout, and is left locked upon return.
  1040. */
  1041. int ntfs_get_size_for_mapping_pairs(const ntfs_volume *vol,
  1042. const runlist_element *rl, const VCN first_vcn,
  1043. const VCN last_vcn)
  1044. {
  1045. LCN prev_lcn;
  1046. int rls;
  1047. bool the_end = false;
  1048. BUG_ON(first_vcn < 0);
  1049. BUG_ON(last_vcn < -1);
  1050. BUG_ON(last_vcn >= 0 && first_vcn > last_vcn);
  1051. if (!rl) {
  1052. BUG_ON(first_vcn);
  1053. BUG_ON(last_vcn > 0);
  1054. return 1;
  1055. }
  1056. /* Skip to runlist element containing @first_vcn. */
  1057. while (rl->length && first_vcn >= rl[1].vcn)
  1058. rl++;
  1059. if (unlikely((!rl->length && first_vcn > rl->vcn) ||
  1060. first_vcn < rl->vcn))
  1061. return -EINVAL;
  1062. prev_lcn = 0;
  1063. /* Always need the termining zero byte. */
  1064. rls = 1;
  1065. /* Do the first partial run if present. */
  1066. if (first_vcn > rl->vcn) {
  1067. s64 delta, length = rl->length;
  1068. /* We know rl->length != 0 already. */
  1069. if (unlikely(length < 0 || rl->lcn < LCN_HOLE))
  1070. goto err_out;
  1071. /*
  1072. * If @stop_vcn is given and finishes inside this run, cap the
  1073. * run length.
  1074. */
  1075. if (unlikely(last_vcn >= 0 && rl[1].vcn > last_vcn)) {
  1076. s64 s1 = last_vcn + 1;
  1077. if (unlikely(rl[1].vcn > s1))
  1078. length = s1 - rl->vcn;
  1079. the_end = true;
  1080. }
  1081. delta = first_vcn - rl->vcn;
  1082. /* Header byte + length. */
  1083. rls += 1 + ntfs_get_nr_significant_bytes(length - delta);
  1084. /*
  1085. * If the logical cluster number (lcn) denotes a hole and we
  1086. * are on NTFS 3.0+, we don't store it at all, i.e. we need
  1087. * zero space. On earlier NTFS versions we just store the lcn.
  1088. * Note: this assumes that on NTFS 1.2-, holes are stored with
  1089. * an lcn of -1 and not a delta_lcn of -1 (unless both are -1).
  1090. */
  1091. if (likely(rl->lcn >= 0 || vol->major_ver < 3)) {
  1092. prev_lcn = rl->lcn;
  1093. if (likely(rl->lcn >= 0))
  1094. prev_lcn += delta;
  1095. /* Change in lcn. */
  1096. rls += ntfs_get_nr_significant_bytes(prev_lcn);
  1097. }
  1098. /* Go to next runlist element. */
  1099. rl++;
  1100. }
  1101. /* Do the full runs. */
  1102. for (; rl->length && !the_end; rl++) {
  1103. s64 length = rl->length;
  1104. if (unlikely(length < 0 || rl->lcn < LCN_HOLE))
  1105. goto err_out;
  1106. /*
  1107. * If @stop_vcn is given and finishes inside this run, cap the
  1108. * run length.
  1109. */
  1110. if (unlikely(last_vcn >= 0 && rl[1].vcn > last_vcn)) {
  1111. s64 s1 = last_vcn + 1;
  1112. if (unlikely(rl[1].vcn > s1))
  1113. length = s1 - rl->vcn;
  1114. the_end = true;
  1115. }
  1116. /* Header byte + length. */
  1117. rls += 1 + ntfs_get_nr_significant_bytes(length);
  1118. /*
  1119. * If the logical cluster number (lcn) denotes a hole and we
  1120. * are on NTFS 3.0+, we don't store it at all, i.e. we need
  1121. * zero space. On earlier NTFS versions we just store the lcn.
  1122. * Note: this assumes that on NTFS 1.2-, holes are stored with
  1123. * an lcn of -1 and not a delta_lcn of -1 (unless both are -1).
  1124. */
  1125. if (likely(rl->lcn >= 0 || vol->major_ver < 3)) {
  1126. /* Change in lcn. */
  1127. rls += ntfs_get_nr_significant_bytes(rl->lcn -
  1128. prev_lcn);
  1129. prev_lcn = rl->lcn;
  1130. }
  1131. }
  1132. return rls;
  1133. err_out:
  1134. if (rl->lcn == LCN_RL_NOT_MAPPED)
  1135. rls = -EINVAL;
  1136. else
  1137. rls = -EIO;
  1138. return rls;
  1139. }
  1140. /**
  1141. * ntfs_write_significant_bytes - write the significant bytes of a number
  1142. * @dst: destination buffer to write to
  1143. * @dst_max: pointer to last byte of destination buffer for bounds checking
  1144. * @n: number whose significant bytes to write
  1145. *
  1146. * Store in @dst, the minimum bytes of the number @n which are required to
  1147. * identify @n unambiguously as a signed number, taking care not to exceed
  1148. * @dest_max, the maximum position within @dst to which we are allowed to
  1149. * write.
  1150. *
  1151. * This is used when building the mapping pairs array of a runlist to compress
  1152. * a given logical cluster number (lcn) or a specific run length to the minimum
  1153. * size possible.
  1154. *
  1155. * Return the number of bytes written on success. On error, i.e. the
  1156. * destination buffer @dst is too small, return -ENOSPC.
  1157. */
  1158. static inline int ntfs_write_significant_bytes(s8 *dst, const s8 *dst_max,
  1159. const s64 n)
  1160. {
  1161. s64 l = n;
  1162. int i;
  1163. s8 j;
  1164. i = 0;
  1165. do {
  1166. if (unlikely(dst > dst_max))
  1167. goto err_out;
  1168. *dst++ = l & 0xffll;
  1169. l >>= 8;
  1170. i++;
  1171. } while (l != 0 && l != -1);
  1172. j = (n >> 8 * (i - 1)) & 0xff;
  1173. /* If the sign bit is wrong, we need an extra byte. */
  1174. if (n < 0 && j >= 0) {
  1175. if (unlikely(dst > dst_max))
  1176. goto err_out;
  1177. i++;
  1178. *dst = (s8)-1;
  1179. } else if (n > 0 && j < 0) {
  1180. if (unlikely(dst > dst_max))
  1181. goto err_out;
  1182. i++;
  1183. *dst = (s8)0;
  1184. }
  1185. return i;
  1186. err_out:
  1187. return -ENOSPC;
  1188. }
  1189. /**
  1190. * ntfs_mapping_pairs_build - build the mapping pairs array from a runlist
  1191. * @vol: ntfs volume (needed for the ntfs version)
  1192. * @dst: destination buffer to which to write the mapping pairs array
  1193. * @dst_len: size of destination buffer @dst in bytes
  1194. * @rl: locked runlist for which to build the mapping pairs array
  1195. * @first_vcn: first vcn which to include in the mapping pairs array
  1196. * @last_vcn: last vcn which to include in the mapping pairs array
  1197. * @stop_vcn: first vcn outside destination buffer on success or -ENOSPC
  1198. *
  1199. * Create the mapping pairs array from the locked runlist @rl, starting at vcn
  1200. * @first_vcn and finishing with vcn @last_vcn and save the array in @dst.
  1201. * @dst_len is the size of @dst in bytes and it should be at least equal to the
  1202. * value obtained by calling ntfs_get_size_for_mapping_pairs().
  1203. *
  1204. * A @last_vcn of -1 means end of runlist and in that case the mapping pairs
  1205. * array corresponding to the runlist starting at vcn @first_vcn and finishing
  1206. * at the end of the runlist is created.
  1207. *
  1208. * If @rl is NULL, just write a single terminator byte to @dst.
  1209. *
  1210. * On success or -ENOSPC error, if @stop_vcn is not NULL, *@stop_vcn is set to
  1211. * the first vcn outside the destination buffer. Note that on error, @dst has
  1212. * been filled with all the mapping pairs that will fit, thus it can be treated
  1213. * as partial success, in that a new attribute extent needs to be created or
  1214. * the next extent has to be used and the mapping pairs build has to be
  1215. * continued with @first_vcn set to *@stop_vcn.
  1216. *
  1217. * Return 0 on success and -errno on error. The following error codes are
  1218. * defined:
  1219. * -EINVAL - Run list contains unmapped elements. Make sure to only pass
  1220. * fully mapped runlists to this function.
  1221. * -EIO - The runlist is corrupt.
  1222. * -ENOSPC - The destination buffer is too small.
  1223. *
  1224. * Locking: @rl must be locked on entry (either for reading or writing), it
  1225. * remains locked throughout, and is left locked upon return.
  1226. */
  1227. int ntfs_mapping_pairs_build(const ntfs_volume *vol, s8 *dst,
  1228. const int dst_len, const runlist_element *rl,
  1229. const VCN first_vcn, const VCN last_vcn, VCN *const stop_vcn)
  1230. {
  1231. LCN prev_lcn;
  1232. s8 *dst_max, *dst_next;
  1233. int err = -ENOSPC;
  1234. bool the_end = false;
  1235. s8 len_len, lcn_len;
  1236. BUG_ON(first_vcn < 0);
  1237. BUG_ON(last_vcn < -1);
  1238. BUG_ON(last_vcn >= 0 && first_vcn > last_vcn);
  1239. BUG_ON(dst_len < 1);
  1240. if (!rl) {
  1241. BUG_ON(first_vcn);
  1242. BUG_ON(last_vcn > 0);
  1243. if (stop_vcn)
  1244. *stop_vcn = 0;
  1245. /* Terminator byte. */
  1246. *dst = 0;
  1247. return 0;
  1248. }
  1249. /* Skip to runlist element containing @first_vcn. */
  1250. while (rl->length && first_vcn >= rl[1].vcn)
  1251. rl++;
  1252. if (unlikely((!rl->length && first_vcn > rl->vcn) ||
  1253. first_vcn < rl->vcn))
  1254. return -EINVAL;
  1255. /*
  1256. * @dst_max is used for bounds checking in
  1257. * ntfs_write_significant_bytes().
  1258. */
  1259. dst_max = dst + dst_len - 1;
  1260. prev_lcn = 0;
  1261. /* Do the first partial run if present. */
  1262. if (first_vcn > rl->vcn) {
  1263. s64 delta, length = rl->length;
  1264. /* We know rl->length != 0 already. */
  1265. if (unlikely(length < 0 || rl->lcn < LCN_HOLE))
  1266. goto err_out;
  1267. /*
  1268. * If @stop_vcn is given and finishes inside this run, cap the
  1269. * run length.
  1270. */
  1271. if (unlikely(last_vcn >= 0 && rl[1].vcn > last_vcn)) {
  1272. s64 s1 = last_vcn + 1;
  1273. if (unlikely(rl[1].vcn > s1))
  1274. length = s1 - rl->vcn;
  1275. the_end = true;
  1276. }
  1277. delta = first_vcn - rl->vcn;
  1278. /* Write length. */
  1279. len_len = ntfs_write_significant_bytes(dst + 1, dst_max,
  1280. length - delta);
  1281. if (unlikely(len_len < 0))
  1282. goto size_err;
  1283. /*
  1284. * If the logical cluster number (lcn) denotes a hole and we
  1285. * are on NTFS 3.0+, we don't store it at all, i.e. we need
  1286. * zero space. On earlier NTFS versions we just write the lcn
  1287. * change. FIXME: Do we need to write the lcn change or just
  1288. * the lcn in that case? Not sure as I have never seen this
  1289. * case on NT4. - We assume that we just need to write the lcn
  1290. * change until someone tells us otherwise... (AIA)
  1291. */
  1292. if (likely(rl->lcn >= 0 || vol->major_ver < 3)) {
  1293. prev_lcn = rl->lcn;
  1294. if (likely(rl->lcn >= 0))
  1295. prev_lcn += delta;
  1296. /* Write change in lcn. */
  1297. lcn_len = ntfs_write_significant_bytes(dst + 1 +
  1298. len_len, dst_max, prev_lcn);
  1299. if (unlikely(lcn_len < 0))
  1300. goto size_err;
  1301. } else
  1302. lcn_len = 0;
  1303. dst_next = dst + len_len + lcn_len + 1;
  1304. if (unlikely(dst_next > dst_max))
  1305. goto size_err;
  1306. /* Update header byte. */
  1307. *dst = lcn_len << 4 | len_len;
  1308. /* Position at next mapping pairs array element. */
  1309. dst = dst_next;
  1310. /* Go to next runlist element. */
  1311. rl++;
  1312. }
  1313. /* Do the full runs. */
  1314. for (; rl->length && !the_end; rl++) {
  1315. s64 length = rl->length;
  1316. if (unlikely(length < 0 || rl->lcn < LCN_HOLE))
  1317. goto err_out;
  1318. /*
  1319. * If @stop_vcn is given and finishes inside this run, cap the
  1320. * run length.
  1321. */
  1322. if (unlikely(last_vcn >= 0 && rl[1].vcn > last_vcn)) {
  1323. s64 s1 = last_vcn + 1;
  1324. if (unlikely(rl[1].vcn > s1))
  1325. length = s1 - rl->vcn;
  1326. the_end = true;
  1327. }
  1328. /* Write length. */
  1329. len_len = ntfs_write_significant_bytes(dst + 1, dst_max,
  1330. length);
  1331. if (unlikely(len_len < 0))
  1332. goto size_err;
  1333. /*
  1334. * If the logical cluster number (lcn) denotes a hole and we
  1335. * are on NTFS 3.0+, we don't store it at all, i.e. we need
  1336. * zero space. On earlier NTFS versions we just write the lcn
  1337. * change. FIXME: Do we need to write the lcn change or just
  1338. * the lcn in that case? Not sure as I have never seen this
  1339. * case on NT4. - We assume that we just need to write the lcn
  1340. * change until someone tells us otherwise... (AIA)
  1341. */
  1342. if (likely(rl->lcn >= 0 || vol->major_ver < 3)) {
  1343. /* Write change in lcn. */
  1344. lcn_len = ntfs_write_significant_bytes(dst + 1 +
  1345. len_len, dst_max, rl->lcn - prev_lcn);
  1346. if (unlikely(lcn_len < 0))
  1347. goto size_err;
  1348. prev_lcn = rl->lcn;
  1349. } else
  1350. lcn_len = 0;
  1351. dst_next = dst + len_len + lcn_len + 1;
  1352. if (unlikely(dst_next > dst_max))
  1353. goto size_err;
  1354. /* Update header byte. */
  1355. *dst = lcn_len << 4 | len_len;
  1356. /* Position at next mapping pairs array element. */
  1357. dst = dst_next;
  1358. }
  1359. /* Success. */
  1360. err = 0;
  1361. size_err:
  1362. /* Set stop vcn. */
  1363. if (stop_vcn)
  1364. *stop_vcn = rl->vcn;
  1365. /* Add terminator byte. */
  1366. *dst = 0;
  1367. return err;
  1368. err_out:
  1369. if (rl->lcn == LCN_RL_NOT_MAPPED)
  1370. err = -EINVAL;
  1371. else
  1372. err = -EIO;
  1373. return err;
  1374. }
  1375. /**
  1376. * ntfs_rl_truncate_nolock - truncate a runlist starting at a specified vcn
  1377. * @vol: ntfs volume (needed for error output)
  1378. * @runlist: runlist to truncate
  1379. * @new_length: the new length of the runlist in VCNs
  1380. *
  1381. * Truncate the runlist described by @runlist as well as the memory buffer
  1382. * holding the runlist elements to a length of @new_length VCNs.
  1383. *
  1384. * If @new_length lies within the runlist, the runlist elements with VCNs of
  1385. * @new_length and above are discarded. As a special case if @new_length is
  1386. * zero, the runlist is discarded and set to NULL.
  1387. *
  1388. * If @new_length lies beyond the runlist, a sparse runlist element is added to
  1389. * the end of the runlist @runlist or if the last runlist element is a sparse
  1390. * one already, this is extended.
  1391. *
  1392. * Note, no checking is done for unmapped runlist elements. It is assumed that
  1393. * the caller has mapped any elements that need to be mapped already.
  1394. *
  1395. * Return 0 on success and -errno on error.
  1396. *
  1397. * Locking: The caller must hold @runlist->lock for writing.
  1398. */
  1399. int ntfs_rl_truncate_nolock(const ntfs_volume *vol, runlist *const runlist,
  1400. const s64 new_length)
  1401. {
  1402. runlist_element *rl;
  1403. int old_size;
  1404. ntfs_debug("Entering for new_length 0x%llx.", (long long)new_length);
  1405. BUG_ON(!runlist);
  1406. BUG_ON(new_length < 0);
  1407. rl = runlist->rl;
  1408. if (!new_length) {
  1409. ntfs_debug("Freeing runlist.");
  1410. runlist->rl = NULL;
  1411. if (rl)
  1412. ntfs_free(rl);
  1413. return 0;
  1414. }
  1415. if (unlikely(!rl)) {
  1416. /*
  1417. * Create a runlist consisting of a sparse runlist element of
  1418. * length @new_length followed by a terminator runlist element.
  1419. */
  1420. rl = ntfs_malloc_nofs(PAGE_SIZE);
  1421. if (unlikely(!rl)) {
  1422. ntfs_error(vol->sb, "Not enough memory to allocate "
  1423. "runlist element buffer.");
  1424. return -ENOMEM;
  1425. }
  1426. runlist->rl = rl;
  1427. rl[1].length = rl->vcn = 0;
  1428. rl->lcn = LCN_HOLE;
  1429. rl[1].vcn = rl->length = new_length;
  1430. rl[1].lcn = LCN_ENOENT;
  1431. return 0;
  1432. }
  1433. BUG_ON(new_length < rl->vcn);
  1434. /* Find @new_length in the runlist. */
  1435. while (likely(rl->length && new_length >= rl[1].vcn))
  1436. rl++;
  1437. /*
  1438. * If not at the end of the runlist we need to shrink it.
  1439. * If at the end of the runlist we need to expand it.
  1440. */
  1441. if (rl->length) {
  1442. runlist_element *trl;
  1443. bool is_end;
  1444. ntfs_debug("Shrinking runlist.");
  1445. /* Determine the runlist size. */
  1446. trl = rl + 1;
  1447. while (likely(trl->length))
  1448. trl++;
  1449. old_size = trl - runlist->rl + 1;
  1450. /* Truncate the run. */
  1451. rl->length = new_length - rl->vcn;
  1452. /*
  1453. * If a run was partially truncated, make the following runlist
  1454. * element a terminator.
  1455. */
  1456. is_end = false;
  1457. if (rl->length) {
  1458. rl++;
  1459. if (!rl->length)
  1460. is_end = true;
  1461. rl->vcn = new_length;
  1462. rl->length = 0;
  1463. }
  1464. rl->lcn = LCN_ENOENT;
  1465. /* Reallocate memory if necessary. */
  1466. if (!is_end) {
  1467. int new_size = rl - runlist->rl + 1;
  1468. rl = ntfs_rl_realloc(runlist->rl, old_size, new_size);
  1469. if (IS_ERR(rl))
  1470. ntfs_warning(vol->sb, "Failed to shrink "
  1471. "runlist buffer. This just "
  1472. "wastes a bit of memory "
  1473. "temporarily so we ignore it "
  1474. "and return success.");
  1475. else
  1476. runlist->rl = rl;
  1477. }
  1478. } else if (likely(/* !rl->length && */ new_length > rl->vcn)) {
  1479. ntfs_debug("Expanding runlist.");
  1480. /*
  1481. * If there is a previous runlist element and it is a sparse
  1482. * one, extend it. Otherwise need to add a new, sparse runlist
  1483. * element.
  1484. */
  1485. if ((rl > runlist->rl) && ((rl - 1)->lcn == LCN_HOLE))
  1486. (rl - 1)->length = new_length - (rl - 1)->vcn;
  1487. else {
  1488. /* Determine the runlist size. */
  1489. old_size = rl - runlist->rl + 1;
  1490. /* Reallocate memory if necessary. */
  1491. rl = ntfs_rl_realloc(runlist->rl, old_size,
  1492. old_size + 1);
  1493. if (IS_ERR(rl)) {
  1494. ntfs_error(vol->sb, "Failed to expand runlist "
  1495. "buffer, aborting.");
  1496. return PTR_ERR(rl);
  1497. }
  1498. runlist->rl = rl;
  1499. /*
  1500. * Set @rl to the same runlist element in the new
  1501. * runlist as before in the old runlist.
  1502. */
  1503. rl += old_size - 1;
  1504. /* Add a new, sparse runlist element. */
  1505. rl->lcn = LCN_HOLE;
  1506. rl->length = new_length - rl->vcn;
  1507. /* Add a new terminator runlist element. */
  1508. rl++;
  1509. rl->length = 0;
  1510. }
  1511. rl->vcn = new_length;
  1512. rl->lcn = LCN_ENOENT;
  1513. } else /* if (unlikely(!rl->length && new_length == rl->vcn)) */ {
  1514. /* Runlist already has same size as requested. */
  1515. rl->lcn = LCN_ENOENT;
  1516. }
  1517. ntfs_debug("Done.");
  1518. return 0;
  1519. }
  1520. /**
  1521. * ntfs_rl_punch_nolock - punch a hole into a runlist
  1522. * @vol: ntfs volume (needed for error output)
  1523. * @runlist: runlist to punch a hole into
  1524. * @start: starting VCN of the hole to be created
  1525. * @length: size of the hole to be created in units of clusters
  1526. *
  1527. * Punch a hole into the runlist @runlist starting at VCN @start and of size
  1528. * @length clusters.
  1529. *
  1530. * Return 0 on success and -errno on error, in which case @runlist has not been
  1531. * modified.
  1532. *
  1533. * If @start and/or @start + @length are outside the runlist return error code
  1534. * -ENOENT.
  1535. *
  1536. * If the runlist contains unmapped or error elements between @start and @start
  1537. * + @length return error code -EINVAL.
  1538. *
  1539. * Locking: The caller must hold @runlist->lock for writing.
  1540. */
  1541. int ntfs_rl_punch_nolock(const ntfs_volume *vol, runlist *const runlist,
  1542. const VCN start, const s64 length)
  1543. {
  1544. const VCN end = start + length;
  1545. s64 delta;
  1546. runlist_element *rl, *rl_end, *rl_real_end, *trl;
  1547. int old_size;
  1548. bool lcn_fixup = false;
  1549. ntfs_debug("Entering for start 0x%llx, length 0x%llx.",
  1550. (long long)start, (long long)length);
  1551. BUG_ON(!runlist);
  1552. BUG_ON(start < 0);
  1553. BUG_ON(length < 0);
  1554. BUG_ON(end < 0);
  1555. rl = runlist->rl;
  1556. if (unlikely(!rl)) {
  1557. if (likely(!start && !length))
  1558. return 0;
  1559. return -ENOENT;
  1560. }
  1561. /* Find @start in the runlist. */
  1562. while (likely(rl->length && start >= rl[1].vcn))
  1563. rl++;
  1564. rl_end = rl;
  1565. /* Find @end in the runlist. */
  1566. while (likely(rl_end->length && end >= rl_end[1].vcn)) {
  1567. /* Verify there are no unmapped or error elements. */
  1568. if (unlikely(rl_end->lcn < LCN_HOLE))
  1569. return -EINVAL;
  1570. rl_end++;
  1571. }
  1572. /* Check the last element. */
  1573. if (unlikely(rl_end->length && rl_end->lcn < LCN_HOLE))
  1574. return -EINVAL;
  1575. /* This covers @start being out of bounds, too. */
  1576. if (!rl_end->length && end > rl_end->vcn)
  1577. return -ENOENT;
  1578. if (!length)
  1579. return 0;
  1580. if (!rl->length)
  1581. return -ENOENT;
  1582. rl_real_end = rl_end;
  1583. /* Determine the runlist size. */
  1584. while (likely(rl_real_end->length))
  1585. rl_real_end++;
  1586. old_size = rl_real_end - runlist->rl + 1;
  1587. /* If @start is in a hole simply extend the hole. */
  1588. if (rl->lcn == LCN_HOLE) {
  1589. /*
  1590. * If both @start and @end are in the same sparse run, we are
  1591. * done.
  1592. */
  1593. if (end <= rl[1].vcn) {
  1594. ntfs_debug("Done (requested hole is already sparse).");
  1595. return 0;
  1596. }
  1597. extend_hole:
  1598. /* Extend the hole. */
  1599. rl->length = end - rl->vcn;
  1600. /* If @end is in a hole, merge it with the current one. */
  1601. if (rl_end->lcn == LCN_HOLE) {
  1602. rl_end++;
  1603. rl->length = rl_end->vcn - rl->vcn;
  1604. }
  1605. /* We have done the hole. Now deal with the remaining tail. */
  1606. rl++;
  1607. /* Cut out all runlist elements up to @end. */
  1608. if (rl < rl_end)
  1609. memmove(rl, rl_end, (rl_real_end - rl_end + 1) *
  1610. sizeof(*rl));
  1611. /* Adjust the beginning of the tail if necessary. */
  1612. if (end > rl->vcn) {
  1613. delta = end - rl->vcn;
  1614. rl->vcn = end;
  1615. rl->length -= delta;
  1616. /* Only adjust the lcn if it is real. */
  1617. if (rl->lcn >= 0)
  1618. rl->lcn += delta;
  1619. }
  1620. shrink_allocation:
  1621. /* Reallocate memory if the allocation changed. */
  1622. if (rl < rl_end) {
  1623. rl = ntfs_rl_realloc(runlist->rl, old_size,
  1624. old_size - (rl_end - rl));
  1625. if (IS_ERR(rl))
  1626. ntfs_warning(vol->sb, "Failed to shrink "
  1627. "runlist buffer. This just "
  1628. "wastes a bit of memory "
  1629. "temporarily so we ignore it "
  1630. "and return success.");
  1631. else
  1632. runlist->rl = rl;
  1633. }
  1634. ntfs_debug("Done (extend hole).");
  1635. return 0;
  1636. }
  1637. /*
  1638. * If @start is at the beginning of a run things are easier as there is
  1639. * no need to split the first run.
  1640. */
  1641. if (start == rl->vcn) {
  1642. /*
  1643. * @start is at the beginning of a run.
  1644. *
  1645. * If the previous run is sparse, extend its hole.
  1646. *
  1647. * If @end is not in the same run, switch the run to be sparse
  1648. * and extend the newly created hole.
  1649. *
  1650. * Thus both of these cases reduce the problem to the above
  1651. * case of "@start is in a hole".
  1652. */
  1653. if (rl > runlist->rl && (rl - 1)->lcn == LCN_HOLE) {
  1654. rl--;
  1655. goto extend_hole;
  1656. }
  1657. if (end >= rl[1].vcn) {
  1658. rl->lcn = LCN_HOLE;
  1659. goto extend_hole;
  1660. }
  1661. /*
  1662. * The final case is when @end is in the same run as @start.
  1663. * For this need to split the run into two. One run for the
  1664. * sparse region between the beginning of the old run, i.e.
  1665. * @start, and @end and one for the remaining non-sparse
  1666. * region, i.e. between @end and the end of the old run.
  1667. */
  1668. trl = ntfs_rl_realloc(runlist->rl, old_size, old_size + 1);
  1669. if (IS_ERR(trl))
  1670. goto enomem_out;
  1671. old_size++;
  1672. if (runlist->rl != trl) {
  1673. rl = trl + (rl - runlist->rl);
  1674. rl_end = trl + (rl_end - runlist->rl);
  1675. rl_real_end = trl + (rl_real_end - runlist->rl);
  1676. runlist->rl = trl;
  1677. }
  1678. split_end:
  1679. /* Shift all the runs up by one. */
  1680. memmove(rl + 1, rl, (rl_real_end - rl + 1) * sizeof(*rl));
  1681. /* Finally, setup the two split runs. */
  1682. rl->lcn = LCN_HOLE;
  1683. rl->length = length;
  1684. rl++;
  1685. rl->vcn += length;
  1686. /* Only adjust the lcn if it is real. */
  1687. if (rl->lcn >= 0 || lcn_fixup)
  1688. rl->lcn += length;
  1689. rl->length -= length;
  1690. ntfs_debug("Done (split one).");
  1691. return 0;
  1692. }
  1693. /*
  1694. * @start is neither in a hole nor at the beginning of a run.
  1695. *
  1696. * If @end is in a hole, things are easier as simply truncating the run
  1697. * @start is in to end at @start - 1, deleting all runs after that up
  1698. * to @end, and finally extending the beginning of the run @end is in
  1699. * to be @start is all that is needed.
  1700. */
  1701. if (rl_end->lcn == LCN_HOLE) {
  1702. /* Truncate the run containing @start. */
  1703. rl->length = start - rl->vcn;
  1704. rl++;
  1705. /* Cut out all runlist elements up to @end. */
  1706. if (rl < rl_end)
  1707. memmove(rl, rl_end, (rl_real_end - rl_end + 1) *
  1708. sizeof(*rl));
  1709. /* Extend the beginning of the run @end is in to be @start. */
  1710. rl->vcn = start;
  1711. rl->length = rl[1].vcn - start;
  1712. goto shrink_allocation;
  1713. }
  1714. /*
  1715. * If @end is not in a hole there are still two cases to distinguish.
  1716. * Either @end is or is not in the same run as @start.
  1717. *
  1718. * The second case is easier as it can be reduced to an already solved
  1719. * problem by truncating the run @start is in to end at @start - 1.
  1720. * Then, if @end is in the next run need to split the run into a sparse
  1721. * run followed by a non-sparse run (already covered above) and if @end
  1722. * is not in the next run switching it to be sparse, again reduces the
  1723. * problem to the already covered case of "@start is in a hole".
  1724. */
  1725. if (end >= rl[1].vcn) {
  1726. /*
  1727. * If @end is not in the next run, reduce the problem to the
  1728. * case of "@start is in a hole".
  1729. */
  1730. if (rl[1].length && end >= rl[2].vcn) {
  1731. /* Truncate the run containing @start. */
  1732. rl->length = start - rl->vcn;
  1733. rl++;
  1734. rl->vcn = start;
  1735. rl->lcn = LCN_HOLE;
  1736. goto extend_hole;
  1737. }
  1738. trl = ntfs_rl_realloc(runlist->rl, old_size, old_size + 1);
  1739. if (IS_ERR(trl))
  1740. goto enomem_out;
  1741. old_size++;
  1742. if (runlist->rl != trl) {
  1743. rl = trl + (rl - runlist->rl);
  1744. rl_end = trl + (rl_end - runlist->rl);
  1745. rl_real_end = trl + (rl_real_end - runlist->rl);
  1746. runlist->rl = trl;
  1747. }
  1748. /* Truncate the run containing @start. */
  1749. rl->length = start - rl->vcn;
  1750. rl++;
  1751. /*
  1752. * @end is in the next run, reduce the problem to the case
  1753. * where "@start is at the beginning of a run and @end is in
  1754. * the same run as @start".
  1755. */
  1756. delta = rl->vcn - start;
  1757. rl->vcn = start;
  1758. if (rl->lcn >= 0) {
  1759. rl->lcn -= delta;
  1760. /* Need this in case the lcn just became negative. */
  1761. lcn_fixup = true;
  1762. }
  1763. rl->length += delta;
  1764. goto split_end;
  1765. }
  1766. /*
  1767. * The first case from above, i.e. @end is in the same run as @start.
  1768. * We need to split the run into three. One run for the non-sparse
  1769. * region between the beginning of the old run and @start, one for the
  1770. * sparse region between @start and @end, and one for the remaining
  1771. * non-sparse region, i.e. between @end and the end of the old run.
  1772. */
  1773. trl = ntfs_rl_realloc(runlist->rl, old_size, old_size + 2);
  1774. if (IS_ERR(trl))
  1775. goto enomem_out;
  1776. old_size += 2;
  1777. if (runlist->rl != trl) {
  1778. rl = trl + (rl - runlist->rl);
  1779. rl_end = trl + (rl_end - runlist->rl);
  1780. rl_real_end = trl + (rl_real_end - runlist->rl);
  1781. runlist->rl = trl;
  1782. }
  1783. /* Shift all the runs up by two. */
  1784. memmove(rl + 2, rl, (rl_real_end - rl + 1) * sizeof(*rl));
  1785. /* Finally, setup the three split runs. */
  1786. rl->length = start - rl->vcn;
  1787. rl++;
  1788. rl->vcn = start;
  1789. rl->lcn = LCN_HOLE;
  1790. rl->length = length;
  1791. rl++;
  1792. delta = end - rl->vcn;
  1793. rl->vcn = end;
  1794. rl->lcn += delta;
  1795. rl->length -= delta;
  1796. ntfs_debug("Done (split both).");
  1797. return 0;
  1798. enomem_out:
  1799. ntfs_error(vol->sb, "Not enough memory to extend runlist buffer.");
  1800. return -ENOMEM;
  1801. }
  1802. #endif /* NTFS_RW */