bug5

BUG5: LINKED LIST CORRUPTION
-----------------------------

Config: CONFIG_DEBUG_LIST
------

Location of Config: Kernel Hacking --> Debug linked list manipulation
------------------

Kernel Documentation: Enable this to turn on extended checks in the linked-list walking routines.
--------------------

Approach: 
---------
	- In a doubly linked list, if prev of node B points to node A, then next of node A should point to node B. If next of node A points to some other node X, the linked list is corrupted. The check for this scenario is there in linked-list walking routines. In this module, I have used the exploited the check in __list_add() routine, it checks for the above scenario before inserting a node between node A and B. 
	- I implemented a doubly linked list using struct list_head.
	- My linked list could be depicted as: HEAD --> A <--> B -->NULL
	- To corrupt the linked list, I changed the next of A to NULL without modifying B's previous. These kind of mistakes are possible to happen in real scenarios, if someone changes the list without using designated routines for the same.
	- After corrupting the link between A and B, if I try to add a node between A and B, it throws list add corruptio. Error message exacty says:
	"list_add corruption. prev->next should be next (ffff99e075e1d808), but was 0000000000000000. (prev=ffff99e075e1d788)."

Bug File Location: CSE-506/sys_bug5.c
-----------------

How ro run?
-----------
	- Run make in CSE-506 directory
	- Run CSE-506/scripts/bug5.sh
	- If you dont want to run the given script, after make you can install the module using "sh install_module.sh 5" and then run user programe "./xhw3 5", it will call sys_bug5() which implements list add corruption

Code in kernel to handle this config:
-------------------------------------
__list_add() called in my code is defined as follows in include/linux/list.h.

	#ifdef CONFIG_DEBUG_LIST
	extern bool __list_add_valid(struct list_head *new,
			      struct list_head *prev,
			      struct list_head *next);
	#else
	static inline bool __list_add_valid(struct list_head *new,
				struct list_head *prev,
				struct list_head *next)
	{
		return true;
	}
	#endif

	static inline void __list_add(struct list_head *new,
			      struct list_head *prev,
			      struct list_head *next)
	{
		if (!__list_add_valid(new, prev, next))
			return;

		next->prev = new;
		new->next = next;
		new->prev = prev;
		WRITE_ONCE(prev->next, new);
	}

__list_add_valid() used above for checking the corruption is defined as follows in lib/list/debug.c.

	
	bool __list_add_valid(struct list_head *new, struct list_head *prev,
		      struct list_head *next)
	{
		if (CHECK_DATA_CORRUPTION(next->prev != prev,
			"list_add corruption. next->prev should be prev (%px), but was %px. (next=%px).\n",
			prev, next->prev, next) ||
	    	    CHECK_DATA_CORRUPTION(prev->next != next,
			"list_add corruption. prev->next should be next (%px), but was %px. (prev=%px).\n",
			next, prev->next, prev) ||
	    	    CHECK_DATA_CORRUPTION(new == prev || new == next,
			"list_add double add: new=%px, prev=%px, next=%px.\n",
			new, prev, next))
		return false;

		return true;
	}