diff options
Diffstat (limited to 'testing/sg_scat_gath.cpp')
| -rw-r--r-- | testing/sg_scat_gath.cpp | 1049 |
1 files changed, 1049 insertions, 0 deletions
diff --git a/testing/sg_scat_gath.cpp b/testing/sg_scat_gath.cpp new file mode 100644 index 00000000..56752718 --- /dev/null +++ b/testing/sg_scat_gath.cpp @@ -0,0 +1,1049 @@ +/* + * Copyright (c) 2014-2020 Douglas Gilbert. + * All rights reserved. + * Use of this source code is governed by a BSD-style + * license that can be found in the BSD_LICENSE file. + * + * SPDX-License-Identifier: BSD-2-Clause + * + * Version 1.02 [20201124] + */ + +// C headers +#include <stdio.h> +#include <stdint.h> +#include <string.h> +#include <limits.h> +#include <ctype.h> +#include <errno.h> +#define __STDC_FORMAT_MACROS 1 +#include <inttypes.h> + +// C++ headers +#include <array> + +#include "sg_scat_gath.h" +#include "sg_lib.h" +#include "sg_pr2serr.h" + +using namespace std; + +#define MAX_SGL_NUM_VAL (INT32_MAX - 1) /* should reduce for testing */ +// #define MAX_SGL_NUM_VAL 7 /* should reduce for testing */ +#if MAX_SGL_NUM_VAL > INT32_MAX +#error "MAX_SGL_NUM_VAL cannot exceed 2^31 - 1" +#endif + +bool +scat_gath_list::empty() const +{ + return sgl.empty(); +} + +bool +scat_gath_list::empty_or_00() const +{ + if (sgl.empty()) + return true; + return ((sgl.size() == 1) && (sgl[0].lba == 0) && (sgl[0].num == 0)); +} + +int +scat_gath_list::num_elems() const +{ + return sgl.size(); +} + + +/* Read numbers (up to 64 bits in size) from command line (comma (or + * (single) space **) separated list). Assumed decimal unless prefixed + * by '0x', '0X' or contains trailing 'h' or 'H' (which indicate hex). + * Returns 0 if ok, or 1 if error. Assumed to be LBA (64 bit) and + * number_of_block (32 bit) pairs. ** Space on command line needs to + * be escaped, otherwise it is an operand/option separator. */ +bool +scat_gath_list::load_from_cli(const char * cl_p, bool b_vb) +{ + bool split, full_pair; + int in_len, k, j; + const int max_nbs = MAX_SGL_NUM_VAL; + int64_t ll, large_num; + uint64_t prev_lba; + char * cp; + char * c2p; + const char * lcp; + class scat_gath_elem sge; + + if (NULL == cl_p) { + pr2serr("%s: bad arguments\n", __func__); + goto err_out; + } + lcp = cl_p; + in_len = strlen(cl_p); + if ('-' == cl_p[0]) { /* read from stdin */ + pr2serr("%s: logic error: no stdin here\n", __func__); + goto err_out; + } else { /* list of numbers (default decimal) on command line */ + k = strspn(cl_p, "0123456789aAbBcCdDeEfFhHxXiIkKmMgGtTpP, "); + if (in_len != k) { + if (b_vb) + pr2serr("%s: error at pos %d\n", __func__, k + 1); + goto err_out; + } + j = 0; + full_pair = true; + for (k = 0, split = false; ; ++k) { + if (split) { + /* splitting given elem with large number_of_blocks into + * multiple elems within array being built */ + ++j; + sge.lba = prev_lba + (uint64_t)max_nbs; + if (large_num > max_nbs) { + sge.num = (uint32_t)max_nbs; + prev_lba = sge.lba; + large_num -= max_nbs; + sgl.push_back(sge); + } else { + sge.num = (uint32_t)large_num; + split = false; + if (b_vb) + pr2serr("%s: split large sg elem into %d element%s\n", + __func__, j, (j == 1 ? "" : "s")); + sgl.push_back(sge); + goto check_for_next; + } + continue; + } + full_pair = false; + ll = sg_get_llnum(lcp); + if (-1 != ll) { + sge.lba = (uint64_t)ll; + cp = (char *)strchr(lcp, ','); + c2p = (char *)strchr(lcp, ' '); + if (NULL == cp) { + cp = c2p; + if (NULL == cp) + break; + } + if (c2p && (c2p < cp)) + cp = c2p; + lcp = cp + 1; + } else { + if (b_vb) + pr2serr("%s: error at pos %d\n", __func__, + (int)(lcp - cl_p + 1)); + goto err_out; + } + ll = sg_get_llnum(lcp); + if (ll >= 0) { + full_pair = true; + if (ll > max_nbs) { + sge.num = (uint32_t)max_nbs; + prev_lba = sge.lba; + large_num = ll - max_nbs; + split = true; + j = 1; + continue; + } + sge.num = (uint32_t)ll; + } else { /* bad or negative number as number_of_blocks */ + if (b_vb) + pr2serr("%s: bad number at pos %d\n", __func__, + (int)(lcp - cl_p + 1)); + goto err_out; + } + sgl.push_back(sge); +check_for_next: + cp = (char *)strchr(lcp, ','); + c2p = (char *)strchr(lcp, ' '); + if (NULL == cp) { + cp = c2p; + if (NULL == cp) + break; + } + if (c2p && (c2p < cp)) + cp = c2p; + lcp = cp + 1; + } /* end of for loop over items in operand */ + /* other than first pair, expect even number of items */ + if ((k > 0) && (! full_pair)) { + if (b_vb) + pr2serr("%s: expected even number of items: " + "LBA0,NUM0,LBA1,NUM1...\n", __func__); + goto err_out; + } + } + return true; +err_out: + if (0 == m_errno) + m_errno = SG_LIB_SYNTAX_ERROR; + return false; +} + +bool +scat_gath_list::file2sgl_helper(FILE * fp, const char * fnp, bool def_hex, + bool flexible, bool b_vb) +{ + bool bit0; + bool pre_addr1 = true; + bool pre_hex_seen = false; + int in_len, k, j, m, ind; + const int max_nbs = MAX_SGL_NUM_VAL; + int off = 0; + int64_t ll; + uint64_t ull, prev_lba; + char * lcp; + class scat_gath_elem sge; + char line[1024]; + + for (j = 0 ; ; ++j) { + if (NULL == fgets(line, sizeof(line), fp)) + break; + // could improve with carry_over logic if sizeof(line) too small + in_len = strlen(line); + if (in_len > 0) { + if ('\n' == line[in_len - 1]) { + --in_len; + line[in_len] = '\0'; + } else { + m_errno = SG_LIB_SYNTAX_ERROR; + if (b_vb) + pr2serr("%s: %s: line too long, max %d bytes\n", + __func__, fnp, (int)(sizeof(line) - 1)); + goto err_out; + } + } + if (in_len < 1) + continue; + lcp = line; + m = strspn(lcp, " \t"); + if (m == in_len) + continue; + lcp += m; + in_len -= m; + if ('#' == *lcp) + continue; + if (pre_addr1 || pre_hex_seen) { + /* Accept lines with leading 'HEX' and ignore as long as there + * is one _before_ any LBA,NUM lines in the file. This allows + * HEX marked sgls to be concaternated together. */ + if (('H' == toupper(lcp[0])) && ('E' == toupper(lcp[1])) && + ('X' == toupper(lcp[2]))) { + pre_hex_seen = true; + if (def_hex) + continue; /* bypass 'HEX' marker line if expecting hex */ + else { + if (flexible) { + def_hex = true; /* okay, switch to hex parse */ + continue; + } else { + pr2serr("%s: %s: 'hex' string detected on line %d, " + "expecting decimal\n", __func__, fnp, j + 1); + m_errno = EINVAL; + goto err_out; + } + } + } + } + k = strspn(lcp, "0123456789aAbBcCdDeEfFhHxXbBdDiIkKmMgGtTpP, \t"); + if ((k < in_len) && ('#' != lcp[k])) { + m_errno = EINVAL; + if (b_vb) + pr2serr("%s: %s: syntax error at line %d, pos %d\n", + __func__, fnp, j + 1, m + k + 1); + goto err_out; + } + for (k = 0; k < 256; ++k) { + /* limit parseable items on one line to 256 */ + if (def_hex) { /* don't accept negatives or multipliers */ + if (1 == sscanf(lcp, "%" SCNx64, &ull)) + ll = (int64_t)ull; + else + ll = -1; /* use (2**64 - 1) as error flag */ + } else + ll = sg_get_llnum(lcp); + if (-1 != ll) { + ind = ((off + k) >> 1); + bit0 = !! (0x1 & (off + k)); + if (ind >= SG_SGL_MAX_ELEMENTS) { + m_errno = EINVAL; + if (b_vb) + pr2serr("%s: %s: array length exceeded\n", __func__, + fnp); + goto err_out; + } + if (bit0) { /* bit0 set when decoding a NUM */ + if (ll < 0) { + m_errno = EINVAL; + if (b_vb) + pr2serr("%s: %s: bad number in line %d, at pos " + "%d\n", __func__, fnp, j + 1, + (int)(lcp - line + 1)); + goto err_out; + } + if (ll > max_nbs) { + int h = 1; + + /* split up this elem into multiple, smaller elems */ + do { + sge.num = (uint32_t)max_nbs; + prev_lba = sge.lba; + sgl.push_back(sge); + sge.lba = prev_lba + (uint64_t)max_nbs; + ++h; + off += 2; + ll -= max_nbs; + } while (ll > max_nbs); + if (b_vb) + pr2serr("%s: split large sg elem into %d " + "elements\n", __func__, h); + } + sge.num = (uint32_t)ll; + sgl.push_back(sge); + } else { /* bit0 clear when decoding a LBA */ + if (pre_addr1) + pre_addr1 = false; + sge.lba = (uint64_t)ll; + } + } else { /* failed to decode number on line */ + if ('#' == *lcp) { /* numbers before #, rest of line comment */ + --k; + break; /* goes to next line */ + } + m_errno = EINVAL; + if (b_vb) + pr2serr("%s: %s: error in line %d, at pos %d\n", + __func__, fnp, j + 1, (int)(lcp - line + 1)); + goto err_out; + } + lcp = strpbrk(lcp, " ,\t#"); + if ((NULL == lcp) || ('#' == *lcp)) + break; + lcp += strspn(lcp, " ,\t"); + if ('\0' == *lcp) + break; + } /* <<< end of for(k < 256) loop */ + off += (k + 1); + } /* <<< end of for loop, one iteration per line */ + /* allow one items, but not higher odd number of items */ + if ((off > 1) && (0x1 & off)) { + m_errno = EINVAL; + if (b_vb) + pr2serr("%s: %s: expect even number of items: " + "LBA0,NUM0,LBA1,NUM1...\n", __func__, fnp); + goto err_out; + } + clearerr(fp); /* even EOF on first pass needs this before rescan */ + return true; +err_out: + clearerr(fp); + return false; +} + +/* Read numbers from filename (or stdin), line by line (comma (or (single) + * space) separated list); places starting_LBA,number_of_block pairs in an + * array of scat_gath_elem elements pointed to by the returned value. If + * this fails NULL is returned and an error number is written to errp (if it + * is non-NULL). Assumed decimal (and may have suffix multipliers) when + * def_hex==false; if a number is prefixed by '0x', '0X' or contains trailing + * 'h' or 'H' that denotes a hex number. When def_hex==true all numbers are + * assumed to be hex (ignored '0x' prefixes and 'h' suffixes) and multipliers + * are not permitted. Heap allocates an array just big enough to hold all + * elements if the file is countable. Pipes and stdin are not considered + * countable. In the non-countable case an array of MAX_FIXED_SGL_ELEMS + * elements is pre-allocated; if it is exceeded sg_convert_errno(EDOM) is + * placed in *errp (if it is non-NULL). One of the first actions is to write + * 0 to *errp (if it is non-NULL) so the caller does not need to zero it + * before calling. */ +bool +scat_gath_list::load_from_file(const char * file_name, bool def_hex, + bool flexible, bool b_vb) +{ + bool have_stdin; + bool have_err = false; + FILE * fp; + const char * fnp; + + have_stdin = ((1 == strlen(file_name)) && ('-' == file_name[0])); + if (have_stdin) { + fp = stdin; + fnp = "<stdin>"; + } else { + fnp = file_name; + fp = fopen(fnp, "r"); + if (NULL == fp) { + m_errno = errno; + if (b_vb) + pr2serr("%s: opening %s: %s\n", __func__, fnp, + safe_strerror(m_errno)); + return false; + } + } + if (! file2sgl_helper(fp, fnp, def_hex, flexible, b_vb)) + have_err = true; + if (! have_stdin) + fclose(fp); + return have_err ? false : true; +} + +const char * +scat_gath_list::linearity_as_str() const +{ + switch (linearity) { + case SGL_LINEAR: + return "linear"; + case SGL_MONOTONIC: + return "monotonic"; + case SGL_MONO_OVERLAP: + return "monotonic, overlapping"; + case SGL_NON_MONOTONIC: + return "non-monotonic"; + default: + return "unknown"; + } +} + +void +scat_gath_list::set_weaker_linearity(enum sgl_linearity_e lin) +{ + int i_lin = (int)lin; + + if (i_lin > (int)linearity) + linearity = lin; +} + +/* id_str may be NULL (if so replace by "unknown"), present to enhance verbose + * output. */ +void +scat_gath_list::dbg_print(bool skip_meta, const char * id_str, bool to_stdout, + bool show_sgl) const +{ + int num = sgl.size(); + const char * caller = id_str ? id_str : "unknown"; + FILE * fp = to_stdout ? stdout : stderr; + + if (! skip_meta) { + fprintf(fp, "%s: elems=%d, sgl %spresent, linearity=%s\n", + caller, num, (sgl.empty() ? "not " : ""), + linearity_as_str()); + fprintf(fp, " sum=%" PRId64 ", sum_hard=%s lowest=0x%" PRIx64 + ", high_lba_p1=", sum, (sum_hard ? "true" : "false"), + lowest_lba); + fprintf(fp, "0x%" PRIx64 "\n", high_lba_p1); + } + fprintf(fp, " >> %s scatter gather list (%d element%s):\n", caller, num, + (num == 1 ? "" : "s")); + if (show_sgl) { + int k; + + for (k = 0; k < num; ++k) { + const class scat_gath_elem & sge = sgl[k]; + + fprintf(fp, " lba: 0x%" PRIx64 ", number: 0x%" PRIx32, + sge.lba, sge.num); + if (sge.lba > 0) + fprintf(fp, " [next lba: 0x%" PRIx64 "]", sge.lba + sge.num); + fprintf(fp, "\n"); + } + } +} + +/* Assumes sgl array (vector) is setup. The other fields in this object are + * set by analyzing sgl in a single pass. The fields that are set are: + * fragmented, lowest_lba, high_lba_p1, monotonic, overlapping, sum and + * sum_hard. Degenerate elements (i.e. those with 0 blocks) are ignored apart + * from when one is last which makes sum_hard false and its LBA becomes + * high_lba_p1 if it is the highest in the list. An empty sgl is equivalent + * to a 1 element list with [0, 0], so sum_hard==false, monit==true, + * fragmented==false and overlapping==false . id_str may be NULL, present + * to enhance verbose output. */ +void +scat_gath_list::sum_scan(const char * id_str, bool show_sgl, bool b_vb) +{ + bool degen = false; + bool first = true; + bool regular = true; /* no overlapping segments detected */ + int k; + int elems = sgl.size(); + uint32_t prev_num, t_num; + uint64_t prev_lba, t_lba, low, high, end; + + sum = 0; + for (k = 0, low = 0, high = 0; k < elems; ++k) { + const class scat_gath_elem & sge = sgl[k]; + + degen = false; + t_num = sge.num; + if (0 == t_num) { + degen = true; + if (! first) + continue; /* ignore degen element that not first */ + } + if (first) { + low = sge.lba; + sum = t_num; + high = sge.lba + sge.num; + first = false; + } else { + t_lba = sge.lba; + if ((prev_lba + prev_num) != t_lba) + set_weaker_linearity(SGL_MONOTONIC); + sum += t_num; + end = t_lba + t_num; + if (end > high) + high = end; /* high is one plus highest LBA */ + if (prev_lba < t_lba) + ; + else if (prev_lba == t_lba) { + if (prev_num > 0) { + set_weaker_linearity(SGL_MONO_OVERLAP); + break; + } + } else { + low = t_lba; + set_weaker_linearity(SGL_NON_MONOTONIC); + break; + } + if (regular) { + if ((prev_lba + prev_num) > t_lba) + regular = false; + } + } + prev_lba = sge.lba; + prev_num = sge.num; + } /* end of for loop while still elements and monot true */ + + if (k < elems) { /* only here if above breaks are taken */ + prev_lba = t_lba; + ++k; + for ( ; k < elems; ++k) { + const class scat_gath_elem & sge = sgl[k]; + + degen = false; + t_lba = sge.lba; + t_num = sge.num; + if (0 == t_num) { + degen = true; + continue; + } + sum += t_num; + end = t_lba + t_num; + if (end > high) + high = end; + if (prev_lba > t_lba) { + if (t_lba < low) + low = t_lba; + } + prev_lba = t_lba; + } + } else + if (! regular) + set_weaker_linearity(SGL_MONO_OVERLAP); + + lowest_lba = low; + if (degen && (elems > 0)) { /* last element always impacts high_lba_p1 */ + t_lba = sgl[elems - 1].lba; + high_lba_p1 = (t_lba > high) ? t_lba : high; + } else + high_lba_p1 = high; + sum_hard = (elems > 0) ? ! degen : false; + if (b_vb) + dbg_print(false, id_str, false, show_sgl); +} + +/* Usually will append (or add to start if empty) sge unless 'extra_blks' + * exceeds MAX_SGL_NUM_VAL. In that case multiple sge_s are added with + * sge.num = MAX_SGL_NUM_VAL or less (for final sge) until extra_blks is + * exhausted. Returns new size of scatter gather list. */ +int +scat_gath_list::append_1or(int64_t extra_blks, int64_t start_lba) +{ + int o_num = sgl.size(); + const int max_nbs = MAX_SGL_NUM_VAL; + int64_t cnt = 0; + class scat_gath_elem sge; + + if ((extra_blks <= 0) && (start_lba < 0)) + return o_num; /* nothing to do */ + if ((o_num > 0) && (! sum_hard)) { + sge = sgl[o_num - 1]; /* assume sge.num==0 */ + if (sge.lba == (uint64_t)start_lba) { + if (extra_blks <= max_nbs) + sge.num = extra_blks; + else + sge.num = max_nbs; + sgl[o_num - 1] = sge; + cnt = sge.num; + sum += cnt; + sum_hard = true; + if (cnt <= extra_blks) { + high_lba_p1 = sge.lba + cnt; + return o_num; + } + } + } else if (0 == o_num) { + lowest_lba = start_lba; + if (0 == extra_blks) { + sge.lba = start_lba; + sge.num = 0; + sgl.push_back(sge); + high_lba_p1 = sge.lba; + return sgl.size(); + } + } + for ( ; cnt < extra_blks; cnt += max_nbs) { + sge.lba = start_lba + cnt; + if ((extra_blks - cnt) <= max_nbs) + sge.num = extra_blks - cnt; + else + sge.num = max_nbs; + sgl.push_back(sge); + sum += sge.num; + } /* always loops at least once */ + sum_hard = true; + high_lba_p1 = sge.lba + sge.num; + return sgl.size(); +} + +int +scat_gath_list::append_1or(int64_t extra_blks) +{ + int o_num = sgl.size(); + + if (o_num < 1) + return append_1or(extra_blks, 0); + + class scat_gath_elem sge = sgl[o_num - 1]; + + return append_1or(extra_blks, sge.lba + sge.num); +} + +bool +sgls_eq_off(const scat_gath_list & left, int l_e_ind, int l_blk_off, + const scat_gath_list & right, int r_e_ind, int r_blk_off, + bool allow_partial) +{ + int lelems = left.sgl.size(); + int relems = right.sgl.size(); + + while ((l_e_ind < lelems) && (r_e_ind < relems)) { + if ((left.sgl[l_e_ind].lba + l_blk_off) != + (right.sgl[r_e_ind].lba + r_blk_off)) + return false; + + int lrem = left.sgl[l_e_ind].num - l_blk_off; + int rrem = right.sgl[r_e_ind].num - r_blk_off; + + if (lrem == rrem) { + ++l_e_ind; + l_blk_off = 0; + ++r_e_ind; + r_blk_off = 0; + } else if (lrem < rrem) { + ++l_e_ind; + l_blk_off = 0; + r_blk_off += lrem; + } else { + ++r_e_ind; + r_blk_off = 0; + l_blk_off += rrem; + } + } + if ((l_e_ind >= lelems) && (r_e_ind >= relems)) + return true; + return allow_partial; +} + +/* If bad arguments returns -1, otherwise returns the lowest LBA in *sglp . + * If no elements considered returns 0. If ignore_degen is true than + * ignores all elements with sge.num zero unless always_last is also + * true in which case the last element is always considered. */ +int64_t +scat_gath_list::get_lowest_lba(bool ignore_degen, bool always_last) const +{ + int k; + const int num_elems = sgl.size(); + bool some = (num_elems > 0); + int64_t res = INT64_MAX; + + for (k = 0; k < num_elems; ++k) { + if ((0 == sgl[k].num) && ignore_degen) + continue; + if ((int64_t)sgl[k].lba < res) + res = sgl[k].lba; + } + if (always_last && some) { + if ((int64_t)sgl[k - 1].lba < res) + res = sgl[k - 1].lba; + } + return (INT64_MAX == res) ? 0 : res; +} + +/* Returns >= 0 if sgl can be simplified to a single LBA. So an empty sgl + * will return 0; a one element sgl will return its LBA. A multiple element + * sgl only returns the first element's LBA (that is not degenerate) if the + * sgl is monotonic and not fragmented. In the extreme case takes last + * element's LBA if all prior elements are degenerate. Else returns -1 . + * Assumes sgl_sum_scan() has been called. */ +int64_t +scat_gath_list::get_low_lba_from_linear() const +{ + const int num_elems = sgl.size(); + int k; + + if (num_elems <= 1) + return (1 == num_elems) ? sgl[0].lba : 0; + else { + if (linearity == SGL_LINEAR) { + for (k = 0; k < (num_elems - 1); ++k) { + if (sgl[k].num > 0) + return sgl[k].lba; + } + /* take last element's LBA if all earlier are degenerate */ + return sgl[k].lba; + } else + return -1; + } +} + +bool +scat_gath_list::is_pipe_suitable() const +{ + return (lowest_lba == 0) && (linearity == SGL_LINEAR); +} + +scat_gath_iter::scat_gath_iter(const scat_gath_list & parent) + : sglist(parent), it_el_ind(0), it_blk_off(0), blk_idx(0) +{ + int elems = sglist.num_elems(); + + if (elems > 0) + extend_last = (0 == sglist.sgl[elems - 1].num); +} + +bool +scat_gath_iter::set_by_blk_idx(int64_t _blk_idx) +{ + bool first; + int k; + const int elems = sglist.sgl.size(); + const int last_ind = elems - 1; + int64_t bc = _blk_idx; + + if (bc < 0) + return false; + + if (bc == blk_idx) + return true; + else if (bc > blk_idx) { + k = it_el_ind; + bc -= blk_idx; + } else + k = 0; + for (first = true; k < elems; ++k, first = false) { + uint32_t num = ((k == last_ind) && extend_last) ? MAX_SGL_NUM_VAL : + sglist.sgl[k].num; + if (first) { + if ((int64_t)(num - it_blk_off) < bc) + bc -= (num - it_blk_off); + else { + it_blk_off = bc + it_blk_off; + break; + } + } else { + if ((int64_t)num < bc) + bc -= num; + else { + it_blk_off = (uint32_t)bc; + break; + } + } + } + it_el_ind = k; + blk_idx = _blk_idx; + + if (k < elems) + return true; + else if ((k == elems) && (0 == it_blk_off)) + return true; /* EOL */ + else + return false; +} + +/* Given a blk_count, the iterator (*iter_p) is moved toward the EOL. + * Returns true unless blk_count takes iterator two or more past the last + * element. So if blk_count takes the iterator to the EOL, this function + * returns true. Takes into account iterator's extend_last flag. */ +bool +scat_gath_iter::add_blks(uint64_t blk_count) +{ + bool first; + int k; + const int elems = sglist.sgl.size(); + const int last_ind = elems - 1; + uint64_t bc = blk_count; + + if (0 == bc) + return true; + for (first = true, k = it_el_ind; k < elems; ++k) { + uint32_t num = ((k == last_ind) && extend_last) ? MAX_SGL_NUM_VAL : + sglist.sgl[k].num; + if (first) { + first = false; + if ((uint64_t)(num - it_blk_off) <= bc) + bc -= (num - it_blk_off); + else { + it_blk_off = bc + it_blk_off; + break; + } + } else { + if ((uint64_t)num <= bc) + bc -= num; + else { + it_blk_off = (uint32_t)bc; + break; + } + } + } + it_el_ind = k; + blk_idx += blk_count; + + if (k < elems) + return true; + else if ((k == elems) && (0 == it_blk_off)) + return true; /* EOL */ + else + return false; +} + +/* Move the iterator from its current position (which may be to EOL) towards + * the start of the sgl (i.e. backwards) for blk_count blocks. Returns true + * if iterator is valid after the move, else returns false. N.B. if false is + * returned, then the iterator is invalid and may need to set it to a valid + * value. */ +bool +scat_gath_iter::sub_blks(uint64_t blk_count) +{ + bool first; + int k = it_el_ind; + uint64_t bc = 0; + const uint64_t orig_blk_count = blk_count; + + if (0 == blk_count) + return true; + for (first = true; k >= 0; --k) { + if (first) { + if (blk_count > (uint64_t)it_blk_off) + blk_count -= it_blk_off; + else { + it_blk_off -= blk_count; + break; + } + first = false; + } else { + uint32_t off = sglist.sgl[k].num; + + bc = blk_count; + if (bc > (uint64_t)off) + blk_count -= off; + else { + bc = off - bc; + break; + } + } + } + if (k < 0) { + blk_idx = 0; + it_blk_off = 0; + return false; /* bad situation */ + } + if ((int64_t)orig_blk_count <= blk_idx) + blk_idx -= orig_blk_count; + else + blk_idx = 0; + it_el_ind = k; + if (! first) + it_blk_off = (uint32_t)bc; + return true; +} + +/* Returns LBA referred to by iterator if valid or returns SG_LBA_INVALID + * (-1) if at end or invalid. */ +int64_t +scat_gath_iter::current_lba() const +{ + const int elems = sglist.sgl.size(); + int64_t res = SG_LBA_INVALID; /* for at end or invalid (-1) */ + + if (it_el_ind < elems) { + class scat_gath_elem sge = sglist.sgl[it_el_ind]; + + if ((uint32_t)it_blk_off < sge.num) + return sge.lba + it_blk_off; + else if (((uint32_t)it_blk_off == sge.num) && + ((it_el_ind + 1) < elems)) { + class scat_gath_iter iter(*this); + + ++iter.it_el_ind; + iter.it_blk_off = 0; + /* worst case recursion will stop at end of sgl */ + return iter.current_lba(); + } + } + return res; +} + +int64_t +scat_gath_iter::current_lba_rem_num(int & rem_num) const +{ + const int elems = sglist.sgl.size(); + int64_t res = SG_LBA_INVALID; /* for at end or invalid (-1) */ + + if (it_el_ind < elems) { + class scat_gath_elem sge = sglist.sgl[it_el_ind]; + + if ((uint32_t)it_blk_off < sge.num) { + rem_num = sge.num - it_blk_off; + return sge.lba + it_blk_off; + } else if (((uint32_t)it_blk_off == sge.num) && + ((it_el_ind + 1) < elems)) { + class scat_gath_iter iter(*this); + + ++iter.it_el_ind; + iter.it_blk_off = 0; + /* worst case recursion will stop at end of sgl */ + return iter.current_lba_rem_num(rem_num); + } + } + rem_num = -1; + return res; +} + +class scat_gath_elem +scat_gath_iter::current_elem() const +{ + const int elems = sglist.sgl.size(); + class scat_gath_elem sge; + + sge.make_bad(); + if (it_el_ind < elems) + return sglist.sgl[it_el_ind]; + return sge; +} + +/* Returns true of no sgl or sgl is at the end [elems, 0], otherwise it + * returns false. */ +bool +scat_gath_iter::at_end() const +{ + const int elems = sglist.sgl.size(); + + return ((0 == elems) || ((it_el_ind == elems) && (0 == it_blk_off))); +} + +/* Returns true if associated iterator is monotonic (increasing) and not + * fragmented. Empty sgl and single element degenerate considered linear. + * Assumes sgl_sum_scan() has been called on sgl. */ +bool +scat_gath_iter::is_sgl_linear() const +{ + return sglist.linearity == SGL_LINEAR; +} + +/* Should return 1 or more unless max_n<=0 or at_end() */ +int +scat_gath_iter::linear_for_n_blks(int max_n) const +{ + int k, rem; + const int elems = sglist.sgl.size(); + uint64_t prev_lba; + class scat_gath_elem sge; + + if (at_end() || (max_n <= 0)) + return 0; + sge = sglist.sgl[it_el_ind]; + rem = (int)sge.num - it_blk_off; + if (rem <= 0) { + sge = sglist.sgl[it_el_ind + 1]; + rem = (int)sge.num; + } + if (max_n <= rem) + return max_n; + prev_lba = sge.lba + sge.num; + for (k = it_el_ind + 1; k < elems; ++k) { + sge = sglist.sgl[k]; + if (sge.lba != prev_lba) + return rem; + rem += sge.num; + if (max_n <= rem) + return max_n; + prev_lba = sge.lba + sge.num; + } + return rem; +} + +/* id_str may be NULL (if so replace by "unknown"), present to enhance verbose + * output. */ +void +scat_gath_iter::dbg_print(const char * id_str, bool to_stdout, + int verbose) const +{ + const char * caller = id_str ? id_str : "unknown"; + FILE * fp = to_stdout ? stdout : stderr; + + fprintf(fp, "%s: it_el_ind=%d, it_blk_off=%d, blk_idx=%" PRId64 "\n", + caller, it_el_ind, it_blk_off, blk_idx); + fprintf(fp, " extend_last=%d\n", extend_last); + if (verbose) + sglist.dbg_print(false, " iterator's", to_stdout, verbose > 1); +} + +/* Calculates difference between iterators, logically: res <-- lhs - rhs + * Checks that lhsp and rhsp have same underlying sgl, if not returns + * INT_MIN. Assumes iterators close enough for result to lie in range + * from (-INT_MAX) to INT_MAX (inclusive). */ +int +diff_between_iters(const class scat_gath_iter & left, + const class scat_gath_iter & right) +{ + int res, k, r_e_ind, l_e_ind; + + if (&left.sglist != &right.sglist) { + pr2serr("%s: bad args\n", __func__); + return INT_MIN; + } + r_e_ind = right.it_el_ind; + l_e_ind = left.it_el_ind; + if (l_e_ind < r_e_ind) { /* so difference will be negative */ + res = diff_between_iters(right, left); /* cheat */ + if (INT_MIN == res) + return res; + return -res; + } else if (l_e_ind == r_e_ind) + return (int)left.it_blk_off - (int)right.it_blk_off; + /* (l_e_ind > r_e_ind) so (lhs > rhs) */ + res = (int)right.sglist.sgl[r_e_ind].num - right.it_blk_off; + for (k = 1; (r_e_ind + k) < l_e_ind; ++k) { + // pr2serr("%s: k=%d, res=%d, num=%d\n", __func__, k, res, + // (int)right.sglist.sgl[r_e_ind + k].num); + res += (int)right.sglist.sgl[r_e_ind + k].num; + } + res += left.it_blk_off; + // pr2serr("%s: at exit res=%d\n", __func__, res); + return res; +} + +/* Compares from the current iterator positions of left and left until + * the shorter list is exhausted. Returns false on the first inequality. + * If no inequality and both remaining lists are same length then returns + * true. If no inequality but remaining lists differ in length then returns + * allow_partial. */ +bool +sgls_eq_from_iters(const class scat_gath_iter & left, + const class scat_gath_iter & right, + bool allow_partial) +{ + return sgls_eq_off(left.sglist, left.it_el_ind, left.it_blk_off, + right.sglist, right.it_el_ind, right.it_blk_off, + allow_partial); +} |