Linked List : list_cut_position
===============================

.. tab-set::

    .. tab-item:: Linked List : list_cut_position

        * In this program, you are going to learn

        .. panels::
                :container: container pb-4
                :column: col-lg-12 p-2
                :card: shadow

                * How to cut a list into two ?

        .. panels::
                :container: container pb-4
                :column: col-lg-12 p-2
                :card: shadow

                * How to use the below API's ?

                        * `INIT_LIST_HEAD <https://elixir.bootlin.com/linux/v6.2/source/tools/include/linux/list.h#L25>`_

                        * `list_add <https://elixir.bootlin.com/linux/latest/source/include/linux/list.h#L86>`_

                        * `list_for_each_entry <https://elixir.bootlin.com/linux/v6.2/source/include/linux/list.h#L673>`_

                        * `list_cut_position <https://elixir.bootlin.com/linux/latest/source/tools/include/linux/list.h#L260>`_

                        * `list_for_each_entry_safe <https://elixir.bootlin.com/linux/v6.2/source/tools/include/linux/list.h#L531>`_

                        * `list_del <https://elixir.bootlin.com/linux/v6.2/source/tools/include/linux/list.h#L113>`_


.. panels::
        :container: container pb-4
        :column: col-lg-12 p-2
        :card: shadow

        Topics in this section,

                * :ref:`Explanation of Program part by part <list_cut_position_4>`

                    * :ref:`List of headers <list_cut_position_5>`

                    * :ref:`Modules macro <list_cut_position_6>`

                    * :ref:`Initialize function and variables <list_cut_position_7>`

                    * :ref:`Module init function <list_cut_position_8>`

                    * :ref:`Module exit function <list_cut_position_9>`

                    * :ref:`Mention init and exit function <list_cut_position_11>`

                * :ref:`See the full program below <list_cut_position_0>`
                
                * :ref:`Makefile <list_cut_position_1>`

                * :ref:`Compile and Load <list_cut_position_2>`

                * :ref:`Summary of Linked List APIs <list_cut_position_3>`


.. _list_cut_position_4:

.. tab-set::

    .. tab-item:: Explanation of program part by part

        * In this example, we are going to cut a list into two.
        
        .. _list_cut_position_5: 

        .. tab-set::

            .. tab-item:: List of headers

                * Add the list of header files to refer the APIs used in this program.

                .. code-block:: c

                    #include <linux/init.h>
                    #include <linux/module.h>
                    #include <linux/kernel.h>
                    #include <linux/list.h>
                    #include <linux/slab.h>

        .. _list_cut_position_6:
        
        .. tab-set::

            .. tab-item:: Modules macro

                * Add the modules macro which lists the information about the license, author and description.

                .. code-block:: c

                    MODULE_LICENSE("GPL");
                    MODULE_AUTHOR("linux_usr");
                    MODULE_DESCRIPTION("Linked List");

        .. _list_cut_position_7:

        .. tab-set::

            .. tab-item:: Initialize function and variables

                * ``LIST_HEAD`` is used to initialize the list.

                .. code-block:: c

                    struct list_node {
                    	int data;
                    	struct list_head list;
                    };

                    static LIST_HEAD(my_list);
                    static LIST_HEAD(new_list);

                    struct list_node data1, data2, data3,data4,  *entry;

        .. _list_cut_position_8:

        .. tab-set::

            .. tab-item:: Module init function

                * Add the module init function to execute the function once when the module is loaded to the linux kernel.

                .. code-block:: c

                        static int __init linkedlist_init(void)
                        {
                            pr_info("Driver loaded\n");

                            data1.data = 10;
                            data2.data = 20;
                            data3.data = 30;
                            data4.data = 40;

                            INIT_LIST_HEAD(&data1.list);
                            INIT_LIST_HEAD(&data2.list);
                            INIT_LIST_HEAD(&data3.list);
                            INIT_LIST_HEAD(&data4.list);

                            list_add(&data1.list, &my_list);
                            list_add(&data2.list, &my_list);
                            list_add(&data3.list, &my_list);
                            list_add(&data4.list, &my_list);

                            list_for_each_entry(entry, &my_list, list) 
                                printk(KERN_INFO "my_list entry 1: %d\n",entry->data);

                            INIT_LIST_HEAD(&new_list);

                            list_cut_position(&new_list, &my_list, my_list.next);

                            list_for_each_entry(entry, &my_list, list) 
                                printk(KERN_INFO "my_list entry 2: %d\n",entry->data);

                            list_for_each_entry(entry, &new_list, list) 
							    printk(KERN_INFO "new_list entry : %d\n",entry->data);

                                return 0;
                        }

            
                * ``INIT_LIST_HEAD`` is used to initialize a list_head structure.

                .. code-block:: c

                    INIT_LIST_HEAD(&data1.list);
                    INIT_LIST_HEAD(&data2.list);
                    INIT_LIST_HEAD(&data3.list);
                    INIT_LIST_HEAD(&data4.list); 

                * ``list_add`` to insert a new element after the given list head. 

                .. code-block:: c

                    list_add(&data1.list, &my_list);
                    list_add(&data2.list, &my_list);
                    list_add(&data3.list, &my_list);
                    list_add(&data4.list, &my_list);

                * ``list_for_each_entry`` to iterate over list of given type.

                .. code-block:: c

                    list_for_each_entry(entry, &my_list, list)

                * ``list_cut_position`` All entries from list up to and including entry are moved to new, which should be an empty list. Entry may be equal to list, in which case no entries are moved. 

                .. code-block:: c

                    list_cut_position(&new_list, &my_list, my_list.next);

        .. _list_cut_position_9:

        .. tab-set::

            .. tab-item:: Module exit function

                * Add module exit function which is executed once the module is unloaded from the kernel.

                .. code-block:: c

					static void __exit linkedlist_exit(void)
					{
						struct list_node *ptr, *next;

						list_for_each_entry_safe(ptr, next, &my_list, list) {
							list_del(&ptr->list);
						}

						list_for_each_entry_safe(ptr, next, &new_list, list) {
							list_del(&ptr->list);
						}
						pr_info("Driver unloaded\n");
					}

        .. _list_cut_position_11:

        .. tab-set::

            .. tab-item:: Mention init and exit functions

                * Add the module init and exit which is called when the module is loaded and unloaded.

                .. code-block:: c

                    module_init(linkedlist_init);
                    module_exit(linkedlist_exit);

.. _list_cut_position_0:

.. tab-set::

    .. tab-item:: See the full program below

        .. tab-set::

            .. tab-item:: linked_list.c

                .. literalinclude:: list_cut_position/linked_list.c
		            :language: c
		            :linenos:

.. _list_cut_position_1:

.. tab-set::

    .. tab-item:: Makefile

        .. literalinclude:: list_cut_position/Makefile
		:language: c
		:linenos:


.. _list_cut_position_2:

.. tab-set::

    .. tab-item:: Compile and Load
        
        * Run Make to compile the module.

        .. code-block:: shell

            $make
            make -C /lib/modules/5.4.0-150-generic/build M=$HOME/kernel_linked_list modules
            make[1]: Entering directory '/usr/src/linux-headers-5.4.0-150-generic'
              CC [M]  $HOME/kernel_linked_list/linked_list.o
              Building modules, stage 2.
              MODPOST 1 modules
              CC [M]  $HOME/kernel_linked_list/linked_list.mod.o
              LD [M]  $HOME/kernel_linked_list/linked_list.ko
            make[1]: Leaving directory '/usr/src/linux-headers-5.4.0-150-generic'

        * Run ls to check if linked_list.ko is generated or not.

        .. code-block:: shell

            $ ls -l
            total 36
            -rw-rw-r-- 1 test test  154 Feb 26 13:18 Makefile
            -rw-rw-r-- 1 test test   47 Feb 26 13:18 modules.order
            -rw-rw-r-- 1 test test    0 Feb 26 13:18 Module.symvers
            -rw-rw-r-- 1 test test  820 Feb 26 13:18 linked_list.c
            -rw-rw-r-- 1 test test 5880 Feb 26 13:18 linked_list.ko
            -rw-rw-r-- 1 test test   47 Feb 26 13:18 linked_list.mod
            -rw-rw-r-- 1 test test  919 Feb 26 13:18 linked_list.mod.c
            -rw-rw-r-- 1 test test 3448 Feb 26 13:18 linked_list.mod.o
            -rw-rw-r-- 1 test test 3320 Feb 26 13:18 linked_list.o

        * Run insmod to load the module.

        .. code-block:: shell

            $ sudo insmod ./linked_list.ko

        * Check the kernel messages to see if the kernel module is loaded or not.

        .. code-block:: shell

            $ dmesg
            [15274.105659] Driver loaded
            [15274.105664] my_list entry 1: 40
            [15274.105664] my_list entry 1: 30
            [15274.105665] my_list entry 1: 20
            [15274.105665] my_list entry 1: 10
            [15274.105665] my_list entry 2: 30
            [15274.105666] my_list entry 2: 20
            [15274.105666] my_list entry 2: 10
            [15274.105666] new_list entry : 40

        * Run rmmod to unload the module.

        .. code-block:: shell

            $ sudo rmmod linked_list

        * Check dmesg to see if the module is unloaded from kernel.

        .. code-block:: shell

            $ dmesg
            [15274.105659] Driver loaded
            [15274.105664] my_list entry 1: 40
            [15274.105664] my_list entry 1: 30
            [15274.105665] my_list entry 1: 20
            [15274.105665] my_list entry 1: 10
            [15274.105665] my_list entry 2: 30
            [15274.105666] my_list entry 2: 20
            [15274.105666] my_list entry 2: 10
            [15274.105666] new_list entry : 40
            [15279.094026] Driver unloaded

.. _list_cut_position_3:
  
.. tab-set::

    .. tab-item:: Summary

        =============================== =====================================================================
        API                             Learning
        =============================== =====================================================================
        INIT_LIST_HEAD                  To  initialize a list_head structure
        LIST_HEAD                       To initialize the list
        list_for_each_entry             To iterate over list of given type
        list_cut_position               To cut a list into two
        list_for_each_entry_safe        To iterate over list of given type safe against removal of list entry
        list_add                        To insert a new entry after the specified head 
        list_del                        To delete entry from list  
        =============================== =====================================================================

.. card:: See Also

        * Previous Chapters

                * :doc:`../chapter1_basics/chapter1_basics`

                * :doc:`../chapter2_kthreads/chapter2_kthreads`

                * :doc:`../chapter3_tasklets/chapter3_tasklets`

                * :doc:`../chapter4_workqueue/chapter4_workqueue`        

                * :doc:`../chapter5_timer/chapter5_timer`


        * Other Linked List topics

                * :doc:`insert_rear`

                * :doc:`insert_at_pos`

                * :doc:`delete_rear`

                * :doc:`delete_front`

                * :doc:`delete_at_pos`

                * :doc:`list_splice`

                * :doc:`list_splice_init`

                * :doc:`list_splice_tail`

                * :doc:`list_splice_tail_init`

                * :doc:`list_del_init`

                * :doc:`list_first`

                * :doc:`list_first_entry_or_null`

                * :doc:`list_for_each`

                * :doc:`list_for_each_entry_continue`

                * :doc:`list_for_each_entry_continue_reverse`

                * :doc:`list_for_each_entry_safe_reverse`

                * :doc:`list_is_last`

                * :doc:`list_is_singular`

                * :doc:`list_last`

                * :doc:`list_move`

                * :doc:`list_move_tail`

                * :doc:`list_replace`

                * :doc:`list_replace_init`


        * Next Chapter

                * :doc:`../chapter9_fileSystem/chapter9_fileSystem`


        * Other Chapter
                
                * :doc:`../chapter10_netlink/chapter10_netlink`