Browsing through a linked list.

Index > Main > Browsing through a linked list.

Author

Thread

sid123

Joined: 30 Jul 2013
Posts: 339
Location: Asia, Singapore

sid123 10 May 2014, 15:11

Hi,
I'm implementing my Device Manager which uses linked list for devices (bad idea I know), but anyways here's how my structure looks:

Code:

struc DeviceManager.Device 
{
        ;; pointer to name.
        .name dd 0x0
        ;; Pointer to open()
        ;; IN: ESI - Pointer to FILE structure (full path)
        .open: dd 0x00
        ;; Pointer to Close()
        ;; ESI - Pointer to file structure
        .close dd 0x00
        ;; Pointer to chdir 
        ;; IN: ESI - Pointer to new path
        .chdir: dd 0x0
        ;; Pointer to loadimage
        .loadimage: dd 0x0
        ;; Pointer to Write
        ;; IN: Same as read
        .write: dd 0x0
        ;; Pointer to Read
        ;; Should Follow this standard:
        ;; EAX - Pointer to FILE* structure (see /vfs/file.asm)
        ;; EBX - Memory Address to read to
        ;; ECX - Bytes to Read.
        .read: dd 0x00
        ;; readddir - pointer to readdir
        .readdir: dd 0x0
        ;; prev - pointer to previous device
        .prev dd 0x0
        ;; next - pointer to next device
        .next dd 0x0
        ;; Mounted Flag
        .mounted dd 0x0
        
}

These entries are filled by my device_manager_mount function which works perfectly.
Now I've a DeviceManager.Find function which searches the linked list for a device with a specific name, like "FAT16/" and then returns the entry number in EBX, which can be used to Read/Write to that device (like a file handle), the code is like this: (first_device is basically a pointer to the structure of the first device that was mounted, i.e. the first entry in the linked list)

Code:

;; Device Manager Structure
define DEVICE_MANAGER.NAME_OFFSET 0
define DEVICE_MANAGER.OPEN_OFFSET 4
define DEVICE_MANAGER.CLOSE_OFFSET 8
define DEVICE_MANAGER.CHDIR_OFFSET 12
define DEVICE_MANAGER.LOADIMAGE_OFFSET 16
define DEVICE_MANAGER.WRITE_OFFSET 20
define DEVICE_MANAGER.READ_OFFSET 24
define DEVICE_MANAGER.READDIR_OFFSET 28
define DEVICE_MANAGER.PREVIOUS_ENTRY_OFFSET 32
define DEVICE_MANAGER.NEXT_ENTRY_OFFSET 36
define DEVICE_MANAGER.MOUNTED_FLAG_OFFSET 40
......
;; devicemanager_mount - add a new entry to the device manager
;; in: esi pointer to DEVICE structure
DeviceManager.Mount:
        ;; are number of devices 0?
        cmp dword [number_of_devices], 0x0
        ;; nope, let's add a newone 
        jne .add_new_one
        ;; else do this
        ;; set this device as the first device
        mov dword [first_device], esi
        ;; only one device is there so mount this one as last device
        mov dword [last_device], esi
        ;; now set the previous device as 0
        mov dword [esi + DEVICE_MANAGER.PREVIOUS_ENTRY_OFFSET], 0x00000000
        ;; now set the next device as 0 too.
        mov dword [esi + DEVICE_MANAGER.NEXT_ENTRY_OFFSET], 0x00000000
        ;; Mount it
        mov dword [esi + DEVICE_MANAGER.MOUNTED_FLAG_OFFSET], 0x00000001
        ;; increment the no. of devices
        inc dword [number_of_devices]
        ;; return;
        ret
.add_new_one:
        pushad
        ;; okay, now get the  address of last entry
        mov edi, [last_device]
        ;; set the next entry of the last known mounted device to the device given here, i.e. we're creating a linked list
        mov dword[edi + DEVICE_MANAGER.NEXT_ENTRY_OFFSET], esi
        ;; now set the previous entry of the new device as the last one 
        mov dword[esi + DEVICE_MANAGER.PREVIOUS_ENTRY_OFFSET], edi
        ;; mount it
        mov dword [esi + DEVICE_MANAGER.MOUNTED_FLAG_OFFSET], 0x00000001
        inc dword [number_of_devices]
        ;; that's all, the device is mounted.
        popad
        ret
;; devicemanager_find_device - Find a device with a name
;; ESI - Pointer to name, ECX - Length of Name in Bytes
;; OUT: Device ID in EBX, CF set if device not found
DeviceManager.Find:
        clc
        push esi
        push edi
        push eax
;; save esi, will use this later
        mov dword [.tmp_save], esi
;; null out ebx, this value will be the file handle
        xor ebx, ebx
        ;; set current_device to the first entry for now.
        mov esi, [first_device] ;; -- address of first_device struct
        mov dword [.current_device], esi ;; set the current_device to the first_device
        ;; Set ESI to be the first entry.
        ;; address of name
        mov esi, [.current_device + DEVICE_MANAGER.NAME_OFFSET]
.loop:
;; name of the device that is to be found
        mov edi, [.tmp_save]
        ;; are they equal?
        repe cmpsb
;; yep.
        je .device_found
        ;; set eax to the address of the next device in the linked list
        mov eax, [.current_device + DEVICE_MANAGER.NEXT_ENTRY_OFFSET]
        mov esi, [eax] ;; offset 0 is the address of NAME, grab it.
        ;; and then check if ebx >= number of devices
        cmp ebx, dword [number_of_devices]
;; yes? then the device was not found
        jge .device_NF
;; else increment device ID
        inc ebx
;; and loop
        jmp .loop
.device_found:
        pop eax
        pop edi
        pop esi
        ret
.device_NF:
        pop eax
        pop edi
        pop esi
        stc
        xor ebx, ebx
        ret

        .tmp_save dd 0x0
        .current_device dd 0x0

I try it like this:

Code:

;; mount devnull
.....
DevNull DeviceManager.Device
.....
mov esi, DevNull
call DeviceManager.Mount
.....
FATDevice DeviceManager.Device 
.....
mov esi, FAT_DEVICE_NAME
mov dword [FATDevice.name], esi
;; set read/write/open et.c pointers
...
...
...
mov esi, FATDevice
call DeviceManager.Mount
mov esi, FAT_DEVICE_NAME
mov ecx, 5 ; -- sizeof(FAT_DEVICE_NAME) = 5
call DeviceManager.Find
;; EBX is always 0 and CF is always set, whereas it should be 1, and CF must be cleared.
.....
FAT_DEVICE_NAME db 'FAT16', 0

_________________
"Those who can make you believe in absurdities can make you commit atrocities" -- Voltaire https://github.com/Benderx2/R3X
XD

10 May 2014, 15:11

JohnFound

Joined: 16 Jun 2003
Posts: 3499
Location: Bulgaria

JohnFound 10 May 2014, 15:44

Never use "define" this way! It is very bad practice in FASM.

10 May 2014, 15:44

JohnFound

Joined: 16 Jun 2003
Posts: 3499
Location: Bulgaria

JohnFound 10 May 2014, 15:51

Code:

mov eax, [.current_device + DEVICE_MANAGER.NEXT_ENTRY_OFFSET]

This and all similar lines are wrong. Use:

Code:

mov exx, [.current_device]
mov eax, [exx+DEVICE_MANAGER.NEXT_ENTRY_OFFSET]

Note: "exx" means "any register".

10 May 2014, 15:51

m3ntal

Joined: 08 Dec 2013
Posts: 296

m3ntal 10 May 2014, 17:36

sid123: You can use virtual for this:

Code:

virtual at 0
 DEVICE_MANAGER.NAME_OFFSET dd ?
 DEVICE_MANAGER.OPEN_OFFSET dd ?
 DEVICE_MANAGER.CLOSE_OFFSET dd ?
 DEVICE_MANAGER.CHDIR_OFFSET dd ?
 DEVICE_MANAGER.LOADIMAGE_OFFSET dd ?
 DEVICE_MANAGER.WRITE_OFFSET dd ?
 DEVICE_MANAGER.READ_OFFSET dd ?
 DEVICE_MANAGER.READDIR_OFFSET dd ?
 DEVICE_MANAGER.PREVIOUS_ENTRY_OFFSET dd ?
 DEVICE_MANAGER.NEXT_ENTRY_OFFSET dd ?
 DEVICE_MANAGER.MOUNTED_FLAG_OFFSET dd ?
end virtual

Quote:

Never use "define" this way! It is very bad practice in FASM.

Why? Your FL uses HTML/Javascript keywords like "var a" and "body" while you accuse everyone else of being a HL programmer.

_________________
New FASM Site, Examples, Graphics, Updated Libraries

10 May 2014, 17:36

JohnFound

Joined: 16 Jun 2003
Posts: 3499
Location: Bulgaria

JohnFound 10 May 2014, 17:51

m3ntal wrote:

Why? Your FL uses HTML/Javascript keywords like "var a" and "body" while you accuse everyone else of being a HL programmer.

My note about using "define" has nothing to do with high-level languages. It is bad practice, because FASM has more convenient tools for the same thing. Features that will make the source more readable, easy for support and error-proof.

Notice, that "define" and "equ" work in FASM totally different than in other assemblers and/or C/C++. They have different use also.

If you want to use constants for the structure offsets, then define them simply by "=". But the proper use is to use only the structure definition, because every change of the structure will automatically update the offsets and this way will help to avoid hard to detect bugs.

The proper source for the above example is (comments removed for compactness):

Code:

struc DeviceManager.Device {
        .name dd 0x0
        .open: dd 0x00
        .close dd 0x00
        .chdir: dd 0x0
        .loadimage: dd 0x0
        .write: dd 0x0
        .read: dd 0x00
        .readdir: dd 0x0
        .prev dd 0x0
        .next dd 0x0
        .mounted dd 0x0
}
virtual at 0
  DeviceManager.Device DeviceManager.Device
end virtual

Now everywhere you can use the structure following way:

Code:

    mov   esi, [.ptrMyDevice]
    mov  [esi+DeviceManager.Device.next]

This functionality is embedded in the macro "struct" (both in Fresh macro library and FASM macro library, although the implementation is little bit different). The short way:

Code:

struct DeviceManager.Device
        .name dd 0x0
        .open: dd 0x00
        .close dd 0x00
        .chdir: dd 0x0
        .loadimage: dd 0x0
        .write: dd 0x0
        .read: dd 0x00
        .readdir: dd 0x0
        .prev dd 0x0
        .next dd 0x0
        .mounted dd 0x0
ends

_________________
Tox ID: 48C0321ADDB2FE5F644BB5E3D58B0D58C35E5BCBC81D7CD333633FEDF1047914A534256478D9

10 May 2014, 17:51

m3ntal

Joined: 08 Dec 2013
Posts: 296

m3ntal 10 May 2014, 22:07

Quote:

... uses linked list for devices

A generic fixed array might work. Pseudo: Device devices[32].

Quote:

the proper use is to use only the structure definition

Nothing wrong with using virtual for structures or a custom macro with label name: .member and match for exotic initiations: text t(128)='My Window'. IMAGE image='name.bmp'. "The right way is the way that works".

Quote:

Notice, that "define" and "equ" work in FASM totally different than in other assemblers and/or C/C++

My understanding of define is that it's the same operation of equ - replaces text - except that it works like = inside of the assembly directives: if/while/etc.

_________________
New FASM Site, Examples, Graphics, Updated Libraries

10 May 2014, 22:07

sid123

Joined: 30 Jul 2013
Posts: 339
Location: Asia, Singapore

sid123 11 May 2014, 06:11

JohnFound wrote:

Code:
mov eax, [.current_device + DEVICE_MANAGER.NEXT_ENTRY_OFFSET]     
This and all similar lines are wrong. Use:
Code:
mov exx, [.current_device]
mov eax, [exx+DEVICE_MANAGER.NEXT_ENTRY_OFFSET]    
Note: "exx" means "any register".

Thanks JohnFound for the help, really appreciate it. It works as expected now. Smile

m3ntal wrote:

A generic fixed array might work. Pseudo: Device devices[32].

The problem with fixed arrays as far as I know is that the number of devices will be limited, say if we have 2 consoles, 5 filesystems, 8 USB Devices, 10 printers....... It doesn't make much of sense but I don't want the number of devices to be fixed. Besides I should be using a tree like structure or inodes which is used by most modern OSes.

_________________
"Those who can make you believe in absurdities can make you commit atrocities" -- Voltaire https://github.com/Benderx2/R3X
XD

11 May 2014, 06:11

m3ntal

Joined: 08 Dec 2013
Posts: 296

m3ntal 11 May 2014, 18:02

Ah, I forgot! Too much pain medicine. define does the substitution but does not resolve equates:

Code:

X equ 7
define A X
B equ X

; to see the difference,
; uncomment one of these...

; 'A=' A ; X
; 'B=' B ; 7

sid123: I see it this way:

* Array (fixed): Fastest, easiest. For small arrays. Example: GAMEPAD gamepads[4]. USER chat.users[32]
* Dynamic array: Fast indexing: S*I+B. Insert and remove can take time unless it's an array of pointers
* Linked list (singly, doubly). Indexing takes time, searching nodes for ID. Fast insert and remove
* Binary tree: Complex. For dynamic arrays of arrays

11 May 2014, 18:02

revolution
When all else fails, read the source

Joined: 24 Aug 2004
Posts: 20448
Location: In your JS exploiting you and your system

revolution 12 May 2014, 17:45

Some posts spun off to a new topic here:
http://board.flatassembler.net/topic.php?t=16736

I hope I split it correctly Confused

12 May 2014, 17:45

< Last Thread | Next Thread >

Forum Rules:

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum