[v7,0/3] Implementation of a Stateless Multicast Packet Type

  In-Reply-To: 

Hi,

The following patchset implements a stateless, TVLV capable batman-adv
multicast packet type.

The new batman-adv multicast packet type allows to contain several
originator destination MAC addresses within a TVLV. Routers on the way will
potentially split the batman-adv multicast packet and adjust its tracker
TVLV contents.

Routing decisions are still based on the selected BATMAN IV or BATMAN V
routing algorithm. So this new batman-adv multicast packet type retains
the same loop-free properties.

The purpose of this new packet type is to allow to forward an IP
multicast packet with less transmissions / overhead than the 
multicast-via-multiple-unicasts approach. Or to reach a lot more
destinations (currently up to 196, depending on the payload size, see 
Wiki documentation for details) than with the default multicast fanout
for the via-unicasts approach.

This will allow using applications like mDNS again in several Freifunk
communities. And with less transmissions will also make more bulky
multicast applications, like media streaming (to an assessable amount of
receivers) a lot more feasible.

This approach is way simpler than the original multicast (tracker) packet
approach we envisioned years ago. As it involves no maintenance of an
extra, state based multicast routing table. However the TVLV capability
should allow to extend things later, to split control and data plane a bit
more for instance, to further increase the number of destinations, to
further reduce overhead.

A compact overview can be found in the Wiki here, including limitations:

https://www.open-mesh.org/projects/batman-adv/wiki/Multicast-Packet-Type

Regards, Linus

---

Changelog v7:
* PATCH 1/3:
  * rebased to current main/master branch (resolved net/multicast/routing.h)
  * renamed batadv_mcast_forw_orig_to_neigh() to
    batadv_orig_to_router() and moved it to originator.c, for
    reuse in fragmentation.c
  * added a SKB_LINEAR_ASSERT() to batadv_mcast_forw_packet()
  * adjusted batadv_mcast_forw_scrub_dests():
    added a new macro that updates two dest pointers
    to avoid confusion due to two different updating methods,
    removed goto's and a little reordering
* PATCH 2/3:
  * added SKB_LINEAR_ASSERT() to batadv_mcast_forw_scrape()
* PATCH 3/3:
  * 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)

Changelog v6:
* PATCH 2/3:
  * add missing include of linux/compiler.h for the newly added
    likely() in v5
  * added kerneldoc for @num_dests_pushed to
    the in v5 newly added batadv_mcast_forw_push_adjust_padding()
  * updated kerneldoc of batadv_mcast_forw_push_adjust_padding(),
    original text was wrongly copy & pasted from
    batadv_mcast_forw_push_est_padding() without adjustments
* PATCH 3/3:
  * added missing "static" attribute to the newly added
    batadv_mcast_forw_shrink_align_offset() in v5

Changelog v5:
* removed patches 1/5 + 2/5, as they were already applied
* rebased to current main branch
* changed padding behaviour:
  * now 2 bytes padding on the end of the multicast
    tracker TVLV, if number of destination nodes is
    even
  * as number of destination nodes might change between
    initial check until after pushing them, functions
    to post-adjust padding after pushing were added
* added/fixed TTL handling
* removed skb_pull() bailing from sub-functions of
  batadv_mcast_forw_push(), to only have a single
  skb_pull() to keep track of in batadv_mcast_forw_push()
  to revert the changes to the skb; instead a
  "unsigned short *tvlv_len" is passsed along in 
  batadv_mcast_.*push.*() functions to keep track of
  how many bytes were pushed
* moved + verified skb->ip_summed invalidation
* batadv_mcast_forw_shrink_tracker() xmas tree ordering
* reword batadv_mcast_forw_push_dest() "Return:" kerneldoc
* fixed spelling: outter -> outer

Changelog v4:
* PATCH 4/5:
  * add missing include for linux/types.h in multicast.h
  * add missing kerneldoc for @bat_priv in batadv_mcast_forw_push_dest()
    and batadv_mcast_forw_push_tvlvs()
  * use sizeof_field(type, field) instead of sizeof(((type *)0)->field)
    in batadv_mcast_forw_push_dest()
* PATCH 5/5:
  * rename num_dests_remove to num_dests_reduce in
    batadv_mcast_forw_shrink_align_offse() to fix kerneldocs and for
    consistency
  * fix typo in kerneldoc in batadv_mcast_forw_shrink_update_headers()
    -> @num_dest_reduce -> @num_dests_reduce
  * use sizeof_field(type, field) instead of sizeof(((type *)0)->field)
    in batadv_mcast_forw_shrink_align_offset()

Changelog v3:
* PATCH 1/5:
  * remove now obsolete includes
* PATCH 2/5:
  * fix batadv_tvlv_handler_register() in network-coding.c
  * add missing include for linux/skbuff.h
  * move variable declarations out of the switch case
    in batadv_tvlv_call_handler()
* PATCH 3/5:
  * remove unnecessary include of multicast.h in routing.c
  * add a few missing includes to multicast_forw.c
    (linux/byteorder/generic.h, linux/errno.h, linux/gfp.h, linux/stddef.h
     uapi/linux/batadv_packet.h, multicast.h)
* PATCH 4/5:
  * add missing rcu_read_unlock() in error case before returning in
    batadv_mcast_forw_push_dests_list()
  * remove unnecessary include of soft-interface.h in multicast_forw.c
  * add a few missing includes to multicast_forw.c
    (linux/bug.h, linux/build_bug.h, linux/limits.h, linux/rculist.h,
     linux/rcupdate.h, linux/string.h)
  * make batadv_mcast_forw_mode_by_count() static
  * fix return types in the declaration of
    batadv_mcast_forw_packet_hdrlen() and batadv_mcast_forw_push()
    in multicast.h
  * fix typo in commit message: "that the are capable of"
    -> "that the*y* are capable of"
* PATCH 5/5:
  * make batadv_mcast_forw_shrink_pack_dests() adhere to 80 characters
    per line for consistency
  * add a "continue" statement after the jump label in
    batadv_mcast_forw_shrink_pack_dests() to silence the sparse error
    "error: label at end of compound statement"

Changelog v2:
* Add "[PATCH v2 0/5]" prefix to title of cover letter, so that
  Patchwork can hopefully find it - no other changes
  

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
  

On Sunday, September 24, 2023 12:47:34 PM CET Sven Eckelmann wrote:
> @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

Sorry for the delay, this actually slipped through the cracks on my end ... 
thanks Sven for reminding.

I've checked especially against the points I raised last time. I think 
batadv_mcast_forw_shrink_pack_dests() looks much better now. 
batadv_mcast_forw_scrub_dests() is still quite hard to comprehend, but better 
than before - and good enough to be adopted in my opinion. We'll make sure to 
direct bug reports from that to Linus in any case. ;)

So I'd give for this series:

Acked-by: Simon Wunderlich <sw@simonwunderlich.de>

Thank you!
       Simon
  

On Thursday, 7 September 2023 03:09:07 CET Linus Lüssing wrote:
[...]
> Changelog v7:
> * PATCH 1/3:
>   * rebased to current main/master branch (resolved net/multicast/routing.h)
>   * renamed batadv_mcast_forw_orig_to_neigh() to
>     batadv_orig_to_router() and moved it to originator.c, for
>     reuse in fragmentation.c
>   * added a SKB_LINEAR_ASSERT() to batadv_mcast_forw_packet()
>   * adjusted batadv_mcast_forw_scrub_dests():
>     added a new macro that updates two dest pointers
>     to avoid confusion due to two different updating methods,
>     removed goto's and a little reordering
> * PATCH 2/3:
>   * added SKB_LINEAR_ASSERT() to batadv_mcast_forw_scrape()
> * PATCH 3/3:
>   * 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)

Merged. But I think the wireshark implementation is still missing.

Kind regards,
	Sven