On Thursday, 7 September 2023 03:09:07 CEST Linus Lüssing wrote: [...]
Changelog v7:
- PATCH 1/3:
- rebased to current main/master branch (resolved net/multicast/routing.h)
Are you trying to take over batman-adv and make it the *multicast* mesh protocol? :D
- renamed batadv_mcast_forw_orig_to_neigh() to batadv_orig_to_router() and moved it to originator.c, for reuse in fragmentation.c
For this, you should also remove routing.h from fragmentation.c in patch 1. Same for multicast_forw.c
I have already queued it up in linux-merge with these changes
- PATCH 3/3:
@Simon, can you please also check the remaining code changes? To quickly identify modifications, you can use
pipx install b4 # in you batman-adv repo b4 diff -- 20230907010910.22427-2-linus.luessing@c0d3.blue
- simplified batadv_mcast_forw_shrink_pack_dests(): moved parts to new sub function batadv_mcast_forw_shrink_fill(), removed keeping track of filler over the whole function (might be slower, as we might check+skip the same zero MAC entry multiple times, for each slot, but a lot easier to read - and we don't prioritize performance with this patchset yet)
Independent of the outcome for this patchset, something like this would often be implemented by starting the search on one side of an array and get the replacement from the other side of the array - and when start and end overlap then the algorithm stops. At least for me, it is easier to comprehend than some filler which needs to be pushed forward and is influenced by a variable which is (unexpectedly) modified inside a macro:
#! /usr/bin/env python3
from random import randint
# initialize test array def random_array(): slots = [] for i in range(100): slots.append(randint(0, 5))
return slots
# searches from the end towards the empty slot for fillers (non-zero) # # returns a non-zero entry if return value > empty_slot def find_filler(slots, empty_slot, end): while end > empty_slot: if slots[end] != 0: break
end -= 1
return end
# searches from the front for empty entries and replaces them with # non-empty entries from the end # # returns number of non-empty entries def move_empty_to_end(slots): non_empty = 0 start = 0 length = len(slots) end = length - 1
# replace empty entries at the beginning with non-empty from end while start < end: # ignore non-empty entries at the start if slots[start] != 0: start += 1 non_empty += 1 continue
# find replacement at end new_end = find_filler(slots, start, end) if new_end <= start: # no replacement found break
# move non-empty entry from end to start slots[start] = slots[new_end] end = new_end - 1 slots[new_end] = 0
# count remaining non-empty for i in range(start, length): if slots[i] == 0: break
non_empty += 1
return non_empty
slots = random_array() count_non_empty = move_empty_to_end(slots)
# just to make sure that everything is empty print(slots[count_non_empty:])
# memmove simulator :) slots = slots[:count_non_empty]
# just to see the non-empty entries print(slots)
While the natural way would actually be to move non-empty entries to the end (and then only move the header), your implementation needs them at the start. So I did it similar in this PoC.
Kind regards, Sven