runlist.c 59 KB

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