如何仅使用系统调用创建链表
How to create a linked list using system calls only
我正在尝试使用 C 中的系统调用创建通用链表，但我不确定从哪里开始。我知道如何编写标准链表，但不确定如何仅使用系统调用来转换它。例如，如果我们使用 malloc() 那是一个库调用，所以我不能使用 malloc 因为它不是系统调用。
我是从这个网站上来的https://kernelnewbies.org/FAQ/LinkedLists。
它提到创建一个内核链表，但我似乎无法编译它。
#include <linux/list.h>
struct mystruct
{
int data;
struct list_head mylist;
};
struct mystruct first ={
.data = 10,
.mylist = LIST_HEAD_INIT(first.mylist);
}
收到此编译器错误提示
致命错误：linux/list.h: 没有那个文件或目录
我的标准链表：
#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;
}
所以我的问题是：如何将我的标准列表转换为仅使用系统调用？
For example, if we use malloc() that's a library call so I can't use malloc since it is not a system call.
然后你可以管理分配在堆栈上的“自己的内存”。您的代码（简化为仅使用 int 数据）可能如下所示：
#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;
}
您可以采用 @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 建议的方法。但这里有一个实际系统调用的替代方法：
我相信，在汇编程序中可以最好地理解系统调用，并且在 Linux 下使用系统调用意味着，您写入 EAX 调用您想要的并执行，然后触发中断 0x80，它命令你的内核执行它。
因此，系统调用是 OS 相关的，简单地说，所有系统调用都是某些内核函数（通常以 sys_ 为前缀），它们都有一个明确定义的编号，所有这些通常可以在 /usr/include/bits/syscall.h 下找到。知道这一点很重要，因为标准 C 库（通常是 glibc）可以在这些系统调用之上实现像 malloc 这样的函数。对于每个单独的标准库调用来说，这当然不是真的，但这意味着，您也可以实现自己的 malloc 函数，并以 glibc、ulibc、dietlibc 为例，说明如何实现它。
在更高层次上，您可以使用 syscall，它本身是 glibc 中的一个函数，可以用来开始。但是为了避免任何此类调用，也可以将带有 -nostdlib 参数的程序编译为 gcc。这使得编写程序变得有点困难，因为你甚至不能使用 int main 函数，如果你不整理你的调用堆栈，你的程序就会崩溃，这是术语 argv 和 [=23] 背后的概念=].
由于我正在午休，所以没有完整的示例供您使用，但以下程序足以让您入门
// 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 %%ebp\n\t"
"movl %1, %%eax\n\t"
"movl %2, %%eax\n\t"
"movl %3, %%ebx\n\t"
"movl %4, %%ecx\n\t"
//"movl %4, %%edx\n\t"
"int [=10=]x80\n\t"
"popl %%ebp\n\t"
: "=a"(ret)
: "g"(syscall_number), "g"(arg1), "g"(arg2), "g"(arg3)
: "%ebx", "%ecx", "%edx", "%esi", "%edi"
);
return ret;
}
int _start() {
int start=0, length=10, prot=0, flags=0, fd=0, offset=0;
// @TODO: add further parameters to the syscall implementation
void * list = (void *) syscall(SYS_mmap, start, length, prot);
asm("movl ,%eax;"
"xorl %ebx,%ebx;"
"int [=10=]x80"
);
return 100;
}
我只能建议您阅读 syscall 手册页，linux 关于 writing custom syscalls
的内核文档
credits+thanks（源代码一起撕自：
我正在尝试使用 C 中的系统调用创建通用链表，但我不确定从哪里开始。我知道如何编写标准链表，但不确定如何仅使用系统调用来转换它。例如，如果我们使用 malloc() 那是一个库调用，所以我不能使用 malloc 因为它不是系统调用。
我是从这个网站上来的https://kernelnewbies.org/FAQ/LinkedLists。 它提到创建一个内核链表，但我似乎无法编译它。
#include <linux/list.h>
struct mystruct
{
int data;
struct list_head mylist;
};
struct mystruct first ={
.data = 10,
.mylist = LIST_HEAD_INIT(first.mylist);
}
收到此编译器错误提示 致命错误：linux/list.h: 没有那个文件或目录
我的标准链表：
#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;
}
所以我的问题是：如何将我的标准列表转换为仅使用系统调用？
For example, if we use
malloc()that's a library call so I can't usemallocsince it is not a system call.
然后你可以管理分配在堆栈上的“自己的内存”。您的代码（简化为仅使用 int 数据）可能如下所示：
#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;
}
您可以采用 @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 建议的方法。但这里有一个实际系统调用的替代方法：
我相信，在汇编程序中可以最好地理解系统调用，并且在 Linux 下使用系统调用意味着，您写入 EAX 调用您想要的并执行，然后触发中断 0x80，它命令你的内核执行它。
因此，系统调用是 OS 相关的，简单地说，所有系统调用都是某些内核函数（通常以 sys_ 为前缀），它们都有一个明确定义的编号，所有这些通常可以在 /usr/include/bits/syscall.h 下找到。知道这一点很重要，因为标准 C 库（通常是 glibc）可以在这些系统调用之上实现像 malloc 这样的函数。对于每个单独的标准库调用来说，这当然不是真的，但这意味着，您也可以实现自己的 malloc 函数，并以 glibc、ulibc、dietlibc 为例，说明如何实现它。
在更高层次上，您可以使用 syscall，它本身是 glibc 中的一个函数，可以用来开始。但是为了避免任何此类调用，也可以将带有 -nostdlib 参数的程序编译为 gcc。这使得编写程序变得有点困难，因为你甚至不能使用 int main 函数，如果你不整理你的调用堆栈，你的程序就会崩溃，这是术语 argv 和 [=23] 背后的概念=].
由于我正在午休，所以没有完整的示例供您使用，但以下程序足以让您入门
// 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 %%ebp\n\t"
"movl %1, %%eax\n\t"
"movl %2, %%eax\n\t"
"movl %3, %%ebx\n\t"
"movl %4, %%ecx\n\t"
//"movl %4, %%edx\n\t"
"int [=10=]x80\n\t"
"popl %%ebp\n\t"
: "=a"(ret)
: "g"(syscall_number), "g"(arg1), "g"(arg2), "g"(arg3)
: "%ebx", "%ecx", "%edx", "%esi", "%edi"
);
return ret;
}
int _start() {
int start=0, length=10, prot=0, flags=0, fd=0, offset=0;
// @TODO: add further parameters to the syscall implementation
void * list = (void *) syscall(SYS_mmap, start, length, prot);
asm("movl ,%eax;"
"xorl %ebx,%ebx;"
"int [=10=]x80"
);
return 100;
}
我只能建议您阅读 syscall 手册页，linux 关于 writing custom syscalls
credits+thanks（源代码一起撕自：