dm-bow.c 30 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304
  1. /*
  2. * Copyright (C) 2018 Google Limited.
  3. *
  4. * This file is released under the GPL.
  5. */
  6. #include "dm.h"
  7. #include "dm-core.h"
  8. #include <linux/crc32.h>
  9. #include <linux/dm-bufio.h>
  10. #include <linux/module.h>
  11. #define DM_MSG_PREFIX "bow"
  12. struct log_entry {
  13. u64 source;
  14. u64 dest;
  15. u32 size;
  16. u32 checksum;
  17. } __packed;
  18. struct log_sector {
  19. u32 magic;
  20. u16 header_version;
  21. u16 header_size;
  22. u32 block_size;
  23. u32 count;
  24. u32 sequence;
  25. sector_t sector0;
  26. struct log_entry entries[];
  27. } __packed;
  28. /*
  29. * MAGIC is BOW in ascii
  30. */
  31. #define MAGIC 0x00574f42
  32. #define HEADER_VERSION 0x0100
  33. /*
  34. * A sorted set of ranges representing the state of the data on the device.
  35. * Use an rb_tree for fast lookup of a given sector
  36. * Consecutive ranges are always of different type - operations on this
  37. * set must merge matching consecutive ranges.
  38. *
  39. * Top range is always of type TOP
  40. */
  41. struct bow_range {
  42. struct rb_node node;
  43. sector_t sector;
  44. enum {
  45. INVALID, /* Type not set */
  46. SECTOR0, /* First sector - holds log record */
  47. SECTOR0_CURRENT,/* Live contents of sector0 */
  48. UNCHANGED, /* Original contents */
  49. TRIMMED, /* Range has been trimmed */
  50. CHANGED, /* Range has been changed */
  51. BACKUP, /* Range is being used as a backup */
  52. TOP, /* Final range - sector is size of device */
  53. } type;
  54. struct list_head trimmed_list; /* list of TRIMMED ranges */
  55. };
  56. static const char * const readable_type[] = {
  57. "Invalid",
  58. "Sector0",
  59. "Sector0_current",
  60. "Unchanged",
  61. "Free",
  62. "Changed",
  63. "Backup",
  64. "Top",
  65. };
  66. enum state {
  67. TRIM,
  68. CHECKPOINT,
  69. COMMITTED,
  70. };
  71. struct bow_context {
  72. struct dm_dev *dev;
  73. u32 block_size;
  74. u32 block_shift;
  75. struct workqueue_struct *workqueue;
  76. struct dm_bufio_client *bufio;
  77. struct mutex ranges_lock; /* Hold to access this struct and/or ranges */
  78. struct rb_root ranges;
  79. struct dm_kobject_holder kobj_holder; /* for sysfs attributes */
  80. atomic_t state; /* One of the enum state values above */
  81. u64 trims_total;
  82. struct log_sector *log_sector;
  83. struct list_head trimmed_list;
  84. bool forward_trims;
  85. };
  86. sector_t range_top(struct bow_range *br)
  87. {
  88. return container_of(rb_next(&br->node), struct bow_range, node)
  89. ->sector;
  90. }
  91. u64 range_size(struct bow_range *br)
  92. {
  93. return (range_top(br) - br->sector) * SECTOR_SIZE;
  94. }
  95. static sector_t bvec_top(struct bvec_iter *bi_iter)
  96. {
  97. return bi_iter->bi_sector + bi_iter->bi_size / SECTOR_SIZE;
  98. }
  99. /*
  100. * Find the first range that overlaps with bi_iter
  101. * bi_iter is set to the size of the overlapping sub-range
  102. */
  103. static struct bow_range *find_first_overlapping_range(struct rb_root *ranges,
  104. struct bvec_iter *bi_iter)
  105. {
  106. struct rb_node *node = ranges->rb_node;
  107. struct bow_range *br;
  108. while (node) {
  109. br = container_of(node, struct bow_range, node);
  110. if (br->sector <= bi_iter->bi_sector
  111. && bi_iter->bi_sector < range_top(br))
  112. break;
  113. if (bi_iter->bi_sector < br->sector)
  114. node = node->rb_left;
  115. else
  116. node = node->rb_right;
  117. }
  118. WARN_ON(!node);
  119. if (!node)
  120. return NULL;
  121. if (range_top(br) - bi_iter->bi_sector
  122. < bi_iter->bi_size >> SECTOR_SHIFT)
  123. bi_iter->bi_size = (range_top(br) - bi_iter->bi_sector)
  124. << SECTOR_SHIFT;
  125. return br;
  126. }
  127. void add_before(struct rb_root *ranges, struct bow_range *new_br,
  128. struct bow_range *existing)
  129. {
  130. struct rb_node *parent = &(existing->node);
  131. struct rb_node **link = &(parent->rb_left);
  132. while (*link) {
  133. parent = *link;
  134. link = &((*link)->rb_right);
  135. }
  136. rb_link_node(&new_br->node, parent, link);
  137. rb_insert_color(&new_br->node, ranges);
  138. }
  139. /*
  140. * Given a range br returned by find_first_overlapping_range, split br into a
  141. * leading range, a range matching the bi_iter and a trailing range.
  142. * Leading and trailing may end up size 0 and will then be deleted. The
  143. * new range matching the bi_iter is then returned and should have its type
  144. * and type specific fields populated.
  145. * If bi_iter runs off the end of the range, bi_iter is truncated accordingly
  146. */
  147. static int split_range(struct bow_context *bc, struct bow_range **br,
  148. struct bvec_iter *bi_iter)
  149. {
  150. struct bow_range *new_br;
  151. if (bi_iter->bi_sector < (*br)->sector) {
  152. WARN_ON(true);
  153. return BLK_STS_IOERR;
  154. }
  155. if (bi_iter->bi_sector > (*br)->sector) {
  156. struct bow_range *leading_br =
  157. kzalloc(sizeof(*leading_br), GFP_KERNEL);
  158. if (!leading_br)
  159. return BLK_STS_RESOURCE;
  160. *leading_br = **br;
  161. if (leading_br->type == TRIMMED)
  162. list_add(&leading_br->trimmed_list, &bc->trimmed_list);
  163. add_before(&bc->ranges, leading_br, *br);
  164. (*br)->sector = bi_iter->bi_sector;
  165. }
  166. if (bvec_top(bi_iter) >= range_top(*br)) {
  167. bi_iter->bi_size = (range_top(*br) - (*br)->sector)
  168. * SECTOR_SIZE;
  169. return BLK_STS_OK;
  170. }
  171. /* new_br will be the beginning, existing br will be the tail */
  172. new_br = kzalloc(sizeof(*new_br), GFP_KERNEL);
  173. if (!new_br)
  174. return BLK_STS_RESOURCE;
  175. new_br->sector = (*br)->sector;
  176. (*br)->sector = bvec_top(bi_iter);
  177. add_before(&bc->ranges, new_br, *br);
  178. *br = new_br;
  179. return BLK_STS_OK;
  180. }
  181. /*
  182. * Sets type of a range. May merge range into surrounding ranges
  183. * Since br may be invalidated, always sets br to NULL to prevent
  184. * usage after this is called
  185. */
  186. static void set_type(struct bow_context *bc, struct bow_range **br, int type)
  187. {
  188. struct bow_range *prev = container_of(rb_prev(&(*br)->node),
  189. struct bow_range, node);
  190. struct bow_range *next = container_of(rb_next(&(*br)->node),
  191. struct bow_range, node);
  192. if ((*br)->type == TRIMMED) {
  193. bc->trims_total -= range_size(*br);
  194. list_del(&(*br)->trimmed_list);
  195. }
  196. if (type == TRIMMED) {
  197. bc->trims_total += range_size(*br);
  198. list_add(&(*br)->trimmed_list, &bc->trimmed_list);
  199. }
  200. (*br)->type = type;
  201. if (next->type == type) {
  202. if (type == TRIMMED)
  203. list_del(&next->trimmed_list);
  204. rb_erase(&next->node, &bc->ranges);
  205. kfree(next);
  206. }
  207. if (prev->type == type) {
  208. if (type == TRIMMED)
  209. list_del(&(*br)->trimmed_list);
  210. rb_erase(&(*br)->node, &bc->ranges);
  211. kfree(*br);
  212. }
  213. *br = NULL;
  214. }
  215. static struct bow_range *find_free_range(struct bow_context *bc)
  216. {
  217. if (list_empty(&bc->trimmed_list)) {
  218. DMERR("Unable to find free space to back up to");
  219. return NULL;
  220. }
  221. return list_first_entry(&bc->trimmed_list, struct bow_range,
  222. trimmed_list);
  223. }
  224. static sector_t sector_to_page(struct bow_context const *bc, sector_t sector)
  225. {
  226. WARN_ON((sector & (((sector_t)1 << (bc->block_shift - SECTOR_SHIFT)) - 1))
  227. != 0);
  228. return sector >> (bc->block_shift - SECTOR_SHIFT);
  229. }
  230. static int copy_data(struct bow_context const *bc,
  231. struct bow_range *source, struct bow_range *dest,
  232. u32 *checksum)
  233. {
  234. int i;
  235. if (range_size(source) != range_size(dest)) {
  236. WARN_ON(1);
  237. return BLK_STS_IOERR;
  238. }
  239. if (checksum)
  240. *checksum = sector_to_page(bc, source->sector);
  241. for (i = 0; i < range_size(source) >> bc->block_shift; ++i) {
  242. struct dm_buffer *read_buffer, *write_buffer;
  243. u8 *read, *write;
  244. sector_t page = sector_to_page(bc, source->sector) + i;
  245. read = dm_bufio_read(bc->bufio, page, &read_buffer);
  246. if (IS_ERR(read)) {
  247. DMERR("Cannot read page %llu",
  248. (unsigned long long)page);
  249. return PTR_ERR(read);
  250. }
  251. if (checksum)
  252. *checksum = crc32(*checksum, read, bc->block_size);
  253. write = dm_bufio_new(bc->bufio,
  254. sector_to_page(bc, dest->sector) + i,
  255. &write_buffer);
  256. if (IS_ERR(write)) {
  257. DMERR("Cannot write sector");
  258. dm_bufio_release(read_buffer);
  259. return PTR_ERR(write);
  260. }
  261. memcpy(write, read, bc->block_size);
  262. dm_bufio_mark_buffer_dirty(write_buffer);
  263. dm_bufio_release(write_buffer);
  264. dm_bufio_release(read_buffer);
  265. }
  266. dm_bufio_write_dirty_buffers(bc->bufio);
  267. return BLK_STS_OK;
  268. }
  269. /****** logging functions ******/
  270. static int add_log_entry(struct bow_context *bc, sector_t source, sector_t dest,
  271. unsigned int size, u32 checksum);
  272. static int backup_log_sector(struct bow_context *bc)
  273. {
  274. struct bow_range *first_br, *free_br;
  275. struct bvec_iter bi_iter;
  276. u32 checksum = 0;
  277. int ret;
  278. first_br = container_of(rb_first(&bc->ranges), struct bow_range, node);
  279. if (first_br->type != SECTOR0) {
  280. WARN_ON(1);
  281. return BLK_STS_IOERR;
  282. }
  283. if (range_size(first_br) != bc->block_size) {
  284. WARN_ON(1);
  285. return BLK_STS_IOERR;
  286. }
  287. free_br = find_free_range(bc);
  288. /* No space left - return this error to userspace */
  289. if (!free_br)
  290. return BLK_STS_NOSPC;
  291. bi_iter.bi_sector = free_br->sector;
  292. bi_iter.bi_size = bc->block_size;
  293. ret = split_range(bc, &free_br, &bi_iter);
  294. if (ret)
  295. return ret;
  296. if (bi_iter.bi_size != bc->block_size) {
  297. WARN_ON(1);
  298. return BLK_STS_IOERR;
  299. }
  300. ret = copy_data(bc, first_br, free_br, &checksum);
  301. if (ret)
  302. return ret;
  303. bc->log_sector->count = 0;
  304. bc->log_sector->sequence++;
  305. ret = add_log_entry(bc, first_br->sector, free_br->sector,
  306. range_size(first_br), checksum);
  307. if (ret)
  308. return ret;
  309. set_type(bc, &free_br, BACKUP);
  310. return BLK_STS_OK;
  311. }
  312. static int add_log_entry(struct bow_context *bc, sector_t source, sector_t dest,
  313. unsigned int size, u32 checksum)
  314. {
  315. struct dm_buffer *sector_buffer;
  316. u8 *sector;
  317. if (sizeof(struct log_sector)
  318. + sizeof(struct log_entry) * (bc->log_sector->count + 1)
  319. > bc->block_size) {
  320. int ret = backup_log_sector(bc);
  321. if (ret)
  322. return ret;
  323. }
  324. sector = dm_bufio_new(bc->bufio, 0, &sector_buffer);
  325. if (IS_ERR(sector)) {
  326. DMERR("Cannot write boot sector");
  327. dm_bufio_release(sector_buffer);
  328. return BLK_STS_NOSPC;
  329. }
  330. bc->log_sector->entries[bc->log_sector->count].source = source;
  331. bc->log_sector->entries[bc->log_sector->count].dest = dest;
  332. bc->log_sector->entries[bc->log_sector->count].size = size;
  333. bc->log_sector->entries[bc->log_sector->count].checksum = checksum;
  334. bc->log_sector->count++;
  335. memcpy(sector, bc->log_sector, bc->block_size);
  336. dm_bufio_mark_buffer_dirty(sector_buffer);
  337. dm_bufio_release(sector_buffer);
  338. dm_bufio_write_dirty_buffers(bc->bufio);
  339. return BLK_STS_OK;
  340. }
  341. static int prepare_log(struct bow_context *bc)
  342. {
  343. struct bow_range *free_br, *first_br;
  344. struct bvec_iter bi_iter;
  345. u32 checksum = 0;
  346. int ret;
  347. /* Carve out first sector as log sector */
  348. first_br = container_of(rb_first(&bc->ranges), struct bow_range, node);
  349. if (first_br->type != UNCHANGED) {
  350. WARN_ON(1);
  351. return BLK_STS_IOERR;
  352. }
  353. if (range_size(first_br) < bc->block_size) {
  354. WARN_ON(1);
  355. return BLK_STS_IOERR;
  356. }
  357. bi_iter.bi_sector = 0;
  358. bi_iter.bi_size = bc->block_size;
  359. ret = split_range(bc, &first_br, &bi_iter);
  360. if (ret)
  361. return ret;
  362. first_br->type = SECTOR0;
  363. if (range_size(first_br) != bc->block_size) {
  364. WARN_ON(1);
  365. return BLK_STS_IOERR;
  366. }
  367. /* Find free sector for active sector0 reads/writes */
  368. free_br = find_free_range(bc);
  369. if (!free_br)
  370. return BLK_STS_NOSPC;
  371. bi_iter.bi_sector = free_br->sector;
  372. bi_iter.bi_size = bc->block_size;
  373. ret = split_range(bc, &free_br, &bi_iter);
  374. if (ret)
  375. return ret;
  376. free_br->type = SECTOR0_CURRENT;
  377. /* Copy data */
  378. ret = copy_data(bc, first_br, free_br, NULL);
  379. if (ret)
  380. return ret;
  381. bc->log_sector->sector0 = free_br->sector;
  382. /* Find free sector to back up original sector zero */
  383. free_br = find_free_range(bc);
  384. if (!free_br)
  385. return BLK_STS_NOSPC;
  386. bi_iter.bi_sector = free_br->sector;
  387. bi_iter.bi_size = bc->block_size;
  388. ret = split_range(bc, &free_br, &bi_iter);
  389. if (ret)
  390. return ret;
  391. /* Back up */
  392. ret = copy_data(bc, first_br, free_br, &checksum);
  393. if (ret)
  394. return ret;
  395. /*
  396. * Set up our replacement boot sector - it will get written when we
  397. * add the first log entry, which we do immediately
  398. */
  399. bc->log_sector->magic = MAGIC;
  400. bc->log_sector->header_version = HEADER_VERSION;
  401. bc->log_sector->header_size = sizeof(*bc->log_sector);
  402. bc->log_sector->block_size = bc->block_size;
  403. bc->log_sector->count = 0;
  404. bc->log_sector->sequence = 0;
  405. /* Add log entry */
  406. ret = add_log_entry(bc, first_br->sector, free_br->sector,
  407. range_size(first_br), checksum);
  408. if (ret)
  409. return ret;
  410. set_type(bc, &free_br, BACKUP);
  411. return BLK_STS_OK;
  412. }
  413. static struct bow_range *find_sector0_current(struct bow_context *bc)
  414. {
  415. struct bvec_iter bi_iter;
  416. bi_iter.bi_sector = bc->log_sector->sector0;
  417. bi_iter.bi_size = bc->block_size;
  418. return find_first_overlapping_range(&bc->ranges, &bi_iter);
  419. }
  420. /****** sysfs interface functions ******/
  421. static ssize_t state_show(struct kobject *kobj, struct kobj_attribute *attr,
  422. char *buf)
  423. {
  424. struct bow_context *bc = container_of(kobj, struct bow_context,
  425. kobj_holder.kobj);
  426. return scnprintf(buf, PAGE_SIZE, "%d\n", atomic_read(&bc->state));
  427. }
  428. static ssize_t state_store(struct kobject *kobj, struct kobj_attribute *attr,
  429. const char *buf, size_t count)
  430. {
  431. struct bow_context *bc = container_of(kobj, struct bow_context,
  432. kobj_holder.kobj);
  433. enum state state, original_state;
  434. int ret;
  435. state = buf[0] - '0';
  436. if (state < TRIM || state > COMMITTED) {
  437. DMERR("State value %d out of range", state);
  438. return -EINVAL;
  439. }
  440. mutex_lock(&bc->ranges_lock);
  441. original_state = atomic_read(&bc->state);
  442. if (state != original_state + 1) {
  443. DMERR("Invalid state change from %d to %d",
  444. original_state, state);
  445. ret = -EINVAL;
  446. goto bad;
  447. }
  448. DMINFO("Switching to state %s", state == CHECKPOINT ? "Checkpoint"
  449. : state == COMMITTED ? "Committed" : "Unknown");
  450. if (state == CHECKPOINT) {
  451. ret = prepare_log(bc);
  452. if (ret) {
  453. DMERR("Failed to switch to checkpoint state");
  454. goto bad;
  455. }
  456. } else if (state == COMMITTED) {
  457. struct bow_range *br = find_sector0_current(bc);
  458. struct bow_range *sector0_br =
  459. container_of(rb_first(&bc->ranges), struct bow_range,
  460. node);
  461. ret = copy_data(bc, br, sector0_br, 0);
  462. if (ret) {
  463. DMERR("Failed to switch to committed state");
  464. goto bad;
  465. }
  466. }
  467. atomic_inc(&bc->state);
  468. ret = count;
  469. bad:
  470. mutex_unlock(&bc->ranges_lock);
  471. return ret;
  472. }
  473. static ssize_t free_show(struct kobject *kobj, struct kobj_attribute *attr,
  474. char *buf)
  475. {
  476. struct bow_context *bc = container_of(kobj, struct bow_context,
  477. kobj_holder.kobj);
  478. u64 trims_total;
  479. mutex_lock(&bc->ranges_lock);
  480. trims_total = bc->trims_total;
  481. mutex_unlock(&bc->ranges_lock);
  482. return scnprintf(buf, PAGE_SIZE, "%llu\n", trims_total);
  483. }
  484. static struct kobj_attribute attr_state = __ATTR_RW(state);
  485. static struct kobj_attribute attr_free = __ATTR_RO(free);
  486. static struct attribute *bow_attrs[] = {
  487. &attr_state.attr,
  488. &attr_free.attr,
  489. NULL
  490. };
  491. static struct kobj_type bow_ktype = {
  492. .sysfs_ops = &kobj_sysfs_ops,
  493. .default_attrs = bow_attrs,
  494. .release = dm_kobject_release
  495. };
  496. /****** constructor/destructor ******/
  497. static void dm_bow_dtr(struct dm_target *ti)
  498. {
  499. struct bow_context *bc = (struct bow_context *) ti->private;
  500. struct kobject *kobj;
  501. mutex_lock(&bc->ranges_lock);
  502. while (rb_first(&bc->ranges)) {
  503. struct bow_range *br = container_of(rb_first(&bc->ranges),
  504. struct bow_range, node);
  505. rb_erase(&br->node, &bc->ranges);
  506. kfree(br);
  507. }
  508. mutex_unlock(&bc->ranges_lock);
  509. if (bc->workqueue)
  510. destroy_workqueue(bc->workqueue);
  511. if (bc->bufio)
  512. dm_bufio_client_destroy(bc->bufio);
  513. kobj = &bc->kobj_holder.kobj;
  514. if (kobj->state_initialized) {
  515. kobject_put(kobj);
  516. wait_for_completion(dm_get_completion_from_kobject(kobj));
  517. }
  518. kfree(bc->log_sector);
  519. kfree(bc);
  520. }
  521. static void dm_bow_io_hints(struct dm_target *ti, struct queue_limits *limits)
  522. {
  523. struct bow_context *bc = ti->private;
  524. const unsigned int block_size = bc->block_size;
  525. limits->logical_block_size =
  526. max_t(unsigned int, limits->logical_block_size, block_size);
  527. limits->physical_block_size =
  528. max_t(unsigned int, limits->physical_block_size, block_size);
  529. limits->io_min = max_t(unsigned int, limits->io_min, block_size);
  530. if (limits->max_discard_sectors == 0) {
  531. limits->discard_granularity = 1 << 12;
  532. limits->max_hw_discard_sectors = 1 << 15;
  533. limits->max_discard_sectors = 1 << 15;
  534. bc->forward_trims = false;
  535. } else {
  536. limits->discard_granularity = 1 << 12;
  537. bc->forward_trims = true;
  538. }
  539. }
  540. static int dm_bow_ctr_optional(struct dm_target *ti, unsigned int argc, char **argv)
  541. {
  542. struct bow_context *bc = ti->private;
  543. struct dm_arg_set as;
  544. static const struct dm_arg _args[] = {
  545. {0, 1, "Invalid number of feature args"},
  546. };
  547. unsigned int opt_params;
  548. const char *opt_string;
  549. int err;
  550. char dummy;
  551. as.argc = argc;
  552. as.argv = argv;
  553. err = dm_read_arg_group(_args, &as, &opt_params, &ti->error);
  554. if (err)
  555. return err;
  556. while (opt_params--) {
  557. opt_string = dm_shift_arg(&as);
  558. if (!opt_string) {
  559. ti->error = "Not enough feature arguments";
  560. return -EINVAL;
  561. }
  562. if (sscanf(opt_string, "block_size:%u%c",
  563. &bc->block_size, &dummy) == 1) {
  564. if (bc->block_size < SECTOR_SIZE ||
  565. bc->block_size > 4096 ||
  566. !is_power_of_2(bc->block_size)) {
  567. ti->error = "Invalid block_size";
  568. return -EINVAL;
  569. }
  570. } else {
  571. ti->error = "Invalid feature arguments";
  572. return -EINVAL;
  573. }
  574. }
  575. return 0;
  576. }
  577. static int dm_bow_ctr(struct dm_target *ti, unsigned int argc, char **argv)
  578. {
  579. struct bow_context *bc;
  580. struct bow_range *br;
  581. int ret;
  582. struct mapped_device *md = dm_table_get_md(ti->table);
  583. if (argc < 1) {
  584. ti->error = "Invalid argument count";
  585. return -EINVAL;
  586. }
  587. bc = kzalloc(sizeof(*bc), GFP_KERNEL);
  588. if (!bc) {
  589. ti->error = "Cannot allocate bow context";
  590. return -ENOMEM;
  591. }
  592. ti->num_flush_bios = 1;
  593. ti->num_discard_bios = 1;
  594. ti->num_write_same_bios = 1;
  595. ti->private = bc;
  596. ret = dm_get_device(ti, argv[0], dm_table_get_mode(ti->table),
  597. &bc->dev);
  598. if (ret) {
  599. ti->error = "Device lookup failed";
  600. goto bad;
  601. }
  602. bc->block_size =
  603. bdev_get_queue(bc->dev->bdev)->limits.logical_block_size;
  604. if (argc > 1) {
  605. ret = dm_bow_ctr_optional(ti, argc - 1, &argv[1]);
  606. if (ret)
  607. goto bad;
  608. }
  609. bc->block_shift = ilog2(bc->block_size);
  610. bc->log_sector = kzalloc(bc->block_size, GFP_KERNEL);
  611. if (!bc->log_sector) {
  612. ti->error = "Cannot allocate log sector";
  613. goto bad;
  614. }
  615. init_completion(&bc->kobj_holder.completion);
  616. ret = kobject_init_and_add(&bc->kobj_holder.kobj, &bow_ktype,
  617. &disk_to_dev(dm_disk(md))->kobj, "%s",
  618. "bow");
  619. if (ret) {
  620. ti->error = "Cannot create sysfs node";
  621. goto bad;
  622. }
  623. mutex_init(&bc->ranges_lock);
  624. bc->ranges = RB_ROOT;
  625. bc->bufio = dm_bufio_client_create(bc->dev->bdev, bc->block_size, 1, 0,
  626. NULL, NULL);
  627. if (IS_ERR(bc->bufio)) {
  628. ti->error = "Cannot initialize dm-bufio";
  629. ret = PTR_ERR(bc->bufio);
  630. bc->bufio = NULL;
  631. goto bad;
  632. }
  633. bc->workqueue = alloc_workqueue("dm-bow",
  634. WQ_CPU_INTENSIVE | WQ_MEM_RECLAIM
  635. | WQ_UNBOUND, num_online_cpus());
  636. if (!bc->workqueue) {
  637. ti->error = "Cannot allocate workqueue";
  638. ret = -ENOMEM;
  639. goto bad;
  640. }
  641. INIT_LIST_HEAD(&bc->trimmed_list);
  642. br = kzalloc(sizeof(*br), GFP_KERNEL);
  643. if (!br) {
  644. ti->error = "Cannot allocate ranges";
  645. ret = -ENOMEM;
  646. goto bad;
  647. }
  648. br->sector = ti->len;
  649. br->type = TOP;
  650. rb_link_node(&br->node, NULL, &bc->ranges.rb_node);
  651. rb_insert_color(&br->node, &bc->ranges);
  652. br = kzalloc(sizeof(*br), GFP_KERNEL);
  653. if (!br) {
  654. ti->error = "Cannot allocate ranges";
  655. ret = -ENOMEM;
  656. goto bad;
  657. }
  658. br->sector = 0;
  659. br->type = UNCHANGED;
  660. rb_link_node(&br->node, bc->ranges.rb_node,
  661. &bc->ranges.rb_node->rb_left);
  662. rb_insert_color(&br->node, &bc->ranges);
  663. ti->discards_supported = true;
  664. return 0;
  665. bad:
  666. dm_bow_dtr(ti);
  667. return ret;
  668. }
  669. /****** Handle writes ******/
  670. static int prepare_unchanged_range(struct bow_context *bc, struct bow_range *br,
  671. struct bvec_iter *bi_iter,
  672. bool record_checksum)
  673. {
  674. struct bow_range *backup_br;
  675. struct bvec_iter backup_bi;
  676. sector_t log_source, log_dest;
  677. unsigned int log_size;
  678. u32 checksum = 0;
  679. int ret;
  680. int original_type;
  681. sector_t sector0;
  682. /* Find a free range */
  683. backup_br = find_free_range(bc);
  684. if (!backup_br)
  685. return BLK_STS_NOSPC;
  686. /* Carve out a backup range. This may be smaller than the br given */
  687. backup_bi.bi_sector = backup_br->sector;
  688. backup_bi.bi_size = min(range_size(backup_br), (u64) bi_iter->bi_size);
  689. ret = split_range(bc, &backup_br, &backup_bi);
  690. if (ret)
  691. return ret;
  692. /*
  693. * Carve out a changed range. This will not be smaller than the backup
  694. * br since the backup br is smaller than the source range and iterator
  695. */
  696. bi_iter->bi_size = backup_bi.bi_size;
  697. ret = split_range(bc, &br, bi_iter);
  698. if (ret)
  699. return ret;
  700. if (range_size(br) != range_size(backup_br)) {
  701. WARN_ON(1);
  702. return BLK_STS_IOERR;
  703. }
  704. /* Copy data over */
  705. ret = copy_data(bc, br, backup_br, record_checksum ? &checksum : NULL);
  706. if (ret)
  707. return ret;
  708. /* Add an entry to the log */
  709. log_source = br->sector;
  710. log_dest = backup_br->sector;
  711. log_size = range_size(br);
  712. /*
  713. * Set the types. Note that since set_type also amalgamates ranges
  714. * we have to set both sectors to their final type before calling
  715. * set_type on either
  716. */
  717. original_type = br->type;
  718. sector0 = backup_br->sector;
  719. bc->trims_total -= range_size(backup_br);
  720. if (backup_br->type == TRIMMED)
  721. list_del(&backup_br->trimmed_list);
  722. backup_br->type = br->type == SECTOR0_CURRENT ? SECTOR0_CURRENT
  723. : BACKUP;
  724. br->type = CHANGED;
  725. set_type(bc, &backup_br, backup_br->type);
  726. /*
  727. * Add the log entry after marking the backup sector, since adding a log
  728. * can cause another backup
  729. */
  730. ret = add_log_entry(bc, log_source, log_dest, log_size, checksum);
  731. if (ret) {
  732. br->type = original_type;
  733. return ret;
  734. }
  735. /* Now it is safe to mark this backup successful */
  736. if (original_type == SECTOR0_CURRENT)
  737. bc->log_sector->sector0 = sector0;
  738. set_type(bc, &br, br->type);
  739. return ret;
  740. }
  741. static int prepare_free_range(struct bow_context *bc, struct bow_range *br,
  742. struct bvec_iter *bi_iter)
  743. {
  744. int ret;
  745. ret = split_range(bc, &br, bi_iter);
  746. if (ret)
  747. return ret;
  748. set_type(bc, &br, CHANGED);
  749. return BLK_STS_OK;
  750. }
  751. static int prepare_changed_range(struct bow_context *bc, struct bow_range *br,
  752. struct bvec_iter *bi_iter)
  753. {
  754. /* Nothing to do ... */
  755. return BLK_STS_OK;
  756. }
  757. static int prepare_one_range(struct bow_context *bc,
  758. struct bvec_iter *bi_iter)
  759. {
  760. struct bow_range *br = find_first_overlapping_range(&bc->ranges,
  761. bi_iter);
  762. switch (br->type) {
  763. case CHANGED:
  764. return prepare_changed_range(bc, br, bi_iter);
  765. case TRIMMED:
  766. return prepare_free_range(bc, br, bi_iter);
  767. case UNCHANGED:
  768. case BACKUP:
  769. return prepare_unchanged_range(bc, br, bi_iter, true);
  770. /*
  771. * We cannot track the checksum for the active sector0, since it
  772. * may change at any point.
  773. */
  774. case SECTOR0_CURRENT:
  775. return prepare_unchanged_range(bc, br, bi_iter, false);
  776. case SECTOR0: /* Handled in the dm_bow_map */
  777. case TOP: /* Illegal - top is off the end of the device */
  778. default:
  779. WARN_ON(1);
  780. return BLK_STS_IOERR;
  781. }
  782. }
  783. struct write_work {
  784. struct work_struct work;
  785. struct bow_context *bc;
  786. struct bio *bio;
  787. };
  788. static void bow_write(struct work_struct *work)
  789. {
  790. struct write_work *ww = container_of(work, struct write_work, work);
  791. struct bow_context *bc = ww->bc;
  792. struct bio *bio = ww->bio;
  793. struct bvec_iter bi_iter = bio->bi_iter;
  794. int ret = BLK_STS_OK;
  795. kfree(ww);
  796. mutex_lock(&bc->ranges_lock);
  797. do {
  798. ret = prepare_one_range(bc, &bi_iter);
  799. bi_iter.bi_sector += bi_iter.bi_size / SECTOR_SIZE;
  800. bi_iter.bi_size = bio->bi_iter.bi_size
  801. - (bi_iter.bi_sector - bio->bi_iter.bi_sector)
  802. * SECTOR_SIZE;
  803. } while (!ret && bi_iter.bi_size);
  804. mutex_unlock(&bc->ranges_lock);
  805. if (!ret) {
  806. bio_set_dev(bio, bc->dev->bdev);
  807. submit_bio(bio);
  808. } else {
  809. DMERR("Write failure with error %d", -ret);
  810. bio->bi_status = ret;
  811. bio_endio(bio);
  812. }
  813. }
  814. static int queue_write(struct bow_context *bc, struct bio *bio)
  815. {
  816. struct write_work *ww = kmalloc(sizeof(*ww), GFP_NOIO | __GFP_NORETRY
  817. | __GFP_NOMEMALLOC | __GFP_NOWARN);
  818. if (!ww) {
  819. DMERR("Failed to allocate write_work");
  820. return -ENOMEM;
  821. }
  822. INIT_WORK(&ww->work, bow_write);
  823. ww->bc = bc;
  824. ww->bio = bio;
  825. queue_work(bc->workqueue, &ww->work);
  826. return DM_MAPIO_SUBMITTED;
  827. }
  828. static int handle_sector0(struct bow_context *bc, struct bio *bio)
  829. {
  830. int ret = DM_MAPIO_REMAPPED;
  831. if (bio->bi_iter.bi_size > bc->block_size) {
  832. struct bio * split = bio_split(bio,
  833. bc->block_size >> SECTOR_SHIFT,
  834. GFP_NOIO,
  835. &fs_bio_set);
  836. if (!split) {
  837. DMERR("Failed to split bio");
  838. bio->bi_status = BLK_STS_RESOURCE;
  839. bio_endio(bio);
  840. return DM_MAPIO_SUBMITTED;
  841. }
  842. bio_chain(split, bio);
  843. split->bi_iter.bi_sector = bc->log_sector->sector0;
  844. bio_set_dev(split, bc->dev->bdev);
  845. submit_bio(split);
  846. if (bio_data_dir(bio) == WRITE)
  847. ret = queue_write(bc, bio);
  848. } else {
  849. bio->bi_iter.bi_sector = bc->log_sector->sector0;
  850. }
  851. return ret;
  852. }
  853. static int add_trim(struct bow_context *bc, struct bio *bio)
  854. {
  855. struct bow_range *br;
  856. struct bvec_iter bi_iter = bio->bi_iter;
  857. DMDEBUG("add_trim: %llu, %u",
  858. (unsigned long long)bio->bi_iter.bi_sector,
  859. bio->bi_iter.bi_size);
  860. do {
  861. br = find_first_overlapping_range(&bc->ranges, &bi_iter);
  862. switch (br->type) {
  863. case UNCHANGED:
  864. if (!split_range(bc, &br, &bi_iter))
  865. set_type(bc, &br, TRIMMED);
  866. break;
  867. case TRIMMED:
  868. /* Nothing to do */
  869. break;
  870. default:
  871. /* No other case is legal in TRIM state */
  872. WARN_ON(true);
  873. break;
  874. }
  875. bi_iter.bi_sector += bi_iter.bi_size / SECTOR_SIZE;
  876. bi_iter.bi_size = bio->bi_iter.bi_size
  877. - (bi_iter.bi_sector - bio->bi_iter.bi_sector)
  878. * SECTOR_SIZE;
  879. } while (bi_iter.bi_size);
  880. bio_endio(bio);
  881. return DM_MAPIO_SUBMITTED;
  882. }
  883. static int remove_trim(struct bow_context *bc, struct bio *bio)
  884. {
  885. struct bow_range *br;
  886. struct bvec_iter bi_iter = bio->bi_iter;
  887. DMDEBUG("remove_trim: %llu, %u",
  888. (unsigned long long)bio->bi_iter.bi_sector,
  889. bio->bi_iter.bi_size);
  890. do {
  891. br = find_first_overlapping_range(&bc->ranges, &bi_iter);
  892. switch (br->type) {
  893. case UNCHANGED:
  894. /* Nothing to do */
  895. break;
  896. case TRIMMED:
  897. if (!split_range(bc, &br, &bi_iter))
  898. set_type(bc, &br, UNCHANGED);
  899. break;
  900. default:
  901. /* No other case is legal in TRIM state */
  902. WARN_ON(true);
  903. break;
  904. }
  905. bi_iter.bi_sector += bi_iter.bi_size / SECTOR_SIZE;
  906. bi_iter.bi_size = bio->bi_iter.bi_size
  907. - (bi_iter.bi_sector - bio->bi_iter.bi_sector)
  908. * SECTOR_SIZE;
  909. } while (bi_iter.bi_size);
  910. return DM_MAPIO_REMAPPED;
  911. }
  912. int remap_unless_illegal_trim(struct bow_context *bc, struct bio *bio)
  913. {
  914. if (!bc->forward_trims && bio_op(bio) == REQ_OP_DISCARD) {
  915. bio->bi_status = BLK_STS_NOTSUPP;
  916. bio_endio(bio);
  917. return DM_MAPIO_SUBMITTED;
  918. } else {
  919. bio_set_dev(bio, bc->dev->bdev);
  920. return DM_MAPIO_REMAPPED;
  921. }
  922. }
  923. /****** dm interface ******/
  924. static int dm_bow_map(struct dm_target *ti, struct bio *bio)
  925. {
  926. int ret = DM_MAPIO_REMAPPED;
  927. struct bow_context *bc = ti->private;
  928. if (likely(bc->state.counter == COMMITTED))
  929. return remap_unless_illegal_trim(bc, bio);
  930. if (bio_data_dir(bio) == READ && bio->bi_iter.bi_sector != 0)
  931. return remap_unless_illegal_trim(bc, bio);
  932. if (atomic_read(&bc->state) != COMMITTED) {
  933. enum state state;
  934. mutex_lock(&bc->ranges_lock);
  935. state = atomic_read(&bc->state);
  936. if (state == TRIM) {
  937. if (bio_op(bio) == REQ_OP_DISCARD)
  938. ret = add_trim(bc, bio);
  939. else if (bio_data_dir(bio) == WRITE)
  940. ret = remove_trim(bc, bio);
  941. else
  942. /* pass-through */;
  943. } else if (state == CHECKPOINT) {
  944. if (bio->bi_iter.bi_sector == 0)
  945. ret = handle_sector0(bc, bio);
  946. else if (bio_data_dir(bio) == WRITE)
  947. ret = queue_write(bc, bio);
  948. else
  949. /* pass-through */;
  950. } else {
  951. /* pass-through */
  952. }
  953. mutex_unlock(&bc->ranges_lock);
  954. }
  955. if (ret == DM_MAPIO_REMAPPED)
  956. return remap_unless_illegal_trim(bc, bio);
  957. return ret;
  958. }
  959. static void dm_bow_tablestatus(struct dm_target *ti, char *result,
  960. unsigned int maxlen)
  961. {
  962. char *end = result + maxlen;
  963. struct bow_context *bc = ti->private;
  964. struct rb_node *i;
  965. int trimmed_list_length = 0;
  966. int trimmed_range_count = 0;
  967. struct bow_range *br;
  968. if (maxlen == 0)
  969. return;
  970. result[0] = 0;
  971. list_for_each_entry(br, &bc->trimmed_list, trimmed_list)
  972. if (br->type == TRIMMED) {
  973. ++trimmed_list_length;
  974. } else {
  975. scnprintf(result, end - result,
  976. "ERROR: non-trimmed entry in trimmed_list");
  977. return;
  978. }
  979. if (!rb_first(&bc->ranges)) {
  980. scnprintf(result, end - result, "ERROR: Empty ranges");
  981. return;
  982. }
  983. if (container_of(rb_first(&bc->ranges), struct bow_range, node)
  984. ->sector) {
  985. scnprintf(result, end - result,
  986. "ERROR: First range does not start at sector 0");
  987. return;
  988. }
  989. mutex_lock(&bc->ranges_lock);
  990. for (i = rb_first(&bc->ranges); i; i = rb_next(i)) {
  991. struct bow_range *br = container_of(i, struct bow_range, node);
  992. result += scnprintf(result, end - result, "%s: %llu",
  993. readable_type[br->type],
  994. (unsigned long long)br->sector);
  995. if (result >= end)
  996. goto unlock;
  997. result += scnprintf(result, end - result, "\n");
  998. if (result >= end)
  999. goto unlock;
  1000. if (br->type == TRIMMED)
  1001. ++trimmed_range_count;
  1002. if (br->type == TOP) {
  1003. if (br->sector != ti->len) {
  1004. scnprintf(result, end - result,
  1005. "\nERROR: Top sector is incorrect");
  1006. }
  1007. if (&br->node != rb_last(&bc->ranges)) {
  1008. scnprintf(result, end - result,
  1009. "\nERROR: Top sector is not last");
  1010. }
  1011. break;
  1012. }
  1013. if (!rb_next(i)) {
  1014. scnprintf(result, end - result,
  1015. "\nERROR: Last range not of type TOP");
  1016. goto unlock;
  1017. }
  1018. if (br->sector > range_top(br)) {
  1019. scnprintf(result, end - result,
  1020. "\nERROR: sectors out of order");
  1021. goto unlock;
  1022. }
  1023. }
  1024. if (trimmed_range_count != trimmed_list_length)
  1025. scnprintf(result, end - result,
  1026. "\nERROR: not all trimmed ranges in trimmed list");
  1027. unlock:
  1028. mutex_unlock(&bc->ranges_lock);
  1029. }
  1030. static void dm_bow_status(struct dm_target *ti, status_type_t type,
  1031. unsigned int status_flags, char *result,
  1032. unsigned int maxlen)
  1033. {
  1034. switch (type) {
  1035. case STATUSTYPE_INFO:
  1036. if (maxlen)
  1037. result[0] = 0;
  1038. break;
  1039. case STATUSTYPE_TABLE:
  1040. dm_bow_tablestatus(ti, result, maxlen);
  1041. break;
  1042. }
  1043. }
  1044. int dm_bow_prepare_ioctl(struct dm_target *ti, struct block_device **bdev)
  1045. {
  1046. struct bow_context *bc = ti->private;
  1047. struct dm_dev *dev = bc->dev;
  1048. *bdev = dev->bdev;
  1049. /* Only pass ioctls through if the device sizes match exactly. */
  1050. return ti->len != i_size_read(dev->bdev->bd_inode) >> SECTOR_SHIFT;
  1051. }
  1052. static int dm_bow_iterate_devices(struct dm_target *ti,
  1053. iterate_devices_callout_fn fn, void *data)
  1054. {
  1055. struct bow_context *bc = ti->private;
  1056. return fn(ti, bc->dev, 0, ti->len, data);
  1057. }
  1058. static struct target_type bow_target = {
  1059. .name = "bow",
  1060. .version = {1, 2, 0},
  1061. .features = DM_TARGET_PASSES_CRYPTO,
  1062. .module = THIS_MODULE,
  1063. .ctr = dm_bow_ctr,
  1064. .dtr = dm_bow_dtr,
  1065. .map = dm_bow_map,
  1066. .status = dm_bow_status,
  1067. .prepare_ioctl = dm_bow_prepare_ioctl,
  1068. .iterate_devices = dm_bow_iterate_devices,
  1069. .io_hints = dm_bow_io_hints,
  1070. };
  1071. int __init dm_bow_init(void)
  1072. {
  1073. int r = dm_register_target(&bow_target);
  1074. if (r < 0)
  1075. DMERR("registering bow failed %d", r);
  1076. return r;
  1077. }
  1078. void dm_bow_exit(void)
  1079. {
  1080. dm_unregister_target(&bow_target);
  1081. }
  1082. MODULE_LICENSE("GPL");
  1083. module_init(dm_bow_init);
  1084. module_exit(dm_bow_exit);