I am trying to create a generic linked list using system calls in C, but I am not sure where to start. I know how to write a standard linked list but not sure how to convert it using just system calls. For example, if we use malloc() that's a library call so I can't use malloc since it is not a system call.
I have came up from this website https://kernelnewbies.org/FAQ/LinkedLists. It mentions creating a kernel linked list but I can't seem to compile it.
#include <linux/list.h>
struct mystruct
{
int data;
struct list_head mylist;
};
struct mystruct first ={
.data = 10,
.mylist = LIST_HEAD_INIT(first.mylist);
}
Getting this compiler error saying fatal error: linux/list.h: No such file or directory
My standard linked list:
#include <stdio.h>
#include <stdlib.h>
//Lets create a STRUCT node
struct Node
{
//Any data type since it is a VOID pointer
void *data;
struct Node *next;
};
//Add the Data to the LinkedList
void push(struct Node** head_ref, void *new_data,size_t data_size)
{
//Dynamically allocate the array
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = malloc(data_size);
new_node->next = (*head_ref);
//This will copy the contents of new_dat to newly allocated memory
int i;
for(i=0; i < data_size; i )
{
*(char *)(new_node->data i) = *(char*)(new_data i);
}
//Change head pointer as new node is added at the beginning
(*head_ref) = new_node;
}
void deleteNode(struct Node *head, struct Node *n)
{
// When node to be deleted is head node
if(head == n)
{
if(head->next == NULL)
{
printf("There is only one node. The list can't be made empty ");
return;
}
/* Copy the data of next node to head */
head->data = head->next->data;
// store address of next node
n = head->next;
// Remove the link of next node
head->next = head->next->next;
// free memory
free(n);
return;
}
// When not first node, follow the normal deletion process
// find the previous node
struct Node *prev = head;
while(prev->next != NULL && prev->next != n)
prev = prev->next;
// Check if node really exists in Linked List
if(prev->next == NULL)
{
printf("\n Given node is not present in Linked List");
return;
}
// Remove node from Linked List
prev->next = prev->next->next;
// Free memory
free(n);
return;
}
//Fptr is to access the function to be used for printing current node data
void printList(struct Node *node, void (*fptr)(void *))
{
while(node != NULL)
{
(*fptr)(node->data);
node = node->next;
}
}
//NOTE Different data types need different specifier print command
void printInt(void *n)
{
printf(" %d", *(int *)n);
}
//Function to print a float
void printFloat(void *f)
{
printf(" %f", *(float *)f);
}
int main()
{
//Create an array with the empty data as a start
struct Node *start = NULL;
//Create and print an int linked list
unsigned int_size = sizeof(int);
int arr[] = {10, 20,30,40, 50}, i;
for (i = 4; i >= 0; i--)
{
push(&start, &arr[i], int_size);
}
//You have to tell the position of the data by using the next
deleteNode(start, start->next);
printf("Created integer linked list is \n");
printList(start, printInt);
//Create and print a float linked list;
return 0;
}
So my question is: how do I convert my standard list to use system calls only?
CodePudding user response：
For example, if we use
malloc()that's a library call so I can't usemallocsince it is not a system call.
Then you can manage your "own memory", allocated on the stack. Your code (simplified to use only int data), could then look like this:
#include <stdio.h>
typedef int NodeRef;
struct Node {
int data;
NodeRef next; // index in memo (array)
};
#define MEMSIZE 1000
#define NULLREF MEMSIZE
NodeRef first_free = 0;
NodeRef unused = 0;
struct Node memo[MEMSIZE];
// Getters and setters:
NodeRef getNext(NodeRef node) {
return memo[node].next;
}
void setNext(NodeRef node, NodeRef next) {
memo[node].next = next;
}
int data(NodeRef node) {
return memo[node].data;
}
void setData(NodeRef node, int data) {
memo[node].data = data;
}
// Allocation / Deallocation
NodeRef newNode(int data, NodeRef next) {
NodeRef node = first_free;
if (node == NULLREF) {
printf("No more memory available for new nodes\n");
} else {
first_free = first_free < unused ? getNext(first_free) : first_free 1;
if (first_free > unused) unused = first_free;
setData(node, data);
setNext(node, next);
}
return node;
}
void discardNode(NodeRef node) {
setNext(node, first_free);
first_free = node;
}
// Linked List actions
void push(NodeRef* head_ref, int new_data) {
NodeRef new_node = newNode(new_data, *head_ref);
if (new_node != NULLREF) {
(*head_ref) = new_node;
}
}
void deleteNode(NodeRef* head_ref, NodeRef node) {
if (*head_ref == NULLREF) {
printf("Cannot delete from an empty Linked List\n");
return;
}
if (*head_ref == node) {
(*head_ref) = getNext(*head_ref);
} else {
NodeRef prev = *head_ref;
while (getNext(prev) != node) {
prev = getNext(prev);
if (prev == NULLREF) {
printf("Given node is not present in Linked List\n");
return;
}
}
setNext(prev, getNext(node));
}
discardNode(node);
}
void printList(NodeRef node) {
while (node != NULLREF) {
printf(" %d", data(node));
node = getNext(node);
}
printf("\n");
}
int main() {
NodeRef start = NULLREF;
int arr[] = {10, 20,30, 40, 50}, i;
for (i = 4; i >= 0; i--) {
push(&start, arr[i]);
}
deleteNode(&start, getNext(start));
printf("Created integer linked list is:\n");
printList(start);
return 0;
}
CodePudding user response：
You can go with the approach of @trincot, but it would not take advantage of syscalls. That is completely fine and if I remember correctly bash is implemented in a way, that it does not require a single malloc and instead does it like @trincot suggests. But here is an alternative approach with actual system calls:
I believe, that syscalls can best be understood in Assembler and using system calls under Linux means, that you write into EAX which call you want and execute and then trigger an interrupt 0x80, which commands your kernel to execute it.
For that reason system calls are OS dependent and simply speaking all system calls are certain kernel functions (usually prefixed with sys_), which have a well defined number to them, all of which can usually be found under /usr/include/bits/syscall.h. That is important to know, because the standard C library (often glibc) can implement functions like malloc on top of these system calls. That is not true for each and every individual standard library call, of cause, but it means, that you can also implement your own malloc function and take glibc, ulibc, dietlibc as an example on how you could achieve that.
On a higher level you could make use of syscall, which itself is a function found in glibc to get started. But in order to avoid any of such calls it is also possible to compile your program with the -nostdlib parameter to gcc. This makes writing programs a little harder, because you cannot even use an int main function and your program crashes if you do not tidy up your call stack, which is the concept behind the terms argv and argc.
As I am currenly having my lunch break I have no complete example for you, but the following program could be suffiecient for you to get started
// gcc -o main -nostdlib main.c
#include <sys/syscall.h>
static inline
int syscall(int syscall_number, int arg1, int arg2, int arg3) {
int ret;
asm volatile (
"pushl %