The previous code would, to generate the nth value in the sequence,
generate a random integer, linearly search the already-generated values
for a duplicate, and repeat until a non-colliding number was found.
That's an average of ln(n) + 0.577 attempts per number output, each
attempt is O(n), and it takes O(n) numbers to fill the array, for a
total of O(n^2 * log n).
For large n, the linear search would dominate, but the excess calls
to get_random_bytes() are painful even with small n.
There were also other bizarre things in the code, like the fiddling with
the sign bit, and "j = 10001 - j" when j is a random 32-bit integer.
Replace with an O(n) Fisher-Yates shuffle, and use prandom_max()
rather than expensive crypto-grade random numbers.
In iscsit_randomize_pdu_lists, I even got rid of the temporary array
entirely and shuffled directly in the PDUs.
In iscsit_randomize_seq_lists(), the "seq_list[i].type == SEQTYPE_NORMAL"
condition makes it hard to shuffle in-place, and I didn't want to
dive too deep into the code, but perhaps someone else could.
Signed-off-by: George Spelvin <lkml@xxxxxxx>
Cc: Nicholas Bellinger <nab@xxxxxxxxxxxxxxx>
Cc: Lee Duncan <lduncan@xxxxxxxx>
Cc: Chris Leech <cleech@xxxxxxxxxx>
Cc: linux-scsi@xxxxxxxxxxxxxxx
---
.../target/iscsi/iscsi_target_seq_pdu_list.c | 72 +++++++------------
1 file changed, 24 insertions(+), 48 deletions(-)
diff --git a/drivers/target/iscsi/iscsi_target_seq_pdu_list.c b/drivers/target/iscsi/iscsi_target_seq_pdu_list.c
index ea2b02a93e455..bc40657d4c7d6 100644
--- a/drivers/target/iscsi/iscsi_target_seq_pdu_list.c
+++ b/drivers/target/iscsi/iscsi_target_seq_pdu_list.c
@@ -88,40 +88,40 @@ static void iscsit_ordered_pdu_lists(
}
/*
- * Generate count random values into array.
- * Use 0x80000000 to mark generates valued in array[].
+ * Generate an array holding the values 0..count-1 in random order.
+ * count is guaranteed non-zero.
*/
static void iscsit_create_random_array(u32 *array, u32 count)
{
- int i, j, k;
+ int i;
- if (count == 1) {
- array[0] = 0;
- return;
+ array[0] = 0;
+
+ for (i = 1; i < count; i++) {
+ int j = prandom_u32_max(i+1);
+ array[i] = array[j];
+ array[j] = i;
}
+}
- for (i = 0; i < count; i++) {
-redo:
- get_random_bytes(&j, sizeof(u32));
- j = (1 + (int) (9999 + 1) - j) % count;
- for (k = 0; k < i + 1; k++) {
- j |= 0x80000000;
- if ((array[k] & 0x80000000) && (array[k] == j))
- goto redo;
- }
- array[i] = j;
+/* A specialized version of the above for PDU send orders */
+static void iscsit_random_send_order(struct iscsi_pdu *pdu, u32 count)
+{
+ int i;
+
+ pdu[0].pdu_send_order = 0;
+ for (i = 1; i < count; i++) {
+ int j = prandom_u32_max(i+1);
+ pdu[i].pdu_send_order = pdu[j].pdu_send_order;
+ pdu[j].pdu_send_order = i;
}
-
- for (i = 0; i < count; i++)
- array[i] &= ~0x80000000;
}
static int iscsit_randomize_pdu_lists(
struct iscsi_cmd *cmd,
u8 type)
{
- int i = 0;
- u32 *array, pdu_count, seq_count = 0, seq_no = 0, seq_offset = 0;
+ u32 pdu_count, seq_count = 0, seq_no = 0, seq_offset = 0;
for (pdu_count = 0; pdu_count < cmd->pdu_count; pdu_count++) {
redo:
@@ -129,39 +129,15 @@ static int iscsit_randomize_pdu_lists(
seq_count++;
continue;
}
- array = kcalloc(seq_count, sizeof(u32), GFP_KERNEL);
- if (!array) {
- pr_err("Unable to allocate memory"
- " for random array.\n");
- return -ENOMEM;
- }
- iscsit_create_random_array(array, seq_count);
-
- for (i = 0; i < seq_count; i++)
- cmd->pdu_list[seq_offset+i].pdu_send_order = array[i];
-
- kfree(array);
-
+ iscsit_random_send_order(cmd->pdu_list + seq_offset, seq_count);
seq_offset += seq_count;
seq_count = 0;
seq_no++;
goto redo;
}
- if (seq_count) {
- array = kcalloc(seq_count, sizeof(u32), GFP_KERNEL);
- if (!array) {
- pr_err("Unable to allocate memory for"
- " random array.\n");
- return -ENOMEM;
- }
- iscsit_create_random_array(array, seq_count);
-
- for (i = 0; i < seq_count; i++)
- cmd->pdu_list[seq_offset+i].pdu_send_order = array[i];
-
- kfree(array);
- }
+ if (seq_count)
+ iscsit_random_send_order(cmd->pdu_list + seq_offset, seq_count);
return 0;
}
--
2.26.0
