Changeset e2ea4ab1 in mainline


Ignore:
Timestamp:
2010-07-02T14:22:35Z (14 years ago)
Author:
Jakub Jermar <jakub@…>
Branches:
lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export
Children:
09b859c
Parents:
4d1be48 (diff), e3ee9b9 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

Merge mainline changes.

Files:
2 added
1 deleted
52 edited

Legend:

Unmodified
Added
Removed
  • HelenOS.config

    r4d1be48 re2ea4ab1  
    359359! CONFIG_LOG (n/y)
    360360
     361% Kernel function tracing
     362! CONFIG_TRACE (n/y)
     363
    361364% Compile kernel tests
    362365! CONFIG_TEST (y/n)
  • boot/arch/ia64/src/asm.S

    r4d1be48 re2ea4ab1  
    113113jump_to_kernel:
    114114        alloc loc0 = ar.pfs, 1, 1, 0, 0
    115         mov r1 = in0 ;;                 # Pass bootinfo address
     115        mov r2 = in0 ;;                 # Pass bootinfo address
    116116        movl r8 = KERNEL_ADDRESS;;
    117117        mov b1 = r8 ;;
  • defaults/amd64/Makefile.config

    r4d1be48 re2ea4ab1  
    3232CONFIG_LOG = n
    3333
     34# Kernel function tracing
     35CONFIG_TRACE = n
     36
    3437# Compile kernel tests
    3538CONFIG_TEST = y
  • defaults/arm32/Makefile.config

    r4d1be48 re2ea4ab1  
    2323CONFIG_LOG = n
    2424
     25# Kernel function tracing
     26CONFIG_TRACE = n
     27
    2528# Compile kernel tests
    2629CONFIG_TEST = y
  • defaults/ia32/Makefile.config

    r4d1be48 re2ea4ab1  
    3838CONFIG_LOG = n
    3939
     40# Kernel function tracing
     41CONFIG_TRACE = n
     42
    4043# Compile kernel tests
    4144CONFIG_TEST = y
  • defaults/ia64/Makefile.config

    r4d1be48 re2ea4ab1  
    3535CONFIG_LOG = n
    3636
     37# Kernel function tracing
     38CONFIG_TRACE = n
     39
    3740# Compile kernel tests
    3841CONFIG_TEST = y
  • defaults/mips32/Makefile.config

    r4d1be48 re2ea4ab1  
    2929CONFIG_LOG = n
    3030
     31# Kernel function tracing
     32CONFIG_TRACE = n
     33
    3134# Compile kernel tests
    3235CONFIG_TEST = y
  • defaults/ppc32/Makefile.config

    r4d1be48 re2ea4ab1  
    2323CONFIG_LOG = n
    2424
     25# Kernel function tracing
     26CONFIG_TRACE = n
     27
    2528# Compile kernel tests
    2629CONFIG_TEST = y
  • defaults/sparc64/Makefile.config

    r4d1be48 re2ea4ab1  
    3838CONFIG_LOG = n
    3939
     40# Kernel function tracing
     41CONFIG_TRACE = n
     42
    4043# Compile kernel tests
    4144CONFIG_TEST = y
  • defaults/special/Makefile.config

    r4d1be48 re2ea4ab1  
    2323CONFIG_LOG = n
    2424
     25# Kernel function tracing
     26CONFIG_TRACE = n
     27
    2528# Compile kernel tests
    2629CONFIG_TEST = y
  • kernel/Makefile

    r4d1be48 re2ea4ab1  
    160160        CFLAGS = $(GCC_CFLAGS)
    161161        DEPEND_DEFS = $(DEFS) $(CONFIG_DEFS)
     162        INSTRUMENTATION = -finstrument-functions
    162163endif
    163164
     
    165166        CFLAGS = $(GCC_CFLAGS)
    166167        DEPEND_DEFS = $(DEFS) $(CONFIG_DEFS)
     168        INSTRUMENTATION = -finstrument-functions
    167169endif
    168170
     
    170172        CFLAGS = $(ICC_CFLAGS)
    171173        DEPEND_DEFS = $(DEFS) $(CONFIG_DEFS)
     174        INSTRUMENTATION =
    172175endif
    173176
     
    176179        DEFS += $(CONFIG_DEFS)
    177180        DEPEND_DEFS = $(DEFS)
     181        INSTRUMENTATION =
    178182endif
    179183
     
    181185        CFLAGS = $(CLANG_CFLAGS)
    182186        DEPEND_DEFS = $(DEFS) $(CONFIG_DEFS)
     187        INSTRUMENTATION =
    183188endif
    184189
     
    202207        generic/src/debug/stacktrace.c \
    203208        generic/src/debug/panic.c \
     209        generic/src/debug/debug.c \
    204210        generic/src/interrupt/interrupt.c \
    205211        generic/src/main/main.c \
     
    355361endif
    356362
     363## Sources where instrumentation is enabled
     364#
     365
     366ifeq ($(CONFIG_TRACE),y)
     367INSTRUMENTED_SOURCES = \
     368        generic/src/cpu/cpu.c \
     369        generic/src/main/main.c \
     370        generic/src/main/kinit.c \
     371        generic/src/proc/the.c
     372endif
     373
    357374GENERIC_OBJECTS := $(addsuffix .o,$(basename $(GENERIC_SOURCES)))
    358375ARCH_OBJECTS := $(addsuffix .o,$(basename $(ARCH_SOURCES)))
     
    414431
    415432%.o: %.c $(DEPEND)
    416         $(CC) $(DEFS) $(CFLAGS) $(EXTRA_FLAGS) $(FPU_NO_CFLAGS) -c -o $@ $<
     433        $(CC) $(DEFS) $(CFLAGS) $(EXTRA_FLAGS) $(FPU_NO_CFLAGS) $(if $(findstring $<,$(INSTRUMENTED_SOURCES)),$(INSTRUMENTATION)) -c -o $@ $<
    417434ifeq ($(PRECHECK),y)
    418435        $(JOBFILE) $(JOB) $< $@ cc core $(DEFS) $(CFLAGS) $(EXTRA_FLAGS) $(FPU_NO_CFLAGS)
  • kernel/arch/abs32le/include/interrupt.h

    r4d1be48 re2ea4ab1  
    3737
    3838#include <typedefs.h>
     39#include <verify.h>
    3940
    4041#define IVT_ITEMS  0
  • kernel/arch/abs32le/src/abs32le.c

    r4d1be48 re2ea4ab1  
    151151}
    152152
     153void early_putchar(wchar_t ch)
     154{
     155}
     156
    153157/** @}
    154158 */
  • kernel/arch/amd64/Makefile.inc

    r4d1be48 re2ea4ab1  
    7171        arch/$(KARCH)/src/mm/page.c \
    7272        arch/$(KARCH)/src/mm/tlb.c \
    73         arch/$(KARCH)/src/asm_utils.S \
     73        arch/$(KARCH)/src/asm.S \
    7474        arch/$(KARCH)/src/cpu/cpu.c \
    7575        arch/$(KARCH)/src/proc/scheduler.c \
  • kernel/arch/amd64/src/boot/boot.S

    r4d1be48 re2ea4ab1  
    1 #
    2 # Copyright (c) 2005 Ondrej Palkovsky
    3 # Copyright (c) 2006 Martin Decky
    4 # Copyright (c) 2008 Jakub Jermar
    5 # All rights reserved.
    6 #
    7 # Redistribution and use in source and binary forms, with or without
    8 # modification, are permitted provided that the following conditions
    9 # are met:
    10 #
    11 # - Redistributions of source code must retain the above copyright
    12 #   notice, this list of conditions and the following disclaimer.
    13 # - Redistributions in binary form must reproduce the above copyright
    14 #   notice, this list of conditions and the following disclaimer in the
    15 #   documentation and/or other materials provided with the distribution.
    16 # - The name of the author may not be used to endorse or promote products
    17 #   derived from this software without specific prior written permission.
    18 #
    19 # THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
    20 # IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
    21 # OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
    22 # IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
    23 # INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
    24 # NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
    25 # DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
    26 # THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
    27 # (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
    28 # THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
    29 #
     1/*
     2 * Copyright (c) 2005 Ondrej Palkovsky
     3 * Copyright (c) 2006 Martin Decky
     4 * Copyright (c) 2008 Jakub Jermar
     5 * All rights reserved.
     6 *
     7 * Redistribution and use in source and binary forms, with or without
     8 * modification, are permitted provided that the following conditions
     9 * are met:
     10 *
     11 * - Redistributions of source code must retain the above copyright
     12 *   notice, this list of conditions and the following disclaimer.
     13 * - Redistributions in binary form must reproduce the above copyright
     14 *   notice, this list of conditions and the following disclaimer in the
     15 *   documentation and/or other materials provided with the distribution.
     16 * - The name of the author may not be used to endorse or promote products
     17 *   derived from this software without specific prior written permission.
     18 *
     19 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
     20 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
     21 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
     22 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
     23 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
     24 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
     25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
     26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
     27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
     28 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     29 */
    3030
    3131#include <arch/boot/boot.h>
     
    3737#include <arch/cpuid.h>
    3838
    39 #define START_STACK     (BOOT_OFFSET - BOOT_STACK_SIZE)
     39#define START_STACK  (BOOT_OFFSET - BOOT_STACK_SIZE)
    4040
    4141.section K_TEXT_START, "ax"
    4242
    4343.code32
     44
     45.macro pm_error msg
     46        movl \msg, %esi
     47        jmp pm_error_halt
     48.endm
     49
     50.macro pm_status msg
     51#ifdef CONFIG_EGA
     52        pushl %esi
     53        movl \msg, %esi
     54        call pm_early_puts
     55        popl %esi
     56#endif
     57.endm
     58
     59.macro pm2_status msg
     60#ifndef CONFIG_FB
     61        pm_status \msg
     62#endif
     63.endm
     64
    4465.align 4
    4566.global multiboot_image_start
     
    4768        .long MULTIBOOT_HEADER_MAGIC
    4869        .long MULTIBOOT_HEADER_FLAGS
    49         .long -(MULTIBOOT_HEADER_MAGIC + MULTIBOOT_HEADER_FLAGS)  # checksum
     70        .long -(MULTIBOOT_HEADER_MAGIC + MULTIBOOT_HEADER_FLAGS)  /* checksum */
    5071        .long multiboot_header
    5172        .long unmapped_ktext_start
     
    5677multiboot_image_start:
    5778        cld
    58         movl $START_STACK, %esp             # initialize stack pointer
    59         lgdtl bootstrap_gdtr                # initialize Global Descriptor Table register
    60        
     79       
     80        /* Initialize stack pointer */
     81        movl $START_STACK, %esp
     82       
     83        /* Initialize Global Descriptor Table register */
     84        lgdtl bootstrap_gdtr
     85       
     86        /* Kernel data + stack */
    6187        movw $gdtselector(KDATA_DES), %cx
    6288        movw %cx, %es
    63         movw %cx, %ds                       # kernel data + stack
     89        movw %cx, %ds
    6490        movw %cx, %ss
    6591       
    66         #
    67         # Simics seems to remove hidden part of GS on entering user mode
    68         # when _visible_ part of GS does not point to user-mode segment.
    69         #
    70        
     92        /*
     93         * Simics seems to remove hidden part of GS on entering user mode
     94         * when _visible_ part of GS does not point to user-mode segment.
     95         */
    7196        movw $gdtselector(UDATA_DES), %cx
    7297        movw %cx, %fs
     
    76101        multiboot_meeting_point:
    77102       
    78         movl %eax, grub_eax                 # save parameters from GRUB
     103        /* Save GRUB arguments */
     104        movl %eax, grub_eax
    79105        movl %ebx, grub_ebx
    80106       
    81         #
    82         # Protected 32-bit. We want to reuse the code-seg descriptor,
    83         # the Default operand size must not be 1 when entering long mode.
    84         #
     107        pm_status $status_prot
    85108       
    86109        movl $(INTEL_CPUID_EXTENDED), %eax
     
    89112        ja extended_cpuid_supported
    90113       
    91                 movl $extended_cpuid_msg, %esi
    92                 jmp error_halt
     114                pm_error $err_extended_cpuid
    93115       
    94116        extended_cpuid_supported:
     
    99121        jc long_mode_supported
    100122       
    101                 movl $long_mode_msg, %esi
    102                 jmp error_halt
     123                pm_error $err_long_mode
    103124       
    104125        long_mode_supported:
     
    107128        jc noexecute_supported
    108129       
    109                 movl $noexecute_msg, %esi
    110                 jmp error_halt
     130                pm_error $err_noexecute
    111131       
    112132        noexecute_supported:
     
    117137        jc fx_supported
    118138       
    119                 movl $fx_msg, %esi
    120                 jmp error_halt
     139                pm_error $err_fx
    121140       
    122141        fx_supported:
     
    125144        jc sse2_supported
    126145       
    127                 movl $sse2_msg, %esi
    128                 jmp error_halt
     146                pm_error $err_sse2
    129147       
    130148        sse2_supported:
    131 
     149       
    132150#include "vesa_prot.inc"
    133 
    134         #
    135         # Enable 64-bit page translation entries - CR4.PAE = 1.
    136         # Paging is not enabled until after long mode is enabled.
    137         #
     151       
     152        /*
     153         * Protected 32-bit. We want to reuse the code-seg descriptor,
     154         * the Default operand size must not be 1 when entering long mode.
     155         */
     156       
     157        pm2_status $status_prot2
     158       
     159        /*
     160         * Enable 64-bit page translation entries - CR4.PAE = 1.
     161         * Paging is not enabled until after long mode is enabled.
     162         */
    138163       
    139164        movl %cr4, %eax
     
    141166        movl %eax, %cr4
    142167       
    143         # set up paging tables
    144        
     168        /* Set up paging tables */
    145169        leal ptl_0, %eax
    146170        movl %eax, %cr3
    147171       
    148         # enable long mode
    149        
    150         movl $EFER_MSR_NUM, %ecx            # EFER MSR number
    151         rdmsr                               # read EFER
    152         btsl $AMD_LME_FLAG, %eax            # set LME = 1
    153         wrmsr                               # write EFER
    154        
    155         # enable paging to activate long mode (set CR0.PG = 1)
    156        
     172        /* Enable long mode */
     173        movl $EFER_MSR_NUM, %ecx
     174        rdmsr                     /* read EFER */
     175        btsl $AMD_LME_FLAG, %eax  /* set LME = 1 */
     176        wrmsr
     177       
     178        /* Enable paging to activate long mode (set CR0.PG = 1) */
    157179        movl %cr0, %eax
    158180        btsl $31, %eax
    159181        movl %eax, %cr0
    160182       
    161         # at this point we are in compatibility mode
    162        
     183        /* At this point we are in compatibility mode */
    163184        jmpl $gdtselector(KTEXT_DES), $start64
    164185
     186/** Print string to EGA display (in light red) and halt.
     187 *
     188 * Should be executed from 32 bit protected mode with paging
     189 * turned off. Stack is not required. This routine is used even
     190 * if CONFIG_EGA is not enabled. Since we are going to halt the
     191 * CPU anyway, it is always better to at least try to print
     192 * some hints.
     193 *
     194 * @param %esi Pointer to the NULL-terminated string
     195 *             to be print.
     196 *
     197 */
     198pm_error_halt:
     199        movl $0xb8000, %edi  /* base of EGA text mode memory */
     200        xorl %eax, %eax
     201       
     202        /* Read bits 8 - 15 of the cursor address */
     203        movw $0x3d4, %dx
     204        movb $0xe, %al
     205        outb %al, %dx
     206       
     207        movw $0x3d5, %dx
     208        inb %dx, %al
     209        shl $8, %ax
     210       
     211        /* Read bits 0 - 7 of the cursor address */
     212        movw $0x3d4, %dx
     213        movb $0xf, %al
     214        outb %al, %dx
     215       
     216        movw $0x3d5, %dx
     217        inb %dx, %al
     218       
     219        /* Sanity check for the cursor on screen */
     220        cmp $2000, %ax
     221        jb err_cursor_ok
     222       
     223                movw $1998, %ax
     224       
     225        err_cursor_ok:
     226       
     227        movw %ax, %bx
     228        shl $1, %eax
     229        addl %eax, %edi
     230       
     231        err_ploop:
     232                lodsb
     233               
     234                cmp $0, %al
     235                je err_ploop_end
     236               
     237                movb $0x0c, %ah  /* black background, light red foreground */
     238                stosw
     239               
     240                /* Sanity check for the cursor on the last line */
     241                inc %bx
     242                cmp $2000, %bx
     243                jb err_ploop
     244               
     245                /* Scroll the screen (24 rows) */
     246                movl %esi, %edx
     247                movl $0xb80a0, %esi
     248                movl $0xb8000, %edi
     249                movl $1920, %ecx
     250                rep movsw
     251               
     252                /* Clear the 24th row */
     253                xorl %eax, %eax
     254                movl $80, %ecx
     255                rep stosw
     256               
     257                /* Go to row 24 */
     258                movl %edx, %esi
     259                movl $0xb8f00, %edi
     260                movw $1920, %bx
     261               
     262                jmp err_ploop
     263        err_ploop_end:
     264       
     265        /* Write bits 8 - 15 of the cursor address */
     266        movw $0x3d4, %dx
     267        movb $0xe, %al
     268        outb %al, %dx
     269       
     270        movw $0x3d5, %dx
     271        movb %bh, %al
     272        outb %al, %dx
     273       
     274        /* Write bits 0 - 7 of the cursor address */
     275        movw $0x3d4, %dx
     276        movb $0xf, %al
     277        outb %al, %dx
     278       
     279        movw $0x3d5, %dx
     280        movb %bl, %al
     281        outb %al, %dx
     282       
     283        cli
     284        hlt1:
     285                hlt
     286                jmp hlt1
     287
     288/** Print string to EGA display (in light green).
     289 *
     290 * Should be called from 32 bit protected mode with paging
     291 * turned off. A stack space of at least 24 bytes is required,
     292 * but the function does not establish a stack frame.
     293 *
     294 * Macros such as pm_status and pm2_status take care that
     295 * this function is used only when CONFIG_EGA is enabled
     296 * and CONFIG_FB is disabled.
     297 *
     298 * @param %esi Pointer to the NULL-terminated string
     299 *             to be print.
     300 *
     301 */
     302pm_early_puts:
     303        pushl %eax
     304        pushl %ebx
     305        pushl %ecx
     306        pushl %edx
     307        pushl %edi
     308       
     309        movl $0xb8000, %edi  /* base of EGA text mode memory */
     310        xorl %eax, %eax
     311       
     312        /* Read bits 8 - 15 of the cursor address */
     313        movw $0x3d4, %dx
     314        movb $0xe, %al
     315        outb %al, %dx
     316       
     317        movw $0x3d5, %dx
     318        inb %dx, %al
     319        shl $8, %ax
     320       
     321        /* Read bits 0 - 7 of the cursor address */
     322        movw $0x3d4, %dx
     323        movb $0xf, %al
     324        outb %al, %dx
     325       
     326        movw $0x3d5, %dx
     327        inb %dx, %al
     328       
     329        /* Sanity check for the cursor on screen */
     330        cmp $2000, %ax
     331        jb pm_puts_cursor_ok
     332       
     333                movw $1998, %ax
     334       
     335        pm_puts_cursor_ok:
     336       
     337        movw %ax, %bx
     338        shl $1, %eax
     339        addl %eax, %edi
     340       
     341        pm_puts_ploop:
     342                lodsb
     343               
     344                cmp $0, %al
     345                je pm_puts_ploop_end
     346               
     347                movb $0x0a, %ah  /* black background, light green foreground */
     348                stosw
     349               
     350                /* Sanity check for the cursor on the last line */
     351                inc %bx
     352                cmp $2000, %bx
     353                jb pm_puts_ploop
     354               
     355                /* Scroll the screen (24 rows) */
     356                movl %esi, %edx
     357                movl $0xb80a0, %esi
     358                movl $0xb8000, %edi
     359                movl $1920, %ecx
     360                rep movsw
     361               
     362                /* Clear the 24th row */
     363                xorl %eax, %eax
     364                movl $80, %ecx
     365                rep stosw
     366               
     367                /* Go to row 24 */
     368                movl %edx, %esi
     369                movl $0xb8f00, %edi
     370                movw $1920, %bx
     371               
     372                jmp pm_puts_ploop
     373        pm_puts_ploop_end:
     374       
     375        /* Write bits 8 - 15 of the cursor address */
     376        movw $0x3d4, %dx
     377        movb $0xe, %al
     378        outb %al, %dx
     379       
     380        movw $0x3d5, %dx
     381        movb %bh, %al
     382        outb %al, %dx
     383       
     384        /* Write bits 0 - 7 of the cursor address */
     385        movw $0x3d4, %dx
     386        movb $0xf, %al
     387        outb %al, %dx
     388       
     389        movw $0x3d5, %dx
     390        movb %bl, %al
     391        outb %al, %dx
     392       
     393        popl %edi
     394        popl %edx
     395        popl %ecx
     396        popl %ebx
     397        popl %eax
     398       
     399        ret
     400
    165401.code64
     402
     403.macro long_status msg
     404        pushq %rdi
     405        movq \msg, %rdi
     406        call early_puts
     407        popq %rdi
     408.endm
     409
    166410start64:
     411       
     412        /*
     413         * Long mode.
     414         */
     415       
    167416        movq $(PA2KA(START_STACK)), %rsp
    168417       
    169         # call arch_pre_main(grub_eax, grub_ebx)
     418        /* Create the first stack frame */
     419        pushq $0
     420        movq %rsp, %rbp
     421       
     422        long_status $status_long
     423       
     424        /* Call arch_pre_main(grub_eax, grub_ebx) */
    170425        xorq %rdi, %rdi
    171426        movl grub_eax, %edi
     
    176431        callq *%rax
    177432       
    178         # create the first stack frame
    179         pushq $0
    180         movq %rsp, %rbp
    181        
     433        long_status $status_main
     434       
     435        /* Call main_bsp() */
    182436        movabsq $main_bsp, %rax
    183437        call *%rax
    184438       
    185         # not reached
    186        
     439        /* Not reached */
    187440        cli
    188441        hlt0:
     
    190443                jmp hlt0
    191444
    192 # Print string from %esi to EGA display (in red) and halt
    193 error_halt:
    194         movl $0xb8000, %edi       # base of EGA text mode memory
    195         xorl %eax, %eax
    196        
    197         movw $0x3d4, %dx          # read bits 8 - 15 of the cursor address
     445/** Print string to EGA display.
     446 *
     447 * Should be called from long mode (with paging enabled
     448 * and stack established). This function is ABI compliant
     449 * (without red-zone).
     450 *
     451 * If CONFIG_EGA is undefined or CONFIG_FB is defined
     452 * then this function does nothing.
     453 *
     454 * @param %rdi Pointer to the NULL-terminated string
     455 *             to be printed.
     456 *
     457 */
     458early_puts:
     459       
     460#if ((defined(CONFIG_EGA)) && (!defined(CONFIG_FB)))
     461       
     462        /* Prologue, save preserved registers */
     463        pushq %rbp
     464        movq %rsp, %rbp
     465        pushq %rbx
     466       
     467        movq %rdi, %rsi
     468        movq $(PA2KA(0xb8000)), %rdi  /* base of EGA text mode memory */
     469        xorq %rax, %rax
     470       
     471        /* Read bits 8 - 15 of the cursor address */
     472        movw $0x3d4, %dx
    198473        movb $0xe, %al
    199474        outb %al, %dx
     
    203478        shl $8, %ax
    204479       
    205         movw $0x3d4, %dx          # read bits 0 - 7 of the cursor address
     480        /* Read bits 0 - 7 of the cursor address */
     481        movw $0x3d4, %dx
    206482        movb $0xf, %al
    207483        outb %al, %dx
     
    210486        inb %dx, %al
    211487       
    212         cmp $1920, %ax
    213         jbe cursor_ok
    214        
    215                 movw $1920, %ax       # sanity check for the cursor on the last line
    216        
    217         cursor_ok:
     488        /* Sanity check for the cursor on screen */
     489        cmp $2000, %ax
     490        jb early_puts_cursor_ok
     491       
     492                movw $1998, %ax
     493       
     494        early_puts_cursor_ok:
    218495       
    219496        movw %ax, %bx
    220         shl $1, %eax
    221         addl %eax, %edi
    222        
    223         movw $0x0c00, %ax         # black background, light red foreground
    224        
    225         ploop:
     497        shl $1, %rax
     498        addq %rax, %rdi
     499       
     500        early_puts_ploop:
    226501                lodsb
     502               
    227503                cmp $0, %al
    228                 je ploop_end
     504                je early_puts_ploop_end
     505               
     506                movb $0x0e, %ah  /* black background, yellow foreground */
    229507                stosw
     508               
     509                /* Sanity check for the cursor on the last line */
    230510                inc %bx
    231                 jmp ploop
    232         ploop_end:
    233        
    234         movw $0x3d4, %dx          # write bits 8 - 15 of the cursor address
     511                cmp $2000, %bx
     512                jb early_puts_ploop
     513               
     514                /* Scroll the screen (24 rows) */
     515                movq %rsi, %rdx
     516                movq $(PA2KA(0xb80a0)), %rsi
     517                movq $(PA2KA(0xb8000)), %rdi
     518                movq $1920, %rcx
     519                rep movsw
     520               
     521                /* Clear the 24th row */
     522                xorq %rax, %rax
     523                movq $80, %rcx
     524                rep stosw
     525               
     526                /* Go to row 24 */
     527                movq %rdx, %rsi
     528                movq $(PA2KA(0xb8f00)), %rdi
     529                movw $1920, %bx
     530               
     531                jmp early_puts_ploop
     532        early_puts_ploop_end:
     533       
     534        /* Write bits 8 - 15 of the cursor address */
     535        movw $0x3d4, %dx
    235536        movb $0xe, %al
    236537        outb %al, %dx
     
    240541        outb %al, %dx
    241542       
    242         movw $0x3d4, %dx          # write bits 0 - 7 of the cursor address
     543        /* Write bits 0 - 7 of the cursor address */
     544        movw $0x3d4, %dx
    243545        movb $0xf, %al
    244546        outb %al, %dx
     
    248550        outb %al, %dx
    249551       
    250         cli
    251         hlt1:
    252                 hlt
    253                 jmp hlt1
     552        /* Epilogue, restore preserved registers */
     553        popq %rbx
     554        leave
     555       
     556#endif
     557       
     558        ret
    254559
    255560#include "vesa_real.inc"
     
    257562.section K_INI_PTLS, "aw", @progbits
    258563
    259 #
    260 # Macro for generating initial page table contents.
    261 # @param cnt Number of entries to generate. Must be multiple of 8.
    262 # @param g   Number of GB that will be added to the mapping.
    263 #
     564/** Generate initial page table contents.
     565 *
     566 * @param cnt Number of entries to generate. Must be multiple of 8.
     567 * @param g   Number of GB that will be added to the mapping.
     568 *
     569 */
    264570.macro ptl2gen cnt g
    265571        .if \cnt
     
    276582.endm
    277583
    278 # Page table for pages in the 1st gigabyte.
     584/* Page table for pages in the 1st gigabyte. */
    279585.align 4096
    280586ptl_2_0g:
    281587        ptl2gen 512 0
    282588
    283 # Page table for pages in the 2nd gigabyte.
     589/* Page table for pages in the 2nd gigabyte. */
    284590.align 4096
    285591ptl_2_1g:
    286592        ptl2gen 512 1
    287593
    288 # Page table for pages in the 3rd gigabyte.
     594/* Page table for pages in the 3rd gigabyte. */
    289595.align 4096
    290596ptl_2_2g:
    291597        ptl2gen 512 2
    292598
    293 # Page table for pages in the 4th gigabyte.
     599/* Page table for pages in the 4th gigabyte. */
    294600.align 4096
    295601ptl_2_3g:
    296602        ptl2gen 512 3
    297603
    298 # Page table for pages in the 5th gigabyte.
     604/* Page table for pages in the 5th gigabyte. */
    299605.align 4096
    300606ptl_2_4g:
    301607        ptl2gen 512 3
    302608
    303 # Page table for pages in the 6th gigabyte.
     609/* Page table for pages in the 6th gigabyte. */
    304610.align 4096
    305611ptl_2_5g:
    306612        ptl2gen 512 3
    307613
    308 # Page table for pages in the 7th gigabyte.
     614/* Page table for pages in the 7th gigabyte. */
    309615.align 4096
    310616ptl_2_6g:
    311617        ptl2gen 512 3
    312618
    313 # Page table for pages in the 8th gigabyte.
     619/* Page table for pages in the 8th gigabyte. */
    314620.align 4096
    315621ptl_2_7g:
     
    318624.align 4096
    319625ptl_1:
    320         # Identity mapping for [0; 8G)
     626        /* Identity mapping for [0; 8G) */
    321627        .quad ptl_2_0g + (PTL_WRITABLE | PTL_PRESENT)
    322628        .quad ptl_2_1g + (PTL_WRITABLE | PTL_PRESENT)
     
    350656        .long 0
    351657
    352 extended_cpuid_msg:
     658err_extended_cpuid:
    353659        .asciz "Error: Extended CPUID not supported -- CPU is not 64-bit. System halted."
    354 long_mode_msg:
     660err_long_mode:
    355661        .asciz "Error: 64-bit long mode not supported. System halted."
    356 noexecute_msg:
     662err_noexecute:
    357663        .asciz "Error: No-execute pages not supported. System halted."
    358 fx_msg:
     664err_fx:
    359665        .asciz "Error: FXSAVE/FXRESTORE instructions not supported. System halted."
    360 sse2_msg:
     666err_sse2:
    361667        .asciz "Error: SSE2 instructions not supported. System halted."
     668
     669status_prot:
     670        .asciz "[prot] "
     671status_vesa_copy:
     672        .asciz "[vesa_copy] "
     673status_grub_cmdline:
     674        .asciz "[grub_cmdline] "
     675status_vesa_real:
     676        .asciz "[vesa_real] "
     677status_prot2:
     678        .asciz "[prot2] "
     679status_long:
     680        .asciz "[long] "
     681status_main:
     682        .asciz "[main] "
  • kernel/arch/amd64/src/boot/vesa_ret.inc

    r4d1be48 re2ea4ab1  
    11.code32
    22vesa_init_protected:
     3        cld
     4       
     5        /* Initialize stack pointer */
     6        movl $START_STACK, %esp
     7       
     8        /* Kernel data + stack */
    39        movw $gdtselector(KDATA_DES), %cx
    410        movw %cx, %es
    5         movw %cx, %ds                       # kernel data + stack
     11        movw %cx, %ds
    612        movw %cx, %ss
    713       
    8         #
    9         # Simics seems to remove hidden part of GS on entering user mode
    10         # when _visible_ part of GS does not point to user-mode segment.
    11         #
     14        /*
     15         * Simics seems to remove hidden part of GS on entering user mode
     16         * when _visible_ part of GS does not point to user-mode segment.
     17         */
    1218       
    1319        movw $gdtselector(UDATA_DES), %cx
     
    1521        movw %cx, %gs
    1622       
    17         movl $START_STACK, %esp             # initialize stack pointer
    18        
    1923        jmpl $gdtselector(KTEXT32_DES), $vesa_meeting_point
  • kernel/arch/amd64/src/debugger.c

    r4d1be48 re2ea4ab1  
    230230                                return;
    231231                       
    232                         printf("*** Found ZERO on address %lx (slot %d) ***\n",
     232                        printf("*** Found ZERO on address %" PRIp " (slot %d) ***\n",
    233233                            breakpoints[slot].address, slot);
    234234                } else {
    235                         printf("Data watchpoint - new data: %lx\n",
     235                        printf("Data watchpoint - new data: %" PRIp "\n",
    236236                            *((unative_t *) breakpoints[slot].address));
    237237                }
    238238        }
    239239       
    240         printf("Reached breakpoint %d:%lx (%s)\n", slot, getip(istate),
     240        printf("Reached breakpoint %d:%" PRIp " (%s)\n", slot, getip(istate),
    241241            symtab_fmt_name_lookup(getip(istate)));
    242242       
  • kernel/arch/arm32/src/asm.S

    r4d1be48 re2ea4ab1  
    1 #
    2 # Copyright (c) 2007 Michal Kebrt
    3 # All rights reserved.
    4 #
    5 # Redistribution and use in source and binary forms, with or without
    6 # modification, are permitted provided that the following conditions
    7 # are met:
    8 #
    9 # - Redistributions of source code must retain the above copyright
    10 #   notice, this list of conditions and the following disclaimer.
    11 # - Redistributions in binary form must reproduce the above copyright
    12 #   notice, this list of conditions and the following disclaimer in the
    13 #   documentation and/or other materials provided with the distribution.
    14 # - The name of the author may not be used to endorse or promote products
    15 #   derived from this software without specific prior written permission.
    16 #
    17 # THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
    18 # IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
    19 # OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
    20 # IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
    21 # INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
    22 # NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
    23 # DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
    24 # THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
    25 # (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
    26 # THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
    27 #
     1/*
     2 * Copyright (c) 2007 Michal Kebrt
     3 * All rights reserved.
     4 *
     5 * Redistribution and use in source and binary forms, with or without
     6 * modification, are permitted provided that the following conditions
     7 * are met:
     8 *
     9 * - Redistributions of source code must retain the above copyright
     10 *   notice, this list of conditions and the following disclaimer.
     11 * - Redistributions in binary form must reproduce the above copyright
     12 *   notice, this list of conditions and the following disclaimer in the
     13 *   documentation and/or other materials provided with the distribution.
     14 * - The name of the author may not be used to endorse or promote products
     15 *   derived from this software without specific prior written permission.
     16 *
     17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
     18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
     19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
     20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
     21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
     22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
     23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
     24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
     25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
     26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     27 */
    2828
    29        
    3029.text
    3130
     
    3736.global memcpy_from_uspace_failover_address
    3837.global memcpy_to_uspace_failover_address
     38.global early_putchar
    3939
    4040memsetb:
     
    4747memcpy_from_uspace:
    4848memcpy_to_uspace:
    49         add     r3, r1, #3
    50         bic     r3, r3, #3
    51         cmp     r1, r3
    52         stmdb   sp!, {r4, r5, lr}
    53         mov     r5, r0                  /* save dst */
    54         beq     4f
    55 1:
    56         cmp     r2, #0
    57         movne   ip, #0
    58         beq     3f
    59 2:
    60         ldrb    r3, [ip, r1]
    61         strb    r3, [ip, r0]
    62         add     ip, ip, #1
    63         cmp     ip, r2
    64         bne     2b
    65 3:
    66         mov     r0, r5
    67         ldmia   sp!, {r4, r5, pc}
    68 4:
    69         add     r3, r0, #3
    70         bic     r3, r3, #3
    71         cmp     r0, r3
    72         bne     1b
    73         movs    r4, r2, lsr #2
    74         moveq   lr, r4
    75         beq     6f
    76         mov     lr, #0
    77         mov     ip, lr
    78 5:
    79         ldr     r3, [ip, r1]
    80         add     lr, lr, #1
    81         cmp     lr, r4
    82         str     r3, [ip, r0]
    83         add     ip, ip, #4
    84         bne     5b
    85 6:
    86         ands    r4, r2, #3
    87         beq     3b
    88         mov     r3, lr, lsl #2
    89         add     r0, r3, r0
    90         add     ip, r3, r1
    91         mov     r2, #0
    92 7:
    93         ldrb    r3, [r2, ip]
    94         strb    r3, [r2, r0]
    95         add     r2, r2, #1
    96         cmp     r2, r4
    97         bne     7b
    98         b       3b
     49        add r3, r1, #3
     50        bic r3, r3, #3
     51        cmp r1, r3
     52        stmdb sp!, {r4, r5, lr}
     53        mov r5, r0 /* save dst */
     54        beq 4f
     55       
     56        1:
     57                cmp r2, #0
     58                movne ip, #0
     59                beq 3f
     60       
     61        2:
     62                ldrb r3, [ip, r1]
     63                strb r3, [ip, r0]
     64                add ip, ip, #1
     65                cmp ip, r2
     66                bne 2b
     67       
     68        3:
     69                mov r0, r5
     70                ldmia sp!, {r4, r5, pc}
     71       
     72        4:
     73                add r3, r0, #3
     74                bic r3, r3, #3
     75                cmp r0, r3
     76                bne 1b
     77                movs r4, r2, lsr #2
     78                moveq lr, r4
     79                beq 6f
     80                mov lr, #0
     81                mov ip, lr
     82       
     83        5:
     84                ldr r3, [ip, r1]
     85                add lr, lr, #1
     86                cmp lr, r4
     87                str r3, [ip, r0]
     88                add ip, ip, #4
     89                bne 5b
     90       
     91        6:
     92                ands r4, r2, #3
     93                beq 3b
     94                mov r3, lr, lsl #2
     95                add r0, r3, r0
     96                add ip, r3, r1
     97                mov r2, #0
     98       
     99        7:
     100                ldrb r3, [r2, ip]
     101                strb r3, [r2, r0]
     102                add r2, r2, #1
     103                cmp r2, r4
     104                bne 7b
     105                b 3b
    99106
    100107memcpy_from_uspace_failover_address:
    101108memcpy_to_uspace_failover_address:
    102         mov     r0, #0
    103         ldmia   sp!, {r4, r5, pc}
     109        mov r0, #0
     110        ldmia sp!, {r4, r5, pc}
     111
     112early_putchar:
     113        mov pc, lr
  • kernel/arch/ia32/include/smp/apic.h

    r4d1be48 re2ea4ab1  
    347347
    348348extern uint32_t apic_id_mask;
     349extern uint8_t bsp_l_apic;
    349350
    350351extern void apic_init(void);
     
    355356extern int l_apic_send_init_ipi(uint8_t);
    356357extern void l_apic_debug(void);
    357 extern uint8_t l_apic_id(void);
    358358
    359359extern uint32_t io_apic_read(uint8_t);
  • kernel/arch/ia32/src/asm.S

    r4d1be48 re2ea4ab1  
    1 #
    2 # Copyright (c) 2001-2004 Jakub Jermar
    3 # All rights reserved.
    4 #
    5 # Redistribution and use in source and binary forms, with or without
    6 # modification, are permitted provided that the following conditions
    7 # are met:
    8 #
    9 # - Redistributions of source code must retain the above copyright
    10 #   notice, this list of conditions and the following disclaimer.
    11 # - Redistributions in binary form must reproduce the above copyright
    12 #   notice, this list of conditions and the following disclaimer in the
    13 #   documentation and/or other materials provided with the distribution.
    14 # - The name of the author may not be used to endorse or promote products
    15 #   derived from this software without specific prior written permission.
    16 #
    17 # THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
    18 # IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
    19 # OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
    20 # IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
    21 # INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
    22 # NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
    23 # DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
    24 # THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
    25 # (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
    26 # THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
    27 #
    28 
    29 ## very low and hardware-level functions
    30 
    31 # Mask for interrupts 0 - 31 (bits 0 - 31) where 0 means that int has no error
    32 # word and 1 means interrupt with error word
    33 #define ERROR_WORD_INTERRUPT_LIST 0x00027d00
     1/*
     2 * Copyright (c) 2001 Jakub Jermar
     3 * All rights reserved.
     4 *
     5 * Redistribution and use in source and binary forms, with or without
     6 * modification, are permitted provided that the following conditions
     7 * are met:
     8 *
     9 * - Redistributions of source code must retain the above copyright
     10 *   notice, this list of conditions and the following disclaimer.
     11 * - Redistributions in binary form must reproduce the above copyright
     12 *   notice, this list of conditions and the following disclaimer in the
     13 *   documentation and/or other materials provided with the distribution.
     14 * - The name of the author may not be used to endorse or promote products
     15 *   derived from this software without specific prior written permission.
     16 *
     17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
     18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
     19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
     20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
     21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
     22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
     23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
     24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
     25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
     26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     27 */
     28
     29/** Very low and hardware-level functions
     30 *
     31 */
     32
     33/**
     34 * Mask for interrupts 0 - 31 (bits 0 - 31) where 0 means that int
     35 * has no error word  and 1 means interrupt with error word
     36 *
     37 */
     38#define ERROR_WORD_INTERRUPT_LIST  0x00027d00
     39
     40#include <arch/pm.h>
     41#include <arch/mm/page.h>
    3442
    3543.text
    36 
    3744.global paging_on
    3845.global enable_l_apic_in_msr
     
    4552.global memcpy_to_uspace
    4653.global memcpy_to_uspace_failover_address
    47 
    48 
    49 # Wrapper for generic memsetb
     54.global early_putchar
     55
     56/* Wrapper for generic memsetb */
    5057memsetb:
    5158        jmp _memsetb
    5259
    53 # Wrapper for generic memsetw
     60/* Wrapper for generic memsetw */
    5461memsetw:
    5562        jmp _memsetw
    5663
    57 
    58 #define MEMCPY_DST      4
    59 #define MEMCPY_SRC      8
    60 #define MEMCPY_SIZE     12
     64#define MEMCPY_DST   4
     65#define MEMCPY_SRC   8
     66#define MEMCPY_SIZE  12
    6167
    6268/** Copy memory to/from userspace.
     
    6874 * or copy_to_uspace().
    6975 *
    70  * @param MEMCPY_DST(%esp)      Destination address.
    71  * @param MEMCPY_SRC(%esp)      Source address.
    72  * @param MEMCPY_SIZE(%esp)     Size.
     76 * @param MEMCPY_DST(%esp)  Destination address.
     77 * @param MEMCPY_SRC(%esp)  Source address.
     78 * @param MEMCPY_SIZE(%esp) Size.
    7379 *
    7480 * @return MEMCPY_DST(%esp) on success and 0 on failure.
     81 *
    7582 */
    7683memcpy:
    7784memcpy_from_uspace:
    7885memcpy_to_uspace:
    79         movl %edi, %edx                 /* save %edi */
    80         movl %esi, %eax                 /* save %esi */
     86        movl %edi, %edx  /* save %edi */
     87        movl %esi, %eax  /* save %esi */
    8188       
    8289        movl MEMCPY_SIZE(%esp), %ecx
    83         shrl $2, %ecx                   /* size / 4 */
     90        shrl $2, %ecx  /* size / 4 */
    8491       
    8592        movl MEMCPY_DST(%esp), %edi
    8693        movl MEMCPY_SRC(%esp), %esi
    8794       
    88         rep movsl                       /* copy whole words */
    89 
     95        /* Copy whole words */
     96        rep movsl
     97       
    9098        movl MEMCPY_SIZE(%esp), %ecx
    91         andl $3, %ecx                   /* size % 4 */
     99        andl $3, %ecx  /* size % 4 */
    92100        jz 0f
    93101       
    94         rep movsb                       /* copy the rest byte by byte */
    95 
    96 0:
    97         movl %edx, %edi
    98         movl %eax, %esi
    99         movl MEMCPY_DST(%esp), %eax     /* MEMCPY_DST(%esp), success */
    100         ret
    101        
     102        /* Copy the rest byte by byte */
     103        rep movsb
     104       
     105        0:
     106       
     107                movl %edx, %edi
     108                movl %eax, %esi
     109               
     110                /* MEMCPY_DST(%esp), success */
     111                movl MEMCPY_DST(%esp), %eax
     112                ret
     113
    102114/*
    103115 * We got here from as_page_fault() after the memory operations
     
    108120        movl %edx, %edi
    109121        movl %eax, %esi
    110         xorl %eax, %eax                 /* return 0, failure */
     122       
     123        /* Return 0, failure */
     124        xorl %eax, %eax
    111125        ret
    112126
    113 ## Turn paging on
    114 #
    115 # Enable paging and write-back caching in CR0.
    116 #
     127/** Turn paging on
     128 *
     129 * Enable paging and write-back caching in CR0.
     130 *
     131 */
    117132paging_on:
    118133        movl %cr0, %edx
    119         orl $(1 << 31), %edx            # paging on
    120         # clear Cache Disable and not Write Though
     134        orl $(1 << 31), %edx  /* paging on */
     135       
     136        /* Clear Cache Disable and not Write Though */
    121137        andl $~((1 << 30) | (1 << 29)), %edx
    122         movl %edx,%cr0
     138        movl %edx, %cr0
    123139        jmp 0f
    124 0:
    125         ret
    126 
    127 
    128 ## Enable local APIC
    129 #
    130 # Enable local APIC in MSR.
    131 #
     140       
     141        0:
     142                ret
     143
     144/** Enable local APIC
     145 *
     146 * Enable local APIC in MSR.
     147 *
     148 */
    132149enable_l_apic_in_msr:
    133150        movl $0x1b, %ecx
     
    138155        ret
    139156
    140 # Clear nested flag
    141 # overwrites %ecx
     157/** Clear nested flag
     158 *
     159 */
    142160.macro CLEAR_NT_FLAG
    143161        pushfl
    144162        andl $0xffffbfff, (%esp)
    145163        popfl
    146 .endm   
     164.endm
    147165
    148166/*
     
    158176sysenter_handler:
    159177        sti
    160         pushl %ebp      # remember user stack
    161         pushl %edi      # remember return user address
    162 
    163         xorl %ebp, %ebp # stop stack traces here
    164 
    165         pushl %gs       # remember TLS
    166 
    167         pushl %eax      # syscall number
    168         subl $8, %esp   # unused sixth and fifth argument
    169         pushl %esi      # fourth argument
    170         pushl %ebx      # third argument
    171         pushl %ecx      # second argument
    172         pushl %edx      # first argument
    173 
     178        pushl %ebp  /* remember user stack */
     179        pushl %edi  /* remember return user address */
     180       
     181        xorl %ebp, %ebp  /* stop stack traces here */
     182       
     183        pushl %gs  /* remember TLS */
     184       
     185        pushl %eax     /* syscall number */
     186        subl $8, %esp  /* unused sixth and fifth argument */
     187        pushl %esi     /* fourth argument */
     188        pushl %ebx     /* third argument */
     189        pushl %ecx     /* second argument */
     190        pushl %edx     /* first argument */
     191       
    174192        movw $16, %ax
    175193        movw %ax, %ds
    176194        movw %ax, %es
    177 
     195       
    178196        cld
    179197        call syscall_handler
    180         addl $28, %esp  # remove arguments from stack
    181 
    182         pop %gs         # restore TLS
    183 
    184         pop %edx        # prepare return EIP for SYSEXIT
    185         pop %ecx        # prepare userspace ESP for SYSEXIT
    186 
    187         sysexit         # return to userspace
    188 
    189 
    190 #define ISTATE_OFFSET_EAX               0
    191 #define ISTATE_OFFSET_EBX               4
    192 #define ISTATE_OFFSET_ECX               8
    193 #define ISTATE_OFFSET_EDX               12
    194 #define ISTATE_OFFSET_EDI               16
    195 #define ISTATE_OFFSET_ESI               20
    196 #define ISTATE_OFFSET_EBP               24
    197 #define ISTATE_OFFSET_EBP_FRAME         28
    198 #define ISTATE_OFFSET_EIP_FRAME         32
    199 #define ISTATE_OFFSET_GS                36
    200 #define ISTATE_OFFSET_FS                40
    201 #define ISTATE_OFFSET_ES                44
    202 #define ISTATE_OFFSET_DS                48
    203 #define ISTATE_OFFSET_ERROR_WORD        52
    204 #define ISTATE_OFFSET_EIP               56
    205 #define ISTATE_OFFSET_CS                60
    206 #define ISTATE_OFFSET_EFLAGS            64
    207 #define ISTATE_OFFSET_ESP               68
    208 #define ISTATE_OFFSET_SS                72
     198        addl $28, %esp  /* remove arguments from stack */
     199       
     200        pop %gs  /* restore TLS */
     201       
     202        pop %edx  /* prepare return EIP for SYSEXIT */
     203        pop %ecx  /* prepare userspace ESP for SYSEXIT */
     204       
     205        sysexit   /* return to userspace */
     206
     207#define ISTATE_OFFSET_EAX         0
     208#define ISTATE_OFFSET_EBX         4
     209#define ISTATE_OFFSET_ECX         8
     210#define ISTATE_OFFSET_EDX         12
     211#define ISTATE_OFFSET_EDI         16
     212#define ISTATE_OFFSET_ESI         20
     213#define ISTATE_OFFSET_EBP         24
     214#define ISTATE_OFFSET_EBP_FRAME   28
     215#define ISTATE_OFFSET_EIP_FRAME   32
     216#define ISTATE_OFFSET_GS          36
     217#define ISTATE_OFFSET_FS          40
     218#define ISTATE_OFFSET_ES          44
     219#define ISTATE_OFFSET_DS          48
     220#define ISTATE_OFFSET_ERROR_WORD  52
     221#define ISTATE_OFFSET_EIP         56
     222#define ISTATE_OFFSET_CS          60
     223#define ISTATE_OFFSET_EFLAGS      64
     224#define ISTATE_OFFSET_ESP         68
     225#define ISTATE_OFFSET_SS          72
    209226
    210227/*
    211  * Size of the istate structure without the hardware-saved part and without the
    212  * error word.
    213  */
    214 #define ISTATE_SOFT_SIZE                52
    215 
    216 ## Declare interrupt handlers
    217 #
    218 # Declare interrupt handlers for n interrupt
    219 # vectors starting at vector i.
    220 #
    221 # The handlers setup data segment registers
    222 # and call exc_dispatch().
    223 #
    224 #define INTERRUPT_ALIGN 256
     228 * Size of the istate structure without the hardware-saved part
     229 * and without the error word.
     230 */
     231#define ISTATE_SOFT_SIZE  52
     232
     233/** Declare interrupt handlers
     234 *
     235 * Declare interrupt handlers for n interrupt
     236 * vectors starting at vector i.
     237 *
     238 * The handlers setup data segment registers
     239 * and call exc_dispatch().
     240 *
     241 */
     242#define INTERRUPT_ALIGN  256
     243
    225244.macro handler i n
    226        
    227 .ifeq \i - 0x30     # Syscall handler
    228         pushl %ds
    229         pushl %es
    230         pushl %fs
    231         pushl %gs
    232                
    233         #
    234         # Push syscall arguments onto the stack
    235         #
    236         # NOTE: The idea behind the order of arguments passed in registers is to
    237         #       use all scratch registers first and preserved registers next.
    238         #       An optimized libc syscall wrapper can make use of this setup.
    239         #
    240         pushl %eax
    241         pushl %ebp
    242         pushl %edi
    243         pushl %esi
    244         pushl %ebx
    245         pushl %ecx
    246         pushl %edx
    247                
    248         # we must fill the data segment registers
    249         movw $16, %ax
    250         movw %ax, %ds
    251         movw %ax, %es
    252        
    253         xorl %ebp, %ebp
    254 
    255         cld
    256         sti
    257         # syscall_handler(edx, ecx, ebx, esi, edi, ebp, eax)
    258         call syscall_handler
    259         cli
    260 
    261         movl 20(%esp), %ebp     # restore EBP
    262         addl $28, %esp          # clean-up of parameters
    263                
    264         popl %gs
    265         popl %fs
    266         popl %es
    267         popl %ds
    268                
    269         CLEAR_NT_FLAG
    270         iret
    271 .else
    272         /*
    273          * This macro distinguishes between two versions of ia32 exceptions.
    274          * One version has error word and the other does not have it.
    275          * The latter version fakes the error word on the stack so that the
    276          * handlers and istate_t can be the same for both types.
    277          */
    278 .iflt \i - 32
    279 .if (1 << \i) & ERROR_WORD_INTERRUPT_LIST
    280         #
    281         # Exception with error word: do nothing
    282         #
    283 .else
    284         #
    285         # Exception without error word: fake up one
    286         #
    287         pushl $0
    288 .endif
    289 .else
    290         #
    291         # Interrupt: fake up one
    292         #
    293         pushl $0
    294 .endif
    295                
    296         subl $ISTATE_SOFT_SIZE, %esp
    297 
    298         #
    299         # Save the general purpose registers.
    300         #
    301         movl %eax, ISTATE_OFFSET_EAX(%esp)
    302         movl %ebx, ISTATE_OFFSET_EBX(%esp)
    303         movl %ecx, ISTATE_OFFSET_ECX(%esp)
    304         movl %edx, ISTATE_OFFSET_EDX(%esp)
    305         movl %edi, ISTATE_OFFSET_EDI(%esp)
    306         movl %esi, ISTATE_OFFSET_ESI(%esp)
    307         movl %ebp, ISTATE_OFFSET_EBP(%esp)
    308        
    309         #
    310         # Save the selector registers.
    311         #
    312         movl %gs, %eax
    313         movl %fs, %ebx
    314         movl %es, %ecx
    315         movl %ds, %edx
    316 
    317         movl %eax, ISTATE_OFFSET_GS(%esp)
    318         movl %ebx, ISTATE_OFFSET_FS(%esp)
    319         movl %ecx, ISTATE_OFFSET_ES(%esp)
    320         movl %edx, ISTATE_OFFSET_DS(%esp)
    321 
    322         #
    323         # Switch to kernel selectors.
    324         #
    325         movl $16, %eax
    326         movl %eax, %ds
    327         movl %eax, %es
    328                
    329         #
    330         # Imitate a regular stack frame linkage.
    331         # Stop stack traces here if we came from userspace.
    332         #
    333         cmpl $8, ISTATE_OFFSET_CS(%esp)
    334         jz 0f
    335         xorl %ebp, %ebp
    336 0:      movl %ebp, ISTATE_OFFSET_EBP_FRAME(%esp)
    337         movl ISTATE_OFFSET_EIP(%esp), %eax
    338         movl %eax, ISTATE_OFFSET_EIP_FRAME(%esp)
    339         leal ISTATE_OFFSET_EBP_FRAME(%esp), %ebp
    340 
    341         cld
    342 
    343         pushl %esp          # pass istate address
    344         pushl $(\i)         # pass intnum
    345         call exc_dispatch   # exc_dispatch(intnum, istate)
    346         addl $8, %esp       # Clear arguments from the stack
    347                
    348         CLEAR_NT_FLAG
    349        
    350         #
    351         # Restore the selector registers.
    352         #
    353         movl ISTATE_OFFSET_GS(%esp), %eax
    354         movl ISTATE_OFFSET_FS(%esp), %ebx
    355         movl ISTATE_OFFSET_ES(%esp), %ecx
    356         movl ISTATE_OFFSET_DS(%esp), %edx
    357 
    358         movl %eax, %gs
    359         movl %ebx, %fs
    360         movl %ecx, %es
    361         movl %edx, %ds
    362 
    363         #
    364         # Restore the scratch registers and the preserved registers the handler
    365         # cloberred itself (i.e. EBX and EBP).
    366         #
    367         movl ISTATE_OFFSET_EAX(%esp), %eax
    368         movl ISTATE_OFFSET_EBX(%esp), %ebx
    369         movl ISTATE_OFFSET_ECX(%esp), %ecx
    370         movl ISTATE_OFFSET_EDX(%esp), %edx
    371         movl ISTATE_OFFSET_EBP(%esp), %ebp
    372        
    373         addl $(ISTATE_SOFT_SIZE + 4), %esp
    374         iret
    375 .endif
    376        
    377 .align INTERRUPT_ALIGN
    378 .if (\n- \i) - 1
    379         handler "(\i + 1)", \n
    380 .endif
     245        .ifeq \i - 0x30
     246                /* Syscall handler */
     247                pushl %ds
     248                pushl %es
     249                pushl %fs
     250                pushl %gs
     251               
     252                /*
     253                 * Push syscall arguments onto the stack
     254                 *
     255                 * NOTE: The idea behind the order of arguments passed
     256                 *       in registers is to use all scratch registers
     257                 *       first and preserved registers next. An optimized
     258                 *       libc syscall wrapper can make use of this setup.
     259                 *
     260                 */
     261                pushl %eax
     262                pushl %ebp
     263                pushl %edi
     264                pushl %esi
     265                pushl %ebx
     266                pushl %ecx
     267                pushl %edx
     268               
     269                /* We must fill the data segment registers */
     270                movw $16, %ax
     271                movw %ax, %ds
     272                movw %ax, %es
     273               
     274                xorl %ebp, %ebp
     275               
     276                cld
     277                sti
     278               
     279                /* Call syscall_handler(edx, ecx, ebx, esi, edi, ebp, eax) */
     280                call syscall_handler
     281                cli
     282               
     283                movl 20(%esp), %ebp  /* restore EBP */
     284                addl $28, %esp       /* clean-up of parameters */
     285               
     286                popl %gs
     287                popl %fs
     288                popl %es
     289                popl %ds
     290               
     291                CLEAR_NT_FLAG
     292                iret
     293        .else
     294                /*
     295                 * This macro distinguishes between two versions of ia32
     296                 * exceptions. One version has error word and the other
     297                 * does not have it. The latter version fakes the error
     298                 * word on the stack so that the handlers and istate_t
     299                 * can be the same for both types.
     300                 */
     301                .iflt \i - 32
     302                        .if (1 << \i) & ERROR_WORD_INTERRUPT_LIST
     303                                /*
     304                                 * Exception with error word: do nothing
     305                                 */
     306                        .else
     307                                /*
     308                                 * Exception without error word: fake up one
     309                                 */
     310                                pushl $0
     311                        .endif
     312                .else
     313                        /*
     314                         * Interrupt: fake up one
     315                         */
     316                        pushl $0
     317                .endif
     318               
     319                subl $ISTATE_SOFT_SIZE, %esp
     320               
     321                /*
     322                 * Save the general purpose registers.
     323                 */
     324                movl %eax, ISTATE_OFFSET_EAX(%esp)
     325                movl %ebx, ISTATE_OFFSET_EBX(%esp)
     326                movl %ecx, ISTATE_OFFSET_ECX(%esp)
     327                movl %edx, ISTATE_OFFSET_EDX(%esp)
     328                movl %edi, ISTATE_OFFSET_EDI(%esp)
     329                movl %esi, ISTATE_OFFSET_ESI(%esp)
     330                movl %ebp, ISTATE_OFFSET_EBP(%esp)
     331               
     332                /*
     333                 * Save the selector registers.
     334                 */
     335                movl %gs, %eax
     336                movl %fs, %ebx
     337                movl %es, %ecx
     338                movl %ds, %edx
     339               
     340                movl %eax, ISTATE_OFFSET_GS(%esp)
     341                movl %ebx, ISTATE_OFFSET_FS(%esp)
     342                movl %ecx, ISTATE_OFFSET_ES(%esp)
     343                movl %edx, ISTATE_OFFSET_DS(%esp)
     344               
     345                /*
     346                 * Switch to kernel selectors.
     347                 */
     348                movl $16, %eax
     349                movl %eax, %ds
     350                movl %eax, %es
     351               
     352                /*
     353                 * Imitate a regular stack frame linkage.
     354                 * Stop stack traces here if we came from userspace.
     355                 */
     356                cmpl $8, ISTATE_OFFSET_CS(%esp)
     357                jz 0f
     358                xorl %ebp, %ebp
     359               
     360                0:
     361               
     362                        movl %ebp, ISTATE_OFFSET_EBP_FRAME(%esp)
     363                        movl ISTATE_OFFSET_EIP(%esp), %eax
     364                        movl %eax, ISTATE_OFFSET_EIP_FRAME(%esp)
     365                        leal ISTATE_OFFSET_EBP_FRAME(%esp), %ebp
     366                       
     367                        cld
     368                       
     369                        pushl %esp   /* pass istate address */
     370                        pushl $(\i)  /* pass intnum */
     371                       
     372                        /* Call exc_dispatch(intnum, istate) */
     373                        call exc_dispatch
     374                       
     375                        addl $8, %esp  /* clear arguments from the stack */
     376                       
     377                        CLEAR_NT_FLAG
     378                       
     379                        /*
     380                         * Restore the selector registers.
     381                         */
     382                        movl ISTATE_OFFSET_GS(%esp), %eax
     383                        movl ISTATE_OFFSET_FS(%esp), %ebx
     384                        movl ISTATE_OFFSET_ES(%esp), %ecx
     385                        movl ISTATE_OFFSET_DS(%esp), %edx
     386                       
     387                        movl %eax, %gs
     388                        movl %ebx, %fs
     389                        movl %ecx, %es
     390                        movl %edx, %ds
     391                       
     392                        /*
     393                         * Restore the scratch registers and the preserved
     394                         * registers the handler cloberred itself
     395                         * (i.e. EBX and EBP).
     396                         */
     397                        movl ISTATE_OFFSET_EAX(%esp), %eax
     398                        movl ISTATE_OFFSET_EBX(%esp), %ebx
     399                        movl ISTATE_OFFSET_ECX(%esp), %ecx
     400                        movl ISTATE_OFFSET_EDX(%esp), %edx
     401                        movl ISTATE_OFFSET_EBP(%esp), %ebp
     402                       
     403                        addl $(ISTATE_SOFT_SIZE + 4), %esp
     404                        iret
     405               
     406        .endif
     407       
     408        .align INTERRUPT_ALIGN
     409        .if (\n - \i) - 1
     410                handler "(\i + 1)", \n
     411        .endif
    381412.endm
    382413
    383 # keep in sync with pm.h !!!
    384 IDT_ITEMS = 64
     414/* Keep in sync with pm.h! */
     415#define IDT_ITEMS  64
     416
    385417.align INTERRUPT_ALIGN
    386418interrupt_handlers:
    387 h_start:
    388         handler 0 IDT_ITEMS
    389 h_end:
     419        h_start:
     420                handler 0 IDT_ITEMS
     421        h_end:
     422
     423/** Print Unicode character to EGA display.
     424 *
     425 * If CONFIG_EGA is undefined or CONFIG_FB is defined
     426 * then this function does nothing.
     427 *
     428 * Since the EGA can only display Extended ASCII (usually
     429 * ISO Latin 1) characters, some of the Unicode characters
     430 * can be displayed in a wrong way. Only the newline character
     431 * is interpreted, all other characters (even unprintable) are
     432 * printed verbatim.
     433 *
     434 * @param %ebp+0x08 Unicode character to be printed.
     435 *
     436 */
     437early_putchar:
     438       
     439#if ((defined(CONFIG_EGA)) && (!defined(CONFIG_FB)))
     440       
     441        /* Prologue, save preserved registers */
     442        pushl %ebp
     443        movl %esp, %ebp
     444        pushl %ebx
     445        pushl %esi
     446        pushl %edi
     447       
     448        movl $(PA2KA(0xb8000)), %edi  /* base of EGA text mode memory */
     449        xorl %eax, %eax
     450       
     451        /* Read bits 8 - 15 of the cursor address */
     452        movw $0x3d4, %dx
     453        movb $0xe, %al
     454        outb %al, %dx
     455       
     456        movw $0x3d5, %dx
     457        inb %dx, %al
     458        shl $8, %ax
     459       
     460        /* Read bits 0 - 7 of the cursor address */
     461        movw $0x3d4, %dx
     462        movb $0xf, %al
     463        outb %al, %dx
     464       
     465        movw $0x3d5, %dx
     466        inb %dx, %al
     467       
     468        /* Sanity check for the cursor on screen */
     469        cmp $2000, %ax
     470        jb early_putchar_cursor_ok
     471       
     472                movw $1998, %ax
     473       
     474        early_putchar_cursor_ok:
     475       
     476        movw %ax, %bx
     477        shl $1, %eax
     478        addl %eax, %edi
     479       
     480        movl 0x08(%ebp), %eax
     481       
     482        cmp $0x0a, %al
     483        jne early_putchar_print
     484       
     485                /* Interpret newline */
     486               
     487                movw %bx, %ax  /* %bx -> %dx:%ax */
     488                xorw %dx, %dx
     489               
     490                movw $80, %cx
     491                idivw %cx, %ax  /* %dx = %bx % 80 */
     492               
     493                /* %bx <- %bx + 80 - (%bx % 80) */
     494                addw %cx, %bx
     495                subw %dx, %bx
     496               
     497                jmp early_putchar_newline
     498       
     499        early_putchar_print:
     500       
     501                /* Print character */
     502               
     503                movb $0x0e, %ah  /* black background, yellow foreground */
     504                stosw
     505                inc %bx
     506       
     507        early_putchar_newline:
     508       
     509        /* Sanity check for the cursor on the last line */
     510        cmp $2000, %bx
     511        jb early_putchar_no_scroll
     512       
     513                /* Scroll the screen (24 rows) */
     514                movl $(PA2KA(0xb80a0)), %esi
     515                movl $(PA2KA(0xb8000)), %edi
     516                movl $1920, %ecx
     517                rep movsw
     518               
     519                /* Clear the 24th row */
     520                xorl %eax, %eax
     521                movl $80, %ecx
     522                rep stosw
     523               
     524                /* Go to row 24 */
     525                movw $1920, %bx
     526       
     527        early_putchar_no_scroll:
     528       
     529        /* Write bits 8 - 15 of the cursor address */
     530        movw $0x3d4, %dx
     531        movb $0xe, %al
     532        outb %al, %dx
     533       
     534        movw $0x3d5, %dx
     535        movb %bh, %al
     536        outb %al, %dx
     537       
     538        /* Write bits 0 - 7 of the cursor address */
     539        movw $0x3d4, %dx
     540        movb $0xf, %al
     541        outb %al, %dx
     542       
     543        movw $0x3d5, %dx
     544        movb %bl, %al
     545        outb %al, %dx
     546       
     547        /* Epilogue, restore preserved registers */
     548        popl %edi
     549        popl %esi
     550        popl %ebx
     551        leave
     552       
     553#endif
     554       
     555        ret
    390556
    391557.data
  • kernel/arch/ia32/src/boot/boot.S

    r4d1be48 re2ea4ab1  
    1 #
    2 # Copyright (c) 2001-2004 Jakub Jermar
    3 # Copyright (c) 2005-2006 Martin Decky
    4 # All rights reserved.
    5 #
    6 # Redistribution and use in source and binary forms, with or without
    7 # modification, are permitted provided that the following conditions
    8 # are met:
    9 #
    10 # - Redistributions of source code must retain the above copyright
    11 #   notice, this list of conditions and the following disclaimer.
    12 # - Redistributions in binary form must reproduce the above copyright
    13 #   notice, this list of conditions and the following disclaimer in the
    14 #   documentation and/or other materials provided with the distribution.
    15 # - The name of the author may not be used to endorse or promote products
    16 #   derived from this software without specific prior written permission.
    17 #
    18 # THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
    19 # IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
    20 # OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
    21 # IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
    22 # INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
    23 # NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
    24 # DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
    25 # THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
    26 # (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
    27 # THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
    28 #
     1/*
     2 * Copyright (c) 2001 Jakub Jermar
     3 * Copyright (c) 2005 Martin Decky
     4 * All rights reserved.
     5 *
     6 * Redistribution and use in source and binary forms, with or without
     7 * modification, are permitted provided that the following conditions
     8 * are met:
     9 *
     10 * - Redistributions of source code must retain the above copyright
     11 *   notice, this list of conditions and the following disclaimer.
     12 * - Redistributions in binary form must reproduce the above copyright
     13 *   notice, this list of conditions and the following disclaimer in the
     14 *   documentation and/or other materials provided with the distribution.
     15 * - The name of the author may not be used to endorse or promote products
     16 *   derived from this software without specific prior written permission.
     17 *
     18 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
     19 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
     20 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
     21 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
     22 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
     23 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
     24 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
     25 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
     26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
     27 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     28 */
    2929
    3030#include <arch/boot/boot.h>
     
    3434#include <arch/cpuid.h>
    3535
    36 #define START_STACK (BOOT_OFFSET - BOOT_STACK_SIZE)
     36#define START_STACK  (BOOT_OFFSET - BOOT_STACK_SIZE)
    3737
    3838.section K_TEXT_START, "ax"
    3939
    4040.code32
     41
     42.macro pm_error msg
     43        movl \msg, %esi
     44        jmp pm_error_halt
     45.endm
     46
     47.macro pm_status msg
     48#ifdef CONFIG_EGA
     49        pushl %esi
     50        movl \msg, %esi
     51        call pm_early_puts
     52        popl %esi
     53#endif
     54.endm
     55
     56.macro pm2_status msg
     57        pushl \msg
     58        call early_puts
     59.endm
     60
    4161.align 4
    4262.global multiboot_image_start
     
    4464        .long MULTIBOOT_HEADER_MAGIC
    4565        .long MULTIBOOT_HEADER_FLAGS
    46         .long -(MULTIBOOT_HEADER_MAGIC + MULTIBOOT_HEADER_FLAGS)  # checksum
     66        .long -(MULTIBOOT_HEADER_MAGIC + MULTIBOOT_HEADER_FLAGS)  /* checksum */
    4767        .long multiboot_header
    4868        .long unmapped_ktext_start
     
    5373multiboot_image_start:
    5474        cld
    55         movl $START_STACK, %esp     # initialize stack pointer
    56         lgdt KA2PA(bootstrap_gdtr)  # initialize Global Descriptor Table register
    57        
     75       
     76        /* Initialize stack pointer */
     77        movl $START_STACK, %esp
     78       
     79        /* Initialize Global Descriptor Table register */
     80        lgdtl KA2PA(bootstrap_gdtr)
     81       
     82        /* Kernel data + stack */
    5883        movw $gdtselector(KDATA_DES), %cx
    5984        movw %cx, %es
    6085        movw %cx, %fs
    6186        movw %cx, %gs
    62         movw %cx, %ds               # kernel data + stack
     87        movw %cx, %ds
    6388        movw %cx, %ss
    6489       
     
    6691        multiboot_meeting_point:
    6792       
    68         movl %eax, grub_eax         # save parameters from GRUB
     93        /* Save GRUB arguments */
     94        movl %eax, grub_eax
    6995        movl %ebx, grub_ebx
     96       
     97        pm_status $status_prot
    7098       
    7199        movl $(INTEL_CPUID_LEVEL), %eax
    72100        cpuid
    73         cmp $0x0, %eax              # any function > 0?
     101        cmp $0x0, %eax  /* any function > 0? */
    74102        jbe pse_unsupported
    75103       
     
    80108       
    81109        pse_unsupported:
    82                 movl $pse_msg, %esi
    83                 jmp error_halt
     110               
     111                pm_error $err_pse
    84112       
    85113        pse_supported:
    86114       
    87115#include "vesa_prot.inc"
    88 
    89         # map kernel and turn paging on
     116       
     117        /* Map kernel and turn paging on */
    90118        call map_kernel
    91119       
    92         # call arch_pre_main(grub_eax, grub_ebx)
     120        /* Create the first stack frame */
     121        pushl $0
     122        movl %esp, %ebp
     123       
     124        pm2_status $status_prot2
     125       
     126        /* Call arch_pre_main(grub_eax, grub_ebx) */
    93127        pushl grub_ebx
    94128        pushl grub_eax
    95129        call arch_pre_main
    96 
    97         # Create the first stack frame
    98         pushl $0
    99         movl %esp, %ebp
    100        
     130       
     131        pm2_status $status_main
     132       
     133        /* Call main_bsp() */
    101134        call main_bsp
    102135       
    103         # not reached
     136        /* Not reached */
    104137        cli
    105138        hlt0:
     
    107140                jmp hlt0
    108141
     142/** Setup mapping for the kernel.
     143 *
     144 * Setup mapping for both the unmapped and mapped sections
     145 * of the kernel. For simplicity, we map the entire 4G space.
     146 *
     147 */
    109148.global map_kernel
    110149map_kernel:
    111         #
    112         # Here we setup mapping for both the unmapped and mapped sections of the kernel.
    113         # For simplicity, we map the entire 4G space.
    114         #
    115150        movl %cr4, %ecx
    116         orl $(1 << 4), %ecx                 # turn PSE on
    117         andl $(~(1 << 5)), %ecx             # turn PAE off
     151        orl $(1 << 4), %ecx      /* PSE on */
     152        andl $(~(1 << 5)), %ecx  /* PAE off */
    118153        movl %ecx, %cr4
    119154       
     
    126161                movl $((1 << 7) | (1 << 1) | (1 << 0)), %eax
    127162                orl %ebx, %eax
    128                 movl %eax, (%esi, %ecx, 4)      # mapping 0x00000000 + %ecx * 4M => 0x00000000 + %ecx * 4M
    129                 movl %eax, (%edi, %ecx, 4)      # mapping 0x80000000 + %ecx * 4M => 0x00000000 + %ecx * 4M
     163                /* Mapping 0x00000000 + %ecx * 4M => 0x00000000 + %ecx * 4M */
     164                movl %eax, (%esi, %ecx, 4)
     165                /* Mapping 0x80000000 + %ecx * 4M => 0x00000000 + %ecx * 4M */
     166                movl %eax, (%edi, %ecx, 4)
    130167                addl $(4 * 1024 * 1024), %ebx
    131168               
     
    137174       
    138175        movl %cr0, %ebx
    139         orl $(1 << 31), %ebx                # turn paging on
     176        orl $(1 << 31), %ebx  /* paging on */
    140177        movl %ebx, %cr0
    141178        ret
    142179
    143 # Print string from %esi to EGA display (in red) and halt
    144 error_halt:
    145         movl $0xb8000, %edi         # base of EGA text mode memory
     180/** Print string to EGA display (in light red) and halt.
     181 *
     182 * Should be executed from 32 bit protected mode with paging
     183 * turned off. Stack is not required. This routine is used even
     184 * if CONFIG_EGA is not enabled. Since we are going to halt the
     185 * CPU anyway, it is always better to at least try to print
     186 * some hints.
     187 *
     188 * @param %esi NULL-terminated string to print.
     189 *
     190 */
     191pm_error_halt:
     192        movl $0xb8000, %edi  /* base of EGA text mode memory */
    146193        xorl %eax, %eax
    147194       
    148         movw $0x3d4, %dx            # read bits 8 - 15 of the cursor address
     195        /* Read bits 8 - 15 of the cursor address */
     196        movw $0x3d4, %dx
    149197        movb $0xe, %al
    150198        outb %al, %dx
     
    154202        shl $8, %ax
    155203       
    156         movw $0x3d4, %dx            # read bits 0 - 7 of the cursor address
     204        /* Read bits 0 - 7 of the cursor address */
     205        movw $0x3d4, %dx
    157206        movb $0xf, %al
    158207        outb %al, %dx
     
    161210        inb %dx, %al
    162211       
    163         cmp $1920, %ax
    164         jbe cursor_ok
    165        
    166                 movw $1920, %ax         # sanity check for the cursor on the last line
    167        
    168         cursor_ok:
     212        /* Sanity check for the cursor on screen */
     213        cmp $2000, %ax
     214        jb err_cursor_ok
     215       
     216                movw $1998, %ax
     217       
     218        err_cursor_ok:
    169219       
    170220        movw %ax, %bx
     
    172222        addl %eax, %edi
    173223       
    174         movw $0x0c00, %ax           # black background, light red foreground
    175        
    176         ploop:
     224        err_ploop:
    177225                lodsb
     226               
    178227                cmp $0, %al
    179                 je ploop_end
     228                je err_ploop_end
     229               
     230                movb $0x0c, %ah  /* black background, light red foreground */
    180231                stosw
     232               
     233                /* Sanity check for the cursor on the last line */
    181234                inc %bx
    182                 jmp ploop
    183         ploop_end:
    184        
    185         movw $0x3d4, %dx            # write bits 8 - 15 of the cursor address
     235                cmp $2000, %bx
     236                jb err_ploop
     237               
     238                /* Scroll the screen (24 rows) */
     239                movl %esi, %edx
     240                movl $0xb80a0, %esi
     241                movl $0xb8000, %edi
     242                movl $1920, %ecx
     243                rep movsw
     244               
     245                /* Clear the 24th row */
     246                xorl %eax, %eax
     247                movl $80, %ecx
     248                rep stosw
     249               
     250                /* Go to row 24 */
     251                movl %edx, %esi
     252                movl $0xb8f00, %edi
     253                movw $1920, %bx
     254               
     255                jmp err_ploop
     256        err_ploop_end:
     257       
     258        /* Write bits 8 - 15 of the cursor address */
     259        movw $0x3d4, %dx
    186260        movb $0xe, %al
    187261        outb %al, %dx
     
    191265        outb %al, %dx
    192266       
    193         movw $0x3d4, %dx            # write bits 0 - 7 of the cursor address
     267        /* Write bits 0 - 7 of the cursor address */
     268        movw $0x3d4, %dx
    194269        movb $0xf, %al
    195270        outb %al, %dx
     
    204279                jmp hlt1
    205280
     281/** Print string to EGA display (in light green).
     282 *
     283 * Should be called from 32 bit protected mode with paging
     284 * turned off. A stack space of at least 24 bytes is required,
     285 * but the function does not establish a stack frame.
     286 *
     287 * Macros such as pm_status take care that this function
     288 * is used only when CONFIG_EGA is enabled.
     289 *
     290 * @param %esi NULL-terminated string to print.
     291 *
     292 */
     293pm_early_puts:
     294        pushl %eax
     295        pushl %ebx
     296        pushl %ecx
     297        pushl %edx
     298        pushl %edi
     299       
     300        movl $0xb8000, %edi  /* base of EGA text mode memory */
     301        xorl %eax, %eax
     302       
     303        /* Read bits 8 - 15 of the cursor address */
     304        movw $0x3d4, %dx
     305        movb $0xe, %al
     306        outb %al, %dx
     307       
     308        movw $0x3d5, %dx
     309        inb %dx, %al
     310        shl $8, %ax
     311       
     312        /* Read bits 0 - 7 of the cursor address */
     313        movw $0x3d4, %dx
     314        movb $0xf, %al
     315        outb %al, %dx
     316       
     317        movw $0x3d5, %dx
     318        inb %dx, %al
     319       
     320        /* Sanity check for the cursor on screen */
     321        cmp $2000, %ax
     322        jb pm_puts_cursor_ok
     323       
     324                movw $1998, %ax
     325       
     326        pm_puts_cursor_ok:
     327       
     328        movw %ax, %bx
     329        shl $1, %eax
     330        addl %eax, %edi
     331       
     332        pm_puts_ploop:
     333                lodsb
     334               
     335                cmp $0, %al
     336                je pm_puts_ploop_end
     337               
     338                movb $0x0a, %ah  /* black background, light green foreground */
     339                stosw
     340               
     341                /* Sanity check for the cursor on the last line */
     342                inc %bx
     343                cmp $2000, %bx
     344                jb pm_puts_ploop
     345               
     346                /* Scroll the screen (24 rows) */
     347                movl %esi, %edx
     348                movl $0xb80a0, %esi
     349                movl $0xb8000, %edi
     350                movl $1920, %ecx
     351                rep movsw
     352               
     353                /* Clear the 24th row */
     354                xorl %eax, %eax
     355                movl $80, %ecx
     356                rep stosw
     357               
     358                /* Go to row 24 */
     359                movl %edx, %esi
     360                movl $0xb8f00, %edi
     361                movw $1920, %bx
     362               
     363                jmp pm_puts_ploop
     364        pm_puts_ploop_end:
     365       
     366        /* Write bits 8 - 15 of the cursor address */
     367        movw $0x3d4, %dx
     368        movb $0xe, %al
     369        outb %al, %dx
     370       
     371        movw $0x3d5, %dx
     372        movb %bh, %al
     373        outb %al, %dx
     374       
     375        /* Write bits 0 - 7 of the cursor address */
     376        movw $0x3d4, %dx
     377        movb $0xf, %al
     378        outb %al, %dx
     379       
     380        movw $0x3d5, %dx
     381        movb %bl, %al
     382        outb %al, %dx
     383       
     384        popl %edi
     385        popl %edx
     386        popl %ecx
     387        popl %ebx
     388        popl %eax
     389       
     390        ret
     391
     392/** Print string to EGA display.
     393 *
     394 * Should be called from 32 bit protected mode (with paging
     395 * enabled and stack established). This function is ABI compliant.
     396 *
     397 * If CONFIG_EGA is undefined or CONFIG_FB is defined
     398 * then this function does nothing.
     399 *
     400 * @param %ebp+0x08 NULL-terminated string to print.
     401 *
     402 */
     403early_puts:
     404       
     405#if ((defined(CONFIG_EGA)) && (!defined(CONFIG_FB)))
     406       
     407        /* Prologue, save preserved registers */
     408        pushl %ebp
     409        movl %esp, %ebp
     410        pushl %ebx
     411        pushl %esi
     412        pushl %edi
     413       
     414        movl 0x08(%ebp), %esi
     415        movl $(PA2KA(0xb8000)), %edi  /* base of EGA text mode memory */
     416        xorl %eax, %eax
     417       
     418        /* Read bits 8 - 15 of the cursor address */
     419        movw $0x3d4, %dx
     420        movb $0xe, %al
     421        outb %al, %dx
     422       
     423        movw $0x3d5, %dx
     424        inb %dx, %al
     425        shl $8, %ax
     426       
     427        /* Read bits 0 - 7 of the cursor address */
     428        movw $0x3d4, %dx
     429        movb $0xf, %al
     430        outb %al, %dx
     431       
     432        movw $0x3d5, %dx
     433        inb %dx, %al
     434       
     435        /* Sanity check for the cursor on screen */
     436        cmp $2000, %ax
     437        jb early_puts_cursor_ok
     438       
     439                movw $1998, %ax
     440       
     441        early_puts_cursor_ok:
     442       
     443        movw %ax, %bx
     444        shl $1, %eax
     445        addl %eax, %edi
     446       
     447        early_puts_ploop:
     448                lodsb
     449               
     450                cmp $0, %al
     451                je early_puts_ploop_end
     452               
     453                movb $0x0e, %ah  /* black background, yellow foreground */
     454                stosw
     455               
     456                /* Sanity check for the cursor on the last line */
     457                inc %bx
     458                cmp $2000, %bx
     459                jb early_puts_ploop
     460               
     461                /* Scroll the screen (24 rows) */
     462                movl %esi, %edx
     463                movl $(PA2KA(0xb80a0)), %esi
     464                movl $(PA2KA(0xb8000)), %edi
     465                movl $1920, %ecx
     466                rep movsw
     467               
     468                /* Clear the 24th row */
     469                xorl %eax, %eax
     470                movl $80, %ecx
     471                rep stosw
     472               
     473                /* Go to row 24 */
     474                movl %edx, %esi
     475                movl $(PA2KA(0xb8f00)), %edi
     476                movw $1920, %bx
     477               
     478                jmp early_puts_ploop
     479        early_puts_ploop_end:
     480       
     481        /* Write bits 8 - 15 of the cursor address */
     482        movw $0x3d4, %dx
     483        movb $0xe, %al
     484        outb %al, %dx
     485       
     486        movw $0x3d5, %dx
     487        movb %bh, %al
     488        outb %al, %dx
     489       
     490        /* Write bits 0 - 7 of the cursor address */
     491        movw $0x3d4, %dx
     492        movb $0xf, %al
     493        outb %al, %dx
     494       
     495        movw $0x3d5, %dx
     496        movb %bl, %al
     497        outb %al, %dx
     498       
     499        /* Epilogue, restore preserved registers */
     500        popl %edi
     501        popl %esi
     502        popl %ebx
     503        leave
     504       
     505#endif
     506       
     507        ret
     508
    206509#include "vesa_real.inc"
    207510
     
    218521        .long 0
    219522
    220 pse_msg:
     523err_pse:
    221524        .asciz "Page Size Extension not supported. System halted."
    222525
     526status_prot:
     527        .asciz "[prot] "
     528status_vesa_copy:
     529        .asciz "[vesa_copy] "
     530status_grub_cmdline:
     531        .asciz "[grub_cmdline] "
     532status_vesa_real:
     533        .asciz "[vesa_real] "
     534status_prot2:
     535        .asciz "[prot2] "
     536status_main:
     537        .asciz "[main] "
  • kernel/arch/ia32/src/boot/vesa_prot.inc

    r4d1be48 re2ea4ab1  
    55#define MBINFO_OFFSET_CMDLINE   16
    66
    7         # copy real mode VESA initialization code
     7        /* Copy real mode VESA initialization code */
     8       
     9        pm_status $status_vesa_copy
    810       
    911        mov $vesa_init, %esi
     
    1214        rep movsb
    1315       
    14         # check for GRUB command line
     16        /* Check for GRUB command line */
     17       
     18        pm_status $status_grub_cmdline
    1519       
    1620        mov grub_eax, %eax
     
    2327        jnc no_cmdline
    2428       
    25         # skip the kernel path in command line
     29        /* Skip the kernel path in command line */
    2630       
    2731        mov MBINFO_OFFSET_CMDLINE(%ebx), %esi
     
    5256        space_loop_done:
    5357       
    54         # copy at most 23 characters from command line
     58        /* Copy at most 23 characters from command line */
    5559       
    5660        mov $VESA_INIT_SEGMENT << 4, %edi
     
    6872        cmd_loop_done:
    6973       
    70         # zero termination
     74        /* Zero termination */
    7175       
    7276        xor %eax, %eax
     
    7579        no_cmdline:
    7680       
    77         # jump to the real mode
     81        /* Jump to the real mode */
     82       
     83        pm_status $status_vesa_real
    7884       
    7985        mov $VESA_INIT_SEGMENT << 4, %edi
     
    8187       
    8288        vesa_meeting_point:
    83                 # returned back to protected mode
     89                /* Returned back to protected mode */
    8490               
    8591                mov %ax, KA2PA(vesa_scanline)
  • kernel/arch/ia32/src/boot/vesa_real.inc

    r4d1be48 re2ea4ab1  
    3131vesa_init:
    3232        jmp $gdtselector(VESA_INIT_DES), $vesa_init_real - vesa_init
    33        
     33
    3434.code16
    3535vesa_init_real:
     
    5555        pushl %eax
    5656       
    57         # parse default mode string
     57        /* Parse default mode string */
    5858       
    5959        mov $default_mode - vesa_init, %di
     
    6565                mov (%di), %al
    6666               
    67                 # check for digit
     67                /* Check for digit */
    6868               
    6969                cmp $'0', %al
     
    7575                sub $'0', %al
    7676               
    77                 # multiply default_width by 10 and add digit
     77                /* Multiply default_width by 10 and add digit */
    7878               
    7979                mov default_width - vesa_init, %bx
     
    9696                mov (%di), %al
    9797               
    98                 # check for digit
     98                /* Check for digit */
    9999               
    100100                cmp $'0', %al
     
    106106                sub $'0', %al
    107107               
    108                 # multiply default_height by 10 and add digit
     108                /* Multiply default_height by 10 and add digit */
    109109               
    110110                mov default_height - vesa_init, %bx
     
    127127                mov (%di), %al
    128128               
    129                 # check for digit
     129                /* Check for digit */
    130130               
    131131                cmp $'0', %al
     
    137137                sub $'0', %al
    138138               
    139                 # multiply default_bpp by 10 and add digit
     139                /* Multiply default_bpp by 10 and add digit */
    140140               
    141141                mov default_bpp - vesa_init, %bx
     
    167167       
    168168        next_mode:
    169                 # try next mode
     169                /* Try next mode */
     170               
    170171                mov %gs:(%si), %cx
    171172                cmp $VESA_END_OF_MODES, %cx
     
    186187                jne no_mode
    187188               
    188                 # check for proper attributes (supported, color, graphics, linear framebuffer)
     189                /*
     190                 * Check for proper attributes (supported,
     191                 * color, graphics, linear framebuffer).
     192                 */
    189193               
    190194                mov VESA_MODE_ATTRIBUTES_OFFSET(%di), %ax
     
    193197                jne next_mode
    194198               
    195                 # check for proper resolution
     199                /* Check for proper resolution */
    196200               
    197201                mov default_width - vesa_init, %ax
     
    203207                jne next_mode
    204208               
    205                 # check for proper bpp
     209                /* Check for proper bpp */
    206210               
    207211                mov default_bpp - vesa_init, %al
     
    213217                jne next_mode
    214218               
    215                 # for 24 bpp modes accept also 32 bit bpp
     219                /* For 24 bpp modes accept also 32 bit bpp */
    216220               
    217221                mov $32, %al
     
    230234                jnz no_mode
    231235               
    232                 # set 3:2:3 VGA palette
     236                /* Set 3:2:3 VGA palette */
    233237               
    234238                mov VESA_MODE_BPP_OFFSET(%di), %al
     
    241245                mov $0x100, %ecx
    242246               
    243                 bt $5, %ax              # test if VGA compatible registers are present
     247                /* Test if VGA compatible registers are present */
     248                bt $5, %ax
    244249                jnc vga_compat
    245250               
    246                         # try VESA routine to set palette
     251                        /* Use VESA routine to set the palette */
     252                       
    247253                        mov $VESA_SET_PALETTE, %ax
    248254                        xor %bl, %bl
     
    254260               
    255261                vga_compat:
    256                         # try VGA registers to set palette
    257                         movw $0x3c6, %dx    # set palette mask
     262                       
     263                        /* Use VGA registers to set the palette */
     264                       
     265                        movw $0x3c6, %dx  /* set palette mask */
    258266                        movb $0xff, %al
    259267                        outb %al, %dx
    260268                       
    261                         movw $0x3c8, %dx    # first index to set
     269                        movw $0x3c8, %dx  /* first index to set */
    262270                        xor %al, %al
    263271                        outb %al, %dx
    264272                       
    265                         movw $0x3c9, %dx    # data port
     273                        movw $0x3c9, %dx  /* data port */
    266274                       
    267275                        vga_loop:
     
    284292                vga_not_set:
    285293               
    286                 # store mode parameters
    287                 #  eax = bpp[8] scanline[16]
    288                 #  ebx = width[16]  height[16]
    289                 #  edx = red_mask[8] red_pos[8] green_mask[8] green_pos[8]
    290                 #  esi = blue_mask[8] blue_pos[8]
    291                 #  edi = linear frame buffer
     294                /*
     295                 * Store mode parameters:
     296                 *  eax = bpp[8] scanline[16]
     297                 *  ebx = width[16]  height[16]
     298                 *  edx = red_mask[8] red_pos[8] green_mask[8] green_pos[8]
     299                 *  esi = blue_mask[8] blue_pos[8]
     300                 *  edi = linear frame buffer
     301                 */
    292302               
    293303                mov VESA_MODE_BPP_OFFSET(%di), %al
     
    328338       
    329339        no_mode:
    330                 # no prefered mode found
     340               
     341                /* No prefered mode found */
     342               
    331343                mov $0x111, %cx
    332344                push %di
     
    339351                cmp $VESA_OK, %al
    340352                jnz text_mode
    341                 jz set_mode             # force relative jump
     353                jz set_mode  /* force relative jump */
    342354       
    343355        text_mode:
    344                 # reset to EGA text mode (because of problems with VESA)
     356               
     357                /* Reset to EGA text mode (because of problems with VESA) */
     358               
    345359                mov $0x0003, %ax
    346360                int $0x10
    347361                mov $0xffffffff, %edi
    348362                xor %ax, %ax
    349                 jz vesa_leave_real      # force relative jump
     363                jz vesa_leave_real  /* force relative jump */
    350364
    351365vga323:
  • kernel/arch/ia32/src/boot/vesa_ret.inc

    r4d1be48 re2ea4ab1  
    11.code32
    22vesa_init_protected:
     3        cld
     4       
     5        /* Initialize stack pointer */
     6        movl $START_STACK, %esp
     7       
     8        /* Kernel data + stack */
    39        movw $gdtselector(KDATA_DES), %cx
    410        movw %cx, %es
    511        movw %cx, %fs
    612        movw %cx, %gs
    7         movw %cx, %ds               # kernel data + stack
     13        movw %cx, %ds
    814        movw %cx, %ss
    915       
    10         movl $START_STACK, %esp     # initialize stack pointer
    11        
    1216        jmpl $gdtselector(KTEXT_DES), $vesa_meeting_point
  • kernel/arch/ia32/src/smp/apic.c

    r4d1be48 re2ea4ab1  
    7676
    7777uint32_t apic_id_mask = 0;
     78uint8_t bsp_l_apic = 0;
     79
    7880static irq_t l_apic_timer_irq;
    7981
     
    154156}
    155157
     158/** Get Local APIC ID.
     159 *
     160 * @return Local APIC ID.
     161 *
     162 */
     163static uint8_t l_apic_id(void)
     164{
     165        l_apic_id_t idreg;
     166       
     167        idreg.value = l_apic[L_APIC_ID];
     168        return idreg.apic_id;
     169}
     170
    156171/** Initialize APIC on BSP. */
    157172void apic_init(void)
     
    208223        l_apic_init();
    209224        l_apic_debug();
     225       
     226        bsp_l_apic = l_apic_id();
    210227}
    211228
     
    460477{
    461478#ifdef LAPIC_VERBOSE
    462         printf("LVT on cpu%" PRIs ", LAPIC ID: %" PRIu8 "\n", CPU->id, l_apic_id());
     479        printf("LVT on cpu%" PRIs ", LAPIC ID: %" PRIu8 "\n",
     480            CPU->id, l_apic_id());
    463481       
    464482        lvt_tm_t tm;
    465483        tm.value = l_apic[LVT_Tm];
    466         printf("LVT Tm: vector=%hhd, %s, %s, %s\n", tm.vector, delivs_str[tm.delivs], mask_str[tm.masked], tm_mode_str[tm.mode]);
     484        printf("LVT Tm: vector=%" PRIu8 ", %s, %s, %s\n",
     485            tm.vector, delivs_str[tm.delivs], mask_str[tm.masked],
     486            tm_mode_str[tm.mode]);
    467487       
    468488        lvt_lint_t lint;
    469489        lint.value = l_apic[LVT_LINT0];
    470         printf("LVT LINT0: vector=%hhd, %s, %s, %s, irr=%d, %s, %s\n", tm.vector, delmod_str[lint.delmod], delivs_str[lint.delivs], intpol_str[lint.intpol], lint.irr, trigmod_str[lint.trigger_mode], mask_str[lint.masked]);
    471         lint.value = l_apic[LVT_LINT1];
    472         printf("LVT LINT1: vector=%hhd, %s, %s, %s, irr=%d, %s, %s\n", tm.vector, delmod_str[lint.delmod], delivs_str[lint.delivs], intpol_str[lint.intpol], lint.irr, trigmod_str[lint.trigger_mode], mask_str[lint.masked]); 
     490        printf("LVT LINT0: vector=%" PRIu8 ", %s, %s, %s, irr=%u, %s, %s\n",
     491            tm.vector, delmod_str[lint.delmod], delivs_str[lint.delivs],
     492            intpol_str[lint.intpol], lint.irr, trigmod_str[lint.trigger_mode],
     493            mask_str[lint.masked]);
     494       
     495        lint.value = l_apic[LVT_LINT1];
     496        printf("LVT LINT1: vector=%" PRIu8 ", %s, %s, %s, irr=%u, %s, %s\n",
     497            tm.vector, delmod_str[lint.delmod], delivs_str[lint.delivs],
     498            intpol_str[lint.intpol], lint.irr, trigmod_str[lint.trigger_mode],
     499            mask_str[lint.masked]);
    473500       
    474501        lvt_error_t error;
    475502        error.value = l_apic[LVT_Err];
    476         printf("LVT Err: vector=%hhd, %s, %s\n", error.vector, delivs_str[error.delivs], mask_str[error.masked]);
     503        printf("LVT Err: vector=%" PRIu8 ", %s, %s\n", error.vector,
     504            delivs_str[error.delivs], mask_str[error.masked]);
    477505#endif
    478 }
    479 
    480 /** Get Local APIC ID.
    481  *
    482  * @return Local APIC ID.
    483  *
    484  */
    485 uint8_t l_apic_id(void)
    486 {
    487         l_apic_id_t idreg;
    488        
    489         idreg.value = l_apic[L_APIC_ID];
    490         return idreg.apic_id;
    491506}
    492507
  • kernel/arch/ia32/src/smp/mps.c

    r4d1be48 re2ea4ab1  
    7272static size_t l_intr_entry_cnt = 0;
    7373
    74 static uint8_t get_cpu_apic_id(size_t i)
     74static uint8_t mps_cpu_apic_id(size_t i)
    7575{
    7676        ASSERT(i < processor_entry_cnt);
     
    7979}
    8080
    81 static bool is_cpu_enabled(size_t i)
     81static bool mps_cpu_enabled(size_t i)
    8282{
    8383        ASSERT(i < processor_entry_cnt);
     
    8585        /*
    8686         * FIXME: The current local APIC driver limits usable
    87          * APIC IDs to 8.
     87         * CPU IDs to 8.
    8888         *
    8989         */
    90         if (get_cpu_apic_id(i) > 7)
     90        if (i > 7)
    9191                return false;
    9292       
     
    9494}
    9595
    96 static bool is_bsp(size_t i)
     96static bool mps_cpu_bootstrap(size_t i)
    9797{
    9898        ASSERT(i < processor_entry_cnt);
     
    118118 */
    119119struct smp_config_operations mps_config_operations = {
    120         .cpu_enabled = is_cpu_enabled,
    121         .cpu_bootstrap = is_bsp,
    122         .cpu_apic_id = get_cpu_apic_id,
     120        .cpu_enabled = mps_cpu_enabled,
     121        .cpu_bootstrap = mps_cpu_bootstrap,
     122        .cpu_apic_id = mps_cpu_apic_id,
    123123        .irq_to_pin = mps_irq_to_pin
    124124};
  • kernel/arch/ia32/src/smp/smp.c

    r4d1be48 re2ea4ab1  
    6262void smp_init(void)
    6363{
    64         uintptr_t l_apic_address;
    65         uintptr_t io_apic_address;
    66        
    6764        if (acpi_madt) {
    6865                acpi_madt_parse();
     
    7572        }
    7673       
    77         l_apic_address = (uintptr_t) frame_alloc(ONE_FRAME,
    78             FRAME_ATOMIC | FRAME_KA);
    79         if (!l_apic_address)
    80                 panic("Cannot allocate address for l_apic.");
    81        
    82         io_apic_address = (uintptr_t) frame_alloc(ONE_FRAME,
    83             FRAME_ATOMIC | FRAME_KA);
    84         if (!io_apic_address)
    85                 panic("Cannot allocate address for io_apic.");
    86        
    8774        if (config.cpu_count > 1) {
    88                 page_table_lock(AS_KERNEL, true);
    89                 page_mapping_insert(AS_KERNEL, l_apic_address,
    90                     (uintptr_t) l_apic, PAGE_NOT_CACHEABLE | PAGE_WRITE);
    91                 page_mapping_insert(AS_KERNEL, io_apic_address,
    92                     (uintptr_t) io_apic, PAGE_NOT_CACHEABLE | PAGE_WRITE);
    93                 page_table_unlock(AS_KERNEL, true);
    94                
    95                 l_apic = (uint32_t *) l_apic_address;
    96                 io_apic = (uint32_t *) io_apic_address;
     75                l_apic = (uint32_t *) hw_map((uintptr_t) l_apic, PAGE_SIZE);
     76                io_apic = (uint32_t *) hw_map((uintptr_t) io_apic, PAGE_SIZE);
    9777        }
    9878}
     
    133113        apic_init();
    134114       
    135         uint8_t apic = l_apic_id();
    136        
    137115        for (i = 0; i < config.cpu_count; i++) {
    138116                /*
     
    148126                        continue;
    149127               
    150                 if (ops->cpu_apic_id(i) == apic) {
    151                         printf("%s: bad processor entry #%u, will not send IPI "
    152                             "to myself\n", __FUNCTION__, i);
     128                if (ops->cpu_apic_id(i) == bsp_l_apic) {
     129                        printf("kmp: bad processor entry #%u, will not send IPI "
     130                            "to myself\n", i);
    153131                        continue;
    154132                }
  • kernel/arch/ia64/src/asm.S

    r4d1be48 re2ea4ab1  
    1 #
    2 # Copyright (c) 2005 Jakub Jermar
    3 # All rights reserved.
    4 #
    5 # Redistribution and use in source and binary forms, with or without
    6 # modification, are permitted provided that the following conditions
    7 # are met:
    8 #
    9 # - Redistributions of source code must retain the above copyright
    10 #   notice, this list of conditions and the following disclaimer.
    11 # - Redistributions in binary form must reproduce the above copyright
    12 #   notice, this list of conditions and the following disclaimer in the
    13 #   documentation and/or other materials provided with the distribution.
    14 # - The name of the author may not be used to endorse or promote products
    15 #   derived from this software without specific prior written permission.
    16 #
    17 # THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
    18 # IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
    19 # OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
    20 # IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
    21 # INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
    22 # NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
    23 # DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
    24 # THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
    25 # (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
    26 # THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
    27 #
     1/*
     2 * Copyright (c) 2005 Jakub Jermar
     3 * All rights reserved.
     4 *
     5 * Redistribution and use in source and binary forms, with or without
     6 * modification, are permitted provided that the following conditions
     7 * are met:
     8 *
     9 * - Redistributions of source code must retain the above copyright
     10 *   notice, this list of conditions and the following disclaimer.
     11 * - Redistributions in binary form must reproduce the above copyright
     12 *   notice, this list of conditions and the following disclaimer in the
     13 *   documentation and/or other materials provided with the distribution.
     14 * - The name of the author may not be used to endorse or promote products
     15 *   derived from this software without specific prior written permission.
     16 *
     17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
     18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
     19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
     20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
     21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
     22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
     23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
     24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
     25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
     26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     27 */
    2828
    2929#include <arch/register.h>
    3030
    3131.text
    32 
    33 /** Copy memory from/to userspace.
    34  *
    35  * This memcpy() has been taken from the assembler output of
    36  * the generic _memcpy() and modified to have the failover part.
    37  *
    38  * @param in0 Destination address.
    39  * @param in1 Source address.
    40  * @param in2 Number of byte to copy.
    41  */
    4232.global memcpy
    4333.global memcpy_from_uspace
     
    4535.global memcpy_from_uspace_failover_address
    4636.global memcpy_to_uspace_failover_address
     37
     38/** Copy memory from/to userspace.
     39 *
     40 * This memcpy() has been taken from the assembler output of
     41 * the generic _memcpy() and modified to have the failover part.
     42 *
     43 * @param in0 Destination address.
     44 * @param in1 Source address.
     45 * @param in2 Number of byte to copy.
     46 *
     47 */
    4748memcpy:
    4849memcpy_from_uspace:
    4950memcpy_to_uspace:
    5051        alloc loc0 = ar.pfs, 3, 1, 0, 0
    51 
     52       
    5253        adds r14 = 7, in1
    5354        mov r2 = ar.lc
     
    5556        and r14 = -8, r14 ;;
    5657        cmp.ne p6, p7 = r14, in1
    57 (p7)    br.cond.dpnt 3f ;;
    58 0:
    59         cmp.ne p6, p7 = 0, in2
    60 (p7)    br.cond.dpnt 2f ;;
    61 (p6)    adds r14 = -1, in2
    62 (p6)    mov r16 = r0
    63 (p6)    mov r17 = r0 ;;
    64 (p6)    mov ar.lc = r14
    65 1:
    66         add r14 = r16, in1
    67         add r15 = r16, in0
    68         adds r17 = 1, r17 ;;
    69         ld1 r14 = [r14]
    70         mov r16 = r17 ;;
    71         st1 [r15] = r14
    72         br.cloop.sptk.few 1b ;;
    73 2:
    74         mov ar.lc = r2
    75         mov ar.pfs = loc0
    76         br.ret.sptk.many rp
    77 3:
    78         adds r14 = 7, in0 ;;
    79         and r14 = -8, r14 ;;
    80         cmp.eq p6, p7 = r14, in0
    81 (p7)    br.cond.dptk 0b
    82         shr.u r18 = in2, 3 ;;
    83         cmp.ne p6, p7 = 0, r18
    84 (p7)    br.cond.dpnt 5f ;;
    85 (p6)    adds r14 = -1, r18
    86 (p6)    mov r16 = r0
    87 (p6)    mov r17 = r0 ;;
    88 (p6)    mov ar.lc = r14
    89 4:
    90         shladd r14 = r16, 3, r0
    91         adds r16 = 1, r17 ;;
    92         add r15 = in1, r14
    93         add r14 = in0, r14
    94         mov r17 = r16 ;;
    95         ld8 r15 = [r15] ;;
    96         st8 [r14] = r15
    97         br.cloop.sptk.few 4b
    98 5:
    99         and r15 = 7, in2
    100         shladd r14 = r18, 3, r0
    101         mov r16 = r0
    102         mov r18 = r0 ;;
    103         cmp.eq p6, p7 = 0, r15
    104         add in0 = r14, in0
    105         adds r15 = -1, r15
    106         add r17 = r14, in1
    107 (p6)    br.cond.dpnt 2b ;;
    108         mov ar.lc = r15
    109 6:
    110         add r14 = r16, r17
    111         add r15 = r16, in0
    112         adds r16 = 1, r18 ;;
    113         ld1 r14 = [r14]
    114         mov r18 = r16 ;;
    115         st1 [r15] = r14
    116         br.cloop.sptk.few 6b ;;
    117         mov ar.lc = r2
    118         mov ar.pfs = loc0
    119         br.ret.sptk.many rp
    120        
     58        (p7) br.cond.dpnt 3f ;;
     59       
     60        0:
     61       
     62                cmp.ne p6, p7 = 0, in2
     63                (p7) br.cond.dpnt 2f ;;
     64                (p6) adds r14 = -1, in2
     65                (p6) mov r16 = r0
     66                (p6) mov r17 = r0 ;;
     67                (p6) mov ar.lc = r14
     68       
     69        1:
     70       
     71                add r14 = r16, in1
     72                add r15 = r16, in0
     73                adds r17 = 1, r17 ;;
     74                ld1 r14 = [r14]
     75                mov r16 = r17 ;;
     76                st1 [r15] = r14
     77                br.cloop.sptk.few 1b ;;
     78       
     79        2:
     80       
     81                mov ar.lc = r2
     82                mov ar.pfs = loc0
     83                br.ret.sptk.many rp
     84       
     85        3:
     86       
     87                adds r14 = 7, in0 ;;
     88                and r14 = -8, r14 ;;
     89                cmp.eq p6, p7 = r14, in0
     90                (p7) br.cond.dptk 0b
     91                shr.u r18 = in2, 3 ;;
     92                cmp.ne p6, p7 = 0, r18
     93                (p7) br.cond.dpnt 5f ;;
     94                (p6) adds r14 = -1, r18
     95                (p6) mov r16 = r0
     96                (p6) mov r17 = r0 ;;
     97                (p6) mov ar.lc = r14
     98       
     99        4:
     100       
     101                shladd r14 = r16, 3, r0
     102                adds r16 = 1, r17 ;;
     103                add r15 = in1, r14
     104                add r14 = in0, r14
     105                mov r17 = r16 ;;
     106                ld8 r15 = [r15] ;;
     107                st8 [r14] = r15
     108                br.cloop.sptk.few 4b
     109       
     110        5:
     111       
     112                and r15 = 7, in2
     113                shladd r14 = r18, 3, r0
     114                mov r16 = r0
     115                mov r18 = r0 ;;
     116                cmp.eq p6, p7 = 0, r15
     117                add in0 = r14, in0
     118                adds r15 = -1, r15
     119                add r17 = r14, in1
     120                (p6) br.cond.dpnt 2b ;;
     121                mov ar.lc = r15
     122       
     123        6:
     124       
     125                add r14 = r16, r17
     126                add r15 = r16, in0
     127                adds r16 = 1, r18 ;;
     128                ld1 r14 = [r14]
     129                mov r18 = r16 ;;
     130                st1 [r15] = r14
     131                br.cloop.sptk.few 6b ;;
     132                mov ar.lc = r2
     133                mov ar.pfs = loc0
     134                br.ret.sptk.many rp
     135
    121136memcpy_from_uspace_failover_address:
    122137memcpy_to_uspace_failover_address:
    123         mov r8 = r0                     /* return 0 on failure */
     138        /* Return 0 on failure */
     139        mov r8 = r0
    124140        mov ar.pfs = loc0
    125141        br.ret.sptk.many rp
     
    145161 * @param in4 Value to be stored in IPSR.
    146162 * @param in5 Value to be stored in RSC.
     163 *
    147164 */
    148165.global switch_to_userspace
    149166switch_to_userspace:
    150167        alloc loc0 = ar.pfs, 6, 3, 0, 0
    151         rsm (PSR_IC_MASK | PSR_I_MASK)          /* disable interruption collection and interrupts */
     168       
     169        /* Disable interruption collection and interrupts */
     170        rsm (PSR_IC_MASK | PSR_I_MASK)
    152171        srlz.d ;;
    153172        srlz.i ;;
     
    156175        mov cr.iip = in0
    157176        mov r12 = in1
    158 
     177       
    159178        xor r1 = r1, r1
    160179       
     
    165184        movl loc2 = PFM_MASK ;;
    166185        and loc1 = loc2, loc1 ;;
    167         mov cr.ifs = loc1 ;;                    /* prevent decrementing BSP by rfi */
    168 
     186        mov cr.ifs = loc1 ;;  /* prevent decrementing BSP by rfi */
     187       
    169188        invala
    170189       
    171190        mov loc1 = ar.rsc ;;
    172         and loc1 = ~3, loc1 ;;                 
    173         mov ar.rsc = loc1 ;;                    /* put RSE into enforced lazy mode */
    174 
     191        and loc1 = ~3, loc1 ;;
     192        mov ar.rsc = loc1 ;;  /* put RSE into enforced lazy mode */
     193       
    175194        flushrs ;;
    176195       
     
    181200       
    182201        rfi ;;
     202
     203.global early_putchar
     204early_putchar:
     205        br.ret.sptk.many b0
  • kernel/arch/ia64/src/start.S

    r4d1be48 re2ea4ab1  
    4747
    4848stack0:
     49
     50#
     51# Kernel entry point.
     52#
     53# This is where we are passed control from the boot code.
     54# Register contents:
     55#
     56#       r2      Address of the boot code's bootinfo structure.
     57#
    4958kernel_image_start:
    5059        .auto
     
    157166        loadrs
    158167       
    159         # Initialize memory stack to some sane value
    160         movl r12 = stack0 ;;
    161         add r12 = -16, r12  /* allocate a scratch area on the stack */
     168        #
     169        # Initialize memory stack to some sane value and allocate a scratch are
     170        # on it.
     171        #
     172        movl sp = stack0 ;;
     173        add sp = -16, sp
    162174       
    163175        # Initialize gp (Global Pointer) register
     176        movl gp = kernel_image_start
     177       
     178        #       
     179        # Initialize bootinfo on BSP.
     180        #
    164181        movl r20 = (VRN_KERNEL << VRN_SHIFT) ;;
    165         or r20 = r20, r1 ;;
    166         movl r1 = kernel_image_start
    167        
    168         /*
    169          * Initialize bootinfo on BSP.
    170          */
     182        or r20 = r20, r2 ;;
    171183        addl r21 = @gprel(bootinfo), gp ;;
    172184        st8 [r21] = r20
  • kernel/arch/mips32/src/asm.S

    r4d1be48 re2ea4ab1  
    1 #
    2 # Copyright (c) 2003-2004 Jakub Jermar
    3 # All rights reserved.
    4 #
    5 # Redistribution and use in source and binary forms, with or without
    6 # modification, are permitted provided that the following conditions
    7 # are met:
    8 #
    9 # - Redistributions of source code must retain the above copyright
    10 #   notice, this list of conditions and the following disclaimer.
    11 # - Redistributions in binary form must reproduce the above copyright
    12 #   notice, this list of conditions and the following disclaimer in the
    13 #   documentation and/or other materials provided with the distribution.
    14 # - The name of the author may not be used to endorse or promote products
    15 #   derived from this software without specific prior written permission.
    16 #
    17 # THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
    18 # IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
    19 # OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
    20 # IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
    21 # INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
    22 # NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
    23 # DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
    24 # THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
    25 # (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
    26 # THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
    27 #
     1/*
     2 * Copyright (c) 2003 Jakub Jermar
     3 * All rights reserved.
     4 *
     5 * Redistribution and use in source and binary forms, with or without
     6 * modification, are permitted provided that the following conditions
     7 * are met:
     8 *
     9 * - Redistributions of source code must retain the above copyright
     10 *   notice, this list of conditions and the following disclaimer.
     11 * - Redistributions in binary form must reproduce the above copyright
     12 *   notice, this list of conditions and the following disclaimer in the
     13 *   documentation and/or other materials provided with the distribution.
     14 * - The name of the author may not be used to endorse or promote products
     15 *   derived from this software without specific prior written permission.
     16 *
     17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
     18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
     19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
     20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
     21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
     22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
     23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
     24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
     25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
     26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     27 */
    2828
    2929#include <arch/asm/regname.h>
     
    5757        nop
    5858
    59 
    6059.global memsetb
    6160memsetb:
     
    6362        nop
    6463
    65 
    6664.global memsetw
    6765memsetw:
    6866        j _memsetw
    6967        nop
    70 
    7168
    7269.global memcpy
     
    7875memcpy_from_uspace:
    7976memcpy_to_uspace:
    80         move $t2, $a0      # save dst
     77        move $t2, $a0  /* save dst */
    8178       
    8279        addiu $v0, $a1, 3
    83         li $v1, -4         # 0xfffffffffffffffc
     80        li $v1, -4  /* 0xfffffffffffffffc */
    8481        and $v0, $v0, $v1
    8582        beq $a1, $v0, 3f
     
    149146        move $v0, $zero
    150147
    151 
    152 
    153148.macro fpu_gp_save reg ctx
    154149        mfc1 $t0, $\reg
     
    164159        cfc1 $t0, $1
    165160        sw $t0, (\reg + 32) * 4(\ctx)
    166 .endm   
     161.endm
    167162
    168163.macro fpu_ct_restore reg ctx
     
    170165        ctc1 $t0, $\reg
    171166.endm
    172 
    173167
    174168.global fpu_context_save
     
    313307        j $ra
    314308        nop
     309
     310.global early_putchar
     311early_putchar:
     312        j $ra
     313        nop
  • kernel/arch/ppc32/src/asm.S

    r4d1be48 re2ea4ab1  
    1 #
    2 # Copyright (c) 2005 Martin Decky
    3 # All rights reserved.
    4 #
    5 # Redistribution and use in source and binary forms, with or without
    6 # modification, are permitted provided that the following conditions
    7 # are met:
    8 #
    9 # - Redistributions of source code must retain the above copyright
    10 #   notice, this list of conditions and the following disclaimer.
    11 # - Redistributions in binary form must reproduce the above copyright
    12 #   notice, this list of conditions and the following disclaimer in the
    13 #   documentation and/or other materials provided with the distribution.
    14 # - The name of the author may not be used to endorse or promote products
    15 #   derived from this software without specific prior written permission.
    16 #
    17 # THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
    18 # IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
    19 # OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
    20 # IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
    21 # INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
    22 # NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
    23 # DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
    24 # THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
    25 # (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
    26 # THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
    27 #
     1/*
     2 * Copyright (c) 2005 Martin Decky
     3 * All rights reserved.
     4 *
     5 * Redistribution and use in source and binary forms, with or without
     6 * modification, are permitted provided that the following conditions
     7 * are met:
     8 *
     9 * - Redistributions of source code must retain the above copyright
     10 *   notice, this list of conditions and the following disclaimer.
     11 * - Redistributions in binary form must reproduce the above copyright
     12 *   notice, this list of conditions and the following disclaimer in the
     13 *   documentation and/or other materials provided with the distribution.
     14 * - The name of the author may not be used to endorse or promote products
     15 *   derived from this software without specific prior written permission.
     16 *
     17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
     18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
     19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
     20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
     21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
     22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
     23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
     24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
     25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
     26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     27 */
    2828
    2929#include <arch/asm/regname.h>
     
    4242.global memcpy_from_uspace_failover_address
    4343.global memcpy_to_uspace_failover_address
     44.global early_putchar
    4445
    4546userspace_asm:
    4647       
    47         # r3 = uspace_uarg
    48         # r4 = stack
    49         # r5 = entry
    50        
    51         # disable interrupts
     48        /*
     49         * r3 = uspace_uarg
     50         * r4 = stack
     51         * r5 = entry
     52         */
     53       
     54        /* Disable interrupts */
    5255       
    5356        mfmsr r31
     
    5558        mtmsr r31
    5659       
    57         # set entry point
     60        /* Set entry point */
    5861       
    5962        mtsrr0 r5
    6063       
    61         # set problem state, enable interrupts
     64        /* Set problem state, enable interrupts */
    6265       
    6366        ori r31, r31, MSR_PR
     
    6568        mtsrr1 r31
    6669       
    67         # set stack
     70        /* Set stack */
    6871       
    6972        mr sp, r4
    7073       
    71         # %r6 is defined to hold pcb_ptr - set it to 0
     74        /* %r6 is defined to hold pcb_ptr - set it to 0 */
    7275       
    7376        xor r6, r6, r6
    7477       
    75         # jump to userspace
     78        /* Jump to userspace */
    7679       
    7780        rfi
     
    7982iret:
    8083       
    81         # disable interrupts
     84        /* Disable interrupts */
    8285       
    8386        mfmsr r31
     
    141144iret_syscall:
    142145       
    143         # reset decrementer
     146        /* Reset decrementer */
    144147       
    145148        li r31, 1000
    146149        mtdec r31
    147150       
    148         # disable interrupts
     151        /* Disable interrupts */
    149152       
    150153        mfmsr r31
     
    278281memcpy_from_uspace_failover_address:
    279282memcpy_to_uspace_failover_address:
    280         # return zero, failure
     283        /* Return zero, failure */
    281284        xor r3, r3, r3
    282285        blr
     286
     287early_putchar:
     288        blr
  • kernel/arch/sparc64/src/asm.S

    r4d1be48 re2ea4ab1  
    1 #
    2 # Copyright (c) 2005 Jakub Jermar
    3 # All rights reserved.
    4 #
    5 # Redistribution and use in source and binary forms, with or without
    6 # modification, are permitted provided that the following conditions
    7 # are met:
    8 #
    9 # - Redistributions of source code must retain the above copyright
    10 #   notice, this list of conditions and the following disclaimer.
    11 # - Redistributions in binary form must reproduce the above copyright
    12 #   notice, this list of conditions and the following disclaimer in the
    13 #   documentation and/or other materials provided with the distribution.
    14 # - The name of the author may not be used to endorse or promote products
    15 #   derived from this software without specific prior written permission.
    16 #
    17 # THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
    18 # IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
    19 # OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
    20 # IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
    21 # INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
    22 # NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
    23 # DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
    24 # THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
    25 # (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
    26 # THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
    27 #
     1/*
     2 * Copyright (c) 2005 Jakub Jermar
     3 * All rights reserved.
     4 *
     5 * Redistribution and use in source and binary forms, with or without
     6 * modification, are permitted provided that the following conditions
     7 * are met:
     8 *
     9 * - Redistributions of source code must retain the above copyright
     10 *   notice, this list of conditions and the following disclaimer.
     11 * - Redistributions in binary form must reproduce the above copyright
     12 *   notice, this list of conditions and the following disclaimer in the
     13 *   documentation and/or other materials provided with the distribution.
     14 * - The name of the author may not be used to endorse or promote products
     15 *   derived from this software without specific prior written permission.
     16 *
     17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
     18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
     19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
     20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
     21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
     22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
     23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
     24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
     25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
     26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     27 */
    2828
    2929#include <arch/arch.h>
     
    3232.text
    3333
    34 .register       %g2, #scratch
    35 .register       %g3, #scratch
     34.register %g2, #scratch
     35.register %g3, #scratch
    3636
    3737/*
     
    4040.global memcpy
    4141memcpy:
    42         mov     %o0, %o3                ! save dst
    43         add     %o1, 7, %g1
    44         and     %g1, -8, %g1
    45         cmp     %o1, %g1
    46         be,pn   %xcc, 3f
    47         add     %o0, 7, %g1
    48         mov     0, %g3
    49 0:
    50         brz,pn  %o2, 2f
    51         mov     0, %g2
    52 1:
    53         ldub    [%g3 + %o1], %g1
    54         add     %g2, 1, %g2
    55         cmp     %o2, %g2
    56         stb     %g1, [%g3 + %o0]
    57         bne,pt  %xcc, 1b
    58         mov     %g2, %g3
    59 2:
    60         jmp     %o7 + 8                 ! exit point
    61         mov     %o3, %o0
    62 3:
    63         and     %g1, -8, %g1
    64         cmp     %o0, %g1
    65         bne,pt  %xcc, 0b
    66         mov     0, %g3
    67         srlx    %o2, 3, %g4
    68         brz,pn  %g4, 5f
    69         mov     0, %g5
    70 4:
    71         sllx    %g3, 3, %g2
    72         add     %g5, 1, %g3
    73         ldx     [%o1 + %g2], %g1
    74         mov     %g3, %g5
    75         cmp     %g4, %g3
    76         bne,pt  %xcc, 4b
    77         stx     %g1, [%o0 + %g2]
    78 5:
    79         and     %o2, 7, %o2
    80         brz,pn  %o2, 2b
    81         sllx    %g4, 3, %g1
    82         mov     0, %g2
    83         add     %g1, %o0, %o0
    84         add     %g1, %o1, %g4
    85         mov     0, %g3
    86 6:
    87         ldub    [%g2 + %g4], %g1
    88         stb     %g1, [%g2 + %o0]
    89         add     %g3, 1, %g2
    90         cmp     %o2, %g2
    91         bne,pt  %xcc, 6b
    92         mov     %g2, %g3
    93 
    94         jmp     %o7 + 8                 ! exit point
    95         mov     %o3, %o0
     42        mov %o0, %o3  /* save dst */
     43        add %o1, 7, %g1
     44        and %g1, -8, %g1
     45        cmp %o1, %g1
     46        be,pn %xcc, 3f
     47        add %o0, 7, %g1
     48        mov 0, %g3
     49       
     50        0:
     51       
     52                brz,pn %o2, 2f
     53                mov 0, %g2
     54       
     55        1:
     56       
     57                ldub [%g3 + %o1], %g1
     58                add %g2, 1, %g2
     59                cmp %o2, %g2
     60                stb %g1, [%g3 + %o0]
     61                bne,pt %xcc, 1b
     62                mov %g2, %g3
     63       
     64        2:
     65       
     66                jmp %o7 + 8  /* exit point */
     67                mov %o3, %o0
     68       
     69        3:
     70       
     71                and %g1, -8, %g1
     72                cmp %o0, %g1
     73                bne,pt %xcc, 0b
     74                mov 0, %g3
     75                srlx %o2, 3, %g4
     76                brz,pn %g4, 5f
     77                mov 0, %g5
     78       
     79        4:
     80       
     81                sllx %g3, 3, %g2
     82                add %g5, 1, %g3
     83                ldx [%o1 + %g2], %g1
     84                mov %g3, %g5
     85                cmp %g4, %g3
     86                bne,pt %xcc, 4b
     87                stx %g1, [%o0 + %g2]
     88       
     89        5:
     90       
     91                and %o2, 7, %o2
     92                brz,pn %o2, 2b
     93                sllx %g4, 3, %g1
     94                mov 0, %g2
     95                add %g1, %o0, %o0
     96                add %g1, %o1, %g4
     97                mov 0, %g3
     98       
     99        6:
     100       
     101                ldub [%g2 + %g4], %g1
     102                stb %g1, [%g2 + %o0]
     103                add %g3, 1, %g2
     104                cmp %o2, %g2
     105                bne,pt %xcc, 6b
     106                mov %g2, %g3
     107               
     108                jmp %o7 + 8  /* exit point */
     109                mov %o3, %o0
    96110
    97111/*
     
    100114.global memcpy_from_uspace
    101115memcpy_from_uspace:
    102         mov     %o0, %o3                ! save dst
    103         add     %o1, 7, %g1
    104         and     %g1, -8, %g1
    105         cmp     %o1, %g1
    106         be,pn   %xcc, 3f
    107         add     %o0, 7, %g1
    108         mov     0, %g3
    109 0:
    110         brz,pn  %o2, 2f
    111         mov     0, %g2
    112 1:
    113         lduba   [%g3 + %o1] ASI_AIUS, %g1
    114         add     %g2, 1, %g2
    115         cmp     %o2, %g2
    116         stb     %g1, [%g3 + %o0]
    117         bne,pt  %xcc, 1b
    118         mov     %g2, %g3
    119 2:
    120         jmp     %o7 + 8                 ! exit point
    121         mov     %o3, %o0
    122 3:
    123         and     %g1, -8, %g1
    124         cmp     %o0, %g1
    125         bne,pt  %xcc, 0b
    126         mov     0, %g3
    127         srlx    %o2, 3, %g4
    128         brz,pn  %g4, 5f
    129         mov     0, %g5
    130 4:
    131         sllx    %g3, 3, %g2
    132         add     %g5, 1, %g3
    133         ldxa    [%o1 + %g2] ASI_AIUS, %g1
    134         mov     %g3, %g5
    135         cmp     %g4, %g3
    136         bne,pt  %xcc, 4b
    137         stx     %g1, [%o0 + %g2]
    138 5:
    139         and     %o2, 7, %o2
    140         brz,pn  %o2, 2b
    141         sllx    %g4, 3, %g1
    142         mov     0, %g2
    143         add     %g1, %o0, %o0
    144         add     %g1, %o1, %g4
    145         mov     0, %g3
    146 6:
    147         lduba   [%g2 + %g4] ASI_AIUS, %g1
    148         stb     %g1, [%g2 + %o0]
    149         add     %g3, 1, %g2
    150         cmp     %o2, %g2
    151         bne,pt  %xcc, 6b
    152         mov     %g2, %g3
    153 
    154         jmp     %o7 + 8                 ! exit point
    155         mov     %o3, %o0
     116        mov %o0, %o3  /* save dst */
     117        add %o1, 7, %g1
     118        and %g1, -8, %g1
     119        cmp %o1, %g1
     120        be,pn %xcc, 3f
     121        add %o0, 7, %g1
     122        mov 0, %g3
     123       
     124        0:
     125       
     126                brz,pn %o2, 2f
     127                mov 0, %g2
     128       
     129        1:
     130       
     131                lduba [%g3 + %o1] ASI_AIUS, %g1
     132                add %g2, 1, %g2
     133                cmp %o2, %g2
     134                stb %g1, [%g3 + %o0]
     135                bne,pt %xcc, 1b
     136                mov %g2, %g3
     137       
     138        2:
     139       
     140                jmp %o7 + 8  /* exit point */
     141                mov %o3, %o0
     142       
     143        3:
     144       
     145                and %g1, -8, %g1
     146                cmp %o0, %g1
     147                bne,pt %xcc, 0b
     148                mov 0, %g3
     149                srlx %o2, 3, %g4
     150                brz,pn %g4, 5f
     151                mov 0, %g5
     152       
     153        4:
     154       
     155                sllx %g3, 3, %g2
     156                add %g5, 1, %g3
     157                ldxa [%o1 + %g2] ASI_AIUS, %g1
     158                mov %g3, %g5
     159                cmp %g4, %g3
     160                bne,pt %xcc, 4b
     161                stx %g1, [%o0 + %g2]
     162       
     163        5:
     164       
     165                and %o2, 7, %o2
     166                brz,pn %o2, 2b
     167                sllx %g4, 3, %g1
     168                mov 0, %g2
     169                add %g1, %o0, %o0
     170                add %g1, %o1, %g4
     171                mov 0, %g3
     172       
     173        6:
     174       
     175                lduba [%g2 + %g4] ASI_AIUS, %g1
     176                stb %g1, [%g2 + %o0]
     177                add %g3, 1, %g2
     178                cmp %o2, %g2
     179                bne,pt %xcc, 6b
     180                mov %g2, %g3
     181               
     182                jmp %o7 + 8  /* exit point */
     183                mov %o3, %o0
    156184
    157185/*
     
    160188.global memcpy_to_uspace
    161189memcpy_to_uspace:
    162         mov     %o0, %o3                ! save dst
    163         add     %o1, 7, %g1
    164         and     %g1, -8, %g1
    165         cmp     %o1, %g1
    166         be,pn   %xcc, 3f
    167         add     %o0, 7, %g1
    168         mov     0, %g3
    169 0:
    170         brz,pn  %o2, 2f
    171         mov     0, %g2
    172 1:
    173         ldub    [%g3 + %o1], %g1
    174         add     %g2, 1, %g2
    175         cmp     %o2, %g2
    176         stba    %g1, [%g3 + %o0] ASI_AIUS
    177         bne,pt  %xcc, 1b
    178         mov     %g2, %g3
    179 2:
    180         jmp     %o7 + 8                 ! exit point
    181         mov     %o3, %o0
    182 3:
    183         and     %g1, -8, %g1
    184         cmp     %o0, %g1
    185         bne,pt  %xcc, 0b
    186         mov     0, %g3
    187         srlx    %o2, 3, %g4
    188         brz,pn  %g4, 5f
    189         mov     0, %g5
    190 4:
    191         sllx    %g3, 3, %g2
    192         add     %g5, 1, %g3
    193         ldx     [%o1 + %g2], %g1
    194         mov     %g3, %g5
    195         cmp     %g4, %g3
    196         bne,pt  %xcc, 4b
    197         stxa    %g1, [%o0 + %g2] ASI_AIUS
    198 5:
    199         and     %o2, 7, %o2
    200         brz,pn  %o2, 2b
    201         sllx    %g4, 3, %g1
    202         mov     0, %g2
    203         add     %g1, %o0, %o0
    204         add     %g1, %o1, %g4
    205         mov     0, %g3
    206 6:
    207         ldub    [%g2 + %g4], %g1
    208         stba    %g1, [%g2 + %o0] ASI_AIUS
    209         add     %g3, 1, %g2
    210         cmp     %o2, %g2
    211         bne,pt  %xcc, 6b
    212         mov     %g2, %g3
    213 
    214         jmp     %o7 + 8                 ! exit point
    215         mov     %o3, %o0
     190        mov %o0, %o3  /* save dst */
     191        add %o1, 7, %g1
     192        and %g1, -8, %g1
     193        cmp %o1, %g1
     194        be,pn %xcc, 3f
     195        add %o0, 7, %g1
     196        mov 0, %g3
     197       
     198        0:
     199       
     200                brz,pn %o2, 2f
     201                mov 0, %g2
     202       
     203        1:
     204       
     205                ldub [%g3 + %o1], %g1
     206                add %g2, 1, %g2
     207                cmp %o2, %g2
     208                stba %g1, [%g3 + %o0] ASI_AIUS
     209                bne,pt %xcc, 1b
     210                mov %g2, %g3
     211       
     212        2:
     213       
     214                jmp %o7 + 8  /* exit point */
     215                mov %o3, %o0
     216       
     217        3:
     218       
     219                and %g1, -8, %g1
     220                cmp %o0, %g1
     221                bne,pt %xcc, 0b
     222                mov 0, %g3
     223                srlx %o2, 3, %g4
     224                brz,pn %g4, 5f
     225                mov 0, %g5
     226       
     227        4:
     228       
     229                sllx %g3, 3, %g2
     230                add %g5, 1, %g3
     231                ldx [%o1 + %g2], %g1
     232                mov %g3, %g5
     233                cmp %g4, %g3
     234                bne,pt %xcc, 4b
     235                stxa %g1, [%o0 + %g2] ASI_AIUS
     236       
     237        5:
     238       
     239                and %o2, 7, %o2
     240                brz,pn %o2, 2b
     241                sllx %g4, 3, %g1
     242                mov 0, %g2
     243                add %g1, %o0, %o0
     244                add %g1, %o1, %g4
     245                mov 0, %g3
     246       
     247        6:
     248       
     249                ldub [%g2 + %g4], %g1
     250                stba %g1, [%g2 + %o0] ASI_AIUS
     251                add %g3, 1, %g2
     252                cmp %o2, %g2
     253                bne,pt %xcc, 6b
     254                mov %g2, %g3
     255               
     256                jmp     %o7 + 8  /* exit point */
     257                mov     %o3, %o0
    216258
    217259.global memcpy_from_uspace_failover_address
     
    219261memcpy_from_uspace_failover_address:
    220262memcpy_to_uspace_failover_address:
    221         jmp     %o7 + 8                 ! exit point
    222         mov     %g0, %o0                ! return 0 on failure
     263        jmp %o7 + 8   /* exit point */
     264        mov %g0, %o0  /* return 0 on failure */
    223265
    224266.global memsetb
     
    232274        nop
    233275
     276.global early_putchar
     277early_putchar:
     278        retl
     279        nop
  • kernel/arch/sparc64/src/trap/sun4v/interrupt.c

    r4d1be48 re2ea4ab1  
    111111                        ((void (*)(void)) data1)();
    112112                } else {
    113                         printf("Spurious interrupt on %d, data = %lx.\n",
     113                        printf("Spurious interrupt on %d, data = %" PRIx64 ".\n",
    114114                            CPU->arch.id, data1);
    115115                }
  • kernel/genarch/src/acpi/madt.c

    r4d1be48 re2ea4ab1  
    9595        /*
    9696         * FIXME: The current local APIC driver limits usable
    97          * APIC IDs to 8.
     97         * CPU IDs to 8.
    9898         *
    9999         */
    100         if (madt_cpu_apic_id(i) > 7)
     100        if (i > 7)
    101101                return false;
    102102       
     
    111111        return ((struct madt_l_apic *)
    112112            madt_entries_index[madt_l_apic_entry_index + i])->apic_id ==
    113             l_apic_id();
     113            bsp_l_apic;
    114114}
    115115
     
    131131};
    132132
    133 static int madt_cmp(void *a, void *b)
    134 {
    135         uint8_t typea = ((struct madt_apic_header *) a)->type;
    136         uint8_t typeb = ((struct madt_apic_header *) b)->type;
     133static int madt_cmp(void *a, void *b, void *arg)
     134{
     135        uint8_t typea = (*((struct madt_apic_header **) a))->type;
     136        uint8_t typeb = (*((struct madt_apic_header **) b))->type;
    137137       
    138138        if (typea > typeb)
     
    147147static void madt_l_apic_entry(struct madt_l_apic *la, size_t i)
    148148{
    149         if (!madt_l_apic_entry_cnt++)
     149        if (madt_l_apic_entry_cnt == 0)
    150150                madt_l_apic_entry_index = i;
     151       
     152        madt_l_apic_entry_cnt++;
    151153       
    152154        if (!(la->flags & 0x1)) {
     
    160162static void madt_io_apic_entry(struct madt_io_apic *ioa, size_t i)
    161163{
    162         if (!madt_io_apic_entry_cnt++) {
     164        if (madt_io_apic_entry_cnt == 0) {
    163165                /* Remember index of the first io apic entry */
    164166                madt_io_apic_entry_index = i;
     
    167169                /* Currently not supported */
    168170        }
     171       
     172        madt_io_apic_entry_cnt++;
    169173}
    170174
     
    190194        /* Count MADT entries */
    191195        unsigned int madt_entries_index_cnt = 0;
    192         for (hdr = &acpi_madt->apic_header[0]; hdr < end;
     196        for (hdr = acpi_madt->apic_header; hdr < end;
    193197            hdr = (struct madt_apic_header *) (((uint8_t *) hdr) + hdr->length))
    194198                madt_entries_index_cnt++;
     
    196200        /* Create MADT APIC entries index array */
    197201        madt_entries_index = (struct madt_apic_header **)
    198             malloc(madt_entries_index_cnt * sizeof(struct madt_apic_header **),
     202            malloc(madt_entries_index_cnt * sizeof(struct madt_apic_header *),
    199203            FRAME_ATOMIC);
    200204        if (!madt_entries_index)
     
    203207        size_t i = 0;
    204208       
    205         for (hdr = &acpi_madt->apic_header[0]; hdr < end;
    206             hdr = (struct madt_apic_header *) (((uint8_t *) hdr) + hdr->length))
    207                 madt_entries_index[i++] = hdr;
     209        for (hdr = acpi_madt->apic_header; hdr < end;
     210            hdr = (struct madt_apic_header *) (((uint8_t *) hdr) + hdr->length)) {
     211                madt_entries_index[i] = hdr;
     212                i++;
     213        }
    208214       
    209215        /* Sort MADT index structure */
    210         qsort(madt_entries_index, madt_entries_index_cnt, sizeof(uintptr_t),
    211             &madt_cmp);
     216        if (!gsort(madt_entries_index, madt_entries_index_cnt,
     217            sizeof(struct madt_apic_header *), madt_cmp, NULL))
     218                panic("Sorting error.");
    212219       
    213220        /* Parse MADT entries */
  • kernel/generic/include/console/console.h

    r4d1be48 re2ea4ab1  
    5656extern outdev_t *stdout;
    5757
     58extern void early_putchar(wchar_t);
     59
    5860extern indev_t *stdin_wire(void);
    5961extern void stdout_wire(outdev_t *outdev);
  • kernel/generic/include/context.h

    r4d1be48 re2ea4ab1  
    8787 *
    8888 * @param ctx Context structure.
     89 *
    8990 */
    90 static inline void context_restore(context_t *ctx)
     91static inline void __attribute__((no_instrument_function))
     92    context_restore(context_t *ctx)
    9193{
    9294        context_restore_arch(ctx);
  • kernel/generic/include/debug.h

    r4d1be48 re2ea4ab1  
    9393#define LOG(format, ...) \
    9494        do { \
    95                 printf("%s->%s() at %s:%u: " format "\n", symtab_fmt_name_lookup(CALLER), \
    96                     __func__, __FILE__, __LINE__, ##__VA_ARGS__); \
    97         } while (0)
    98 
    99 /** Extensive logging execute macro
    100  *
    101  * If CONFIG_LOG is set, the LOG_EXEC() macro
    102  * will print an information about calling a given
    103  * function and call it.
    104  *
    105  */
    106 #define LOG_EXEC(fnc) \
    107         do { \
    108                 printf("%s->%s() at %s:%u: " #fnc "\n", symtab_fmt_name_lookup(CALLER), \
    109                     __func__, __FILE__, __LINE__); \
    110                 fnc; \
     95                printf("%s() from %s at %s:%u: " format "\n", __func__, \
     96                    symtab_fmt_name_lookup(CALLER), __FILE__, __LINE__, \
     97                    ##__VA_ARGS__); \
    11198        } while (0)
    11299
     
    114101
    115102#define LOG(format, ...)
    116 #define LOG_EXEC(fnc)     fnc
    117103
    118 #endif /* CONFOG_LOG */
     104#endif /* CONFIG_LOG */
     105
     106#ifdef CONFIG_TRACE
     107
     108extern void __cyg_profile_func_enter(void *, void *);
     109extern void __cyg_profile_func_exit(void *, void *);
     110
     111#endif /* CONFIG_TRACE */
    119112
    120113#endif
  • kernel/generic/include/macros.h

    r4d1be48 re2ea4ab1  
    4747 * @param sz2 Size of the second interval.
    4848 */
    49 static inline int overlaps(uintptr_t s1, size_t sz1, uintptr_t s2, size_t sz2)
     49static inline int __attribute__((no_instrument_function))
     50    overlaps(uintptr_t s1, size_t sz1, uintptr_t s2, size_t sz2)
    5051{
    5152        uintptr_t e1 = s1 + sz1;
  • kernel/generic/include/sort.h

    r4d1be48 re2ea4ab1  
    3838#include <typedefs.h>
    3939
    40 /*
    41  * sorting routines
    42  */
    43 extern void bubblesort(void * data, size_t n, size_t e_size, int (* cmp) (void * a, void * b));
    44 extern void qsort(void * data, size_t n, size_t e_size, int (* cmp) (void * a, void * b));
     40typedef int (* sort_cmp_t)(void *, void *, void *);
    4541
    46 /*
    47  * default sorting comparators
    48  */
    49 extern int int_cmp(void * a, void * b);
    50 extern int uint32_t_cmp(void * a, void * b);
    51 extern int uint16_t_cmp(void * a, void * b);
    52 extern int uint8_t_cmp(void * a, void * b);
     42extern bool gsort(void *, size_t, size_t, sort_cmp_t, void *);
     43extern bool qsort(void *, size_t, size_t, sort_cmp_t, void *);
    5344
    5445#endif
  • kernel/generic/src/adt/btree.c

    r4d1be48 re2ea4ab1  
    3333/**
    3434 * @file
    35  * @brief       B+tree implementation.
     35 * @brief B+tree implementation.
    3636 *
    3737 * This file implements B+tree type and operations.
     
    5454#include <print.h>
    5555
    56 static void btree_destroy_subtree(btree_node_t *root);
    57 static void _btree_insert(btree_t *t, btree_key_t key, void *value, btree_node_t *rsubtree, btree_node_t *node);
    58 static void _btree_remove(btree_t *t, btree_key_t key, btree_node_t *node);
    59 static void node_initialize(btree_node_t *node);
    60 static void node_insert_key_and_lsubtree(btree_node_t *node, btree_key_t key, void *value, btree_node_t *lsubtree);
    61 static void node_insert_key_and_rsubtree(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree);
    62 static void node_remove_key_and_lsubtree(btree_node_t *node, btree_key_t key);
    63 static void node_remove_key_and_rsubtree(btree_node_t *node, btree_key_t key);
    64 static btree_node_t *node_split(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree, btree_key_t *median);
    65 static btree_node_t *node_combine(btree_node_t *node);
    66 static size_t find_key_by_subtree(btree_node_t *node, btree_node_t *subtree, bool right);
    67 static void rotate_from_right(btree_node_t *lnode, btree_node_t *rnode, size_t idx);
    68 static void rotate_from_left(btree_node_t *lnode, btree_node_t *rnode, size_t idx);
    69 static bool try_insert_by_rotation_to_left(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree);
    70 static bool try_insert_by_rotation_to_right(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree);
    71 static bool try_rotation_from_left(btree_node_t *rnode);
    72 static bool try_rotation_from_right(btree_node_t *lnode);
    73 
    74 #define ROOT_NODE(n)            (!(n)->parent)
    75 #define INDEX_NODE(n)           ((n)->subtree[0] != NULL)
    76 #define LEAF_NODE(n)            ((n)->subtree[0] == NULL)
    77 
    78 #define FILL_FACTOR             ((BTREE_M-1)/2)
    79 
    80 #define MEDIAN_LOW_INDEX(n)     (((n)->keys-1)/2)
    81 #define MEDIAN_HIGH_INDEX(n)    ((n)->keys/2)
    82 #define MEDIAN_LOW(n)           ((n)->key[MEDIAN_LOW_INDEX((n))]);
    83 #define MEDIAN_HIGH(n)          ((n)->key[MEDIAN_HIGH_INDEX((n))]);
    84 
    8556static slab_cache_t *btree_node_slab;
     57
     58#define ROOT_NODE(n)   (!(n)->parent)
     59#define INDEX_NODE(n)  ((n)->subtree[0] != NULL)
     60#define LEAF_NODE(n)   ((n)->subtree[0] == NULL)
     61
     62#define FILL_FACTOR  ((BTREE_M - 1) / 2)
     63
     64#define MEDIAN_LOW_INDEX(n)   (((n)->keys-1) / 2)
     65#define MEDIAN_HIGH_INDEX(n)  ((n)->keys / 2)
     66#define MEDIAN_LOW(n)         ((n)->key[MEDIAN_LOW_INDEX((n))]);
     67#define MEDIAN_HIGH(n)        ((n)->key[MEDIAN_HIGH_INDEX((n))]);
    8668
    8769/** Initialize B-trees. */
    8870void btree_init(void)
    8971{
    90         btree_node_slab = slab_cache_create("btree_node_slab", sizeof(btree_node_t), 0, NULL, NULL, SLAB_CACHE_MAGDEFERRED);
     72        btree_node_slab = slab_cache_create("btree_node_slab",
     73            sizeof(btree_node_t), 0, NULL, NULL, SLAB_CACHE_MAGDEFERRED);
     74}
     75
     76/** Initialize B-tree node.
     77 *
     78 * @param node B-tree node.
     79 *
     80 */
     81static void node_initialize(btree_node_t *node)
     82{
     83        unsigned int i;
     84       
     85        node->keys = 0;
     86       
     87        /* Clean also space for the extra key. */
     88        for (i = 0; i < BTREE_MAX_KEYS + 1; i++) {
     89                node->key[i] = 0;
     90                node->value[i] = NULL;
     91                node->subtree[i] = NULL;
     92        }
     93       
     94        node->subtree[i] = NULL;
     95        node->parent = NULL;
     96       
     97        link_initialize(&node->leaf_link);
     98        link_initialize(&node->bfs_link);
     99        node->depth = 0;
    91100}
    92101
     
    94103 *
    95104 * @param t B-tree.
     105 *
    96106 */
    97107void btree_create(btree_t *t)
     
    103113}
    104114
    105 /** Destroy empty B-tree. */
    106 void btree_destroy(btree_t *t)
    107 {
    108         btree_destroy_subtree(t->root);
    109 }
    110 
    111 /** Insert key-value pair into B-tree.
    112  *
    113  * @param t B-tree.
    114  * @param key Key to be inserted.
    115  * @param value Value to be inserted.
    116  * @param leaf_node Leaf node where the insertion should begin.
    117  */
    118 void btree_insert(btree_t *t, btree_key_t key, void *value, btree_node_t *leaf_node)
    119 {
    120         btree_node_t *lnode;
    121        
    122         ASSERT(value);
    123        
    124         lnode = leaf_node;
    125         if (!lnode) {
    126                 if (btree_search(t, key, &lnode)) {
    127                         panic("B-tree %p already contains key %" PRIu64 ".", t, key);
    128                 }
    129         }
    130        
    131         _btree_insert(t, key, value, NULL, lnode);
    132 }
    133 
    134115/** Destroy subtree rooted in a node.
    135116 *
    136117 * @param root Root of the subtree.
    137  */
    138 void btree_destroy_subtree(btree_node_t *root)
     118 *
     119 */
     120static void btree_destroy_subtree(btree_node_t *root)
    139121{
    140122        size_t i;
    141 
     123       
    142124        if (root->keys) {
    143125                for (i = 0; i < root->keys + 1; i++) {
     
    146128                }
    147129        }
     130       
    148131        slab_free(btree_node_slab, root);
    149132}
    150133
     134/** Destroy empty B-tree. */
     135void btree_destroy(btree_t *t)
     136{
     137        btree_destroy_subtree(t->root);
     138}
     139
     140/** Insert key-value-rsubtree triplet into B-tree node.
     141 *
     142 * It is actually possible to have more keys than BTREE_MAX_KEYS.
     143 * This feature is used during splitting the node when the
     144 * number of keys is BTREE_MAX_KEYS + 1. Insert by left rotation
     145 * also makes use of this feature.
     146 *
     147 * @param node     B-tree node into wich the new key is to be inserted.
     148 * @param key      The key to be inserted.
     149 * @param value    Pointer to value to be inserted.
     150 * @param rsubtree Pointer to the right subtree.
     151 *
     152 */
     153static void node_insert_key_and_rsubtree(btree_node_t *node, btree_key_t key,
     154    void *value, btree_node_t *rsubtree)
     155{
     156        size_t i;
     157       
     158        for (i = 0; i < node->keys; i++) {
     159                if (key < node->key[i]) {
     160                        size_t j;
     161                       
     162                        for (j = node->keys; j > i; j--) {
     163                                node->key[j] = node->key[j - 1];
     164                                node->value[j] = node->value[j - 1];
     165                                node->subtree[j + 1] = node->subtree[j];
     166                        }
     167                       
     168                        break;
     169                }
     170        }
     171       
     172        node->key[i] = key;
     173        node->value[i] = value;
     174        node->subtree[i + 1] = rsubtree;
     175        node->keys++;
     176}
     177
     178/** Find key by its left or right subtree.
     179 *
     180 * @param node    B-tree node.
     181 * @param subtree Left or right subtree of a key found in node.
     182 * @param right   If true, subtree is a right subtree. If false,
     183 *                subtree is a left subtree.
     184 *
     185 * @return Index of the key associated with the subtree.
     186 *
     187 */
     188static size_t find_key_by_subtree(btree_node_t *node, btree_node_t *subtree,
     189    bool right)
     190{
     191        size_t i;
     192       
     193        for (i = 0; i < node->keys + 1; i++) {
     194                if (subtree == node->subtree[i])
     195                        return i - (int) (right != false);
     196        }
     197       
     198        panic("Node %p does not contain subtree %p.", node, subtree);
     199}
     200
     201/** Remove key and its left subtree pointer from B-tree node.
     202 *
     203 * Remove the key and eliminate gaps in node->key array.
     204 * Note that the value pointer and the left subtree pointer
     205 * is removed from the node as well.
     206 *
     207 * @param node B-tree node.
     208 * @param key  Key to be removed.
     209 *
     210 */
     211static void node_remove_key_and_lsubtree(btree_node_t *node, btree_key_t key)
     212{
     213        size_t i;
     214        size_t j;
     215       
     216        for (i = 0; i < node->keys; i++) {
     217                if (key == node->key[i]) {
     218                        for (j = i + 1; j < node->keys; j++) {
     219                                node->key[j - 1] = node->key[j];
     220                                node->value[j - 1] = node->value[j];
     221                                node->subtree[j - 1] = node->subtree[j];
     222                        }
     223                       
     224                        node->subtree[j - 1] = node->subtree[j];
     225                        node->keys--;
     226                       
     227                        return;
     228                }
     229        }
     230       
     231        panic("Node %p does not contain key %" PRIu64 ".", node, key);
     232}
     233
     234/** Remove key and its right subtree pointer from B-tree node.
     235 *
     236 * Remove the key and eliminate gaps in node->key array.
     237 * Note that the value pointer and the right subtree pointer
     238 * is removed from the node as well.
     239 *
     240 * @param node B-tree node.
     241 * @param key  Key to be removed.
     242 *
     243 */
     244static void node_remove_key_and_rsubtree(btree_node_t *node, btree_key_t key)
     245{
     246        size_t i, j;
     247       
     248        for (i = 0; i < node->keys; i++) {
     249                if (key == node->key[i]) {
     250                        for (j = i + 1; j < node->keys; j++) {
     251                                node->key[j - 1] = node->key[j];
     252                                node->value[j - 1] = node->value[j];
     253                                node->subtree[j] = node->subtree[j + 1];
     254                        }
     255                       
     256                        node->keys--;
     257                        return;
     258                }
     259        }
     260       
     261        panic("Node %p does not contain key %" PRIu64 ".", node, key);
     262}
     263
     264/** Insert key-value-lsubtree triplet into B-tree node.
     265 *
     266 * It is actually possible to have more keys than BTREE_MAX_KEYS.
     267 * This feature is used during insert by right rotation.
     268 *
     269 * @param node     B-tree node into wich the new key is to be inserted.
     270 * @param key      The key to be inserted.
     271 * @param value    Pointer to value to be inserted.
     272 * @param lsubtree Pointer to the left subtree.
     273 *
     274 */
     275static void node_insert_key_and_lsubtree(btree_node_t *node, btree_key_t key,
     276    void *value, btree_node_t *lsubtree)
     277{
     278        size_t i;
     279       
     280        for (i = 0; i < node->keys; i++) {
     281                if (key < node->key[i]) {
     282                        size_t j;
     283                       
     284                        for (j = node->keys; j > i; j--) {
     285                                node->key[j] = node->key[j - 1];
     286                                node->value[j] = node->value[j - 1];
     287                                node->subtree[j + 1] = node->subtree[j];
     288                        }
     289                       
     290                        node->subtree[j + 1] = node->subtree[j];
     291                        break;
     292                }
     293        }
     294       
     295        node->key[i] = key;
     296        node->value[i] = value;
     297        node->subtree[i] = lsubtree;
     298       
     299        node->keys++;
     300}
     301
     302/** Rotate one key-value-rsubtree triplet from the left sibling to the right sibling.
     303 *
     304 * The biggest key and its value and right subtree is rotated
     305 * from the left node to the right. If the node is an index node,
     306 * than the parent node key belonging to the left node takes part
     307 * in the rotation.
     308 *
     309 * @param lnode Left sibling.
     310 * @param rnode Right sibling.
     311 * @param idx   Index of the parent node key that is taking part
     312 *              in the rotation.
     313 *
     314 */
     315static void rotate_from_left(btree_node_t *lnode, btree_node_t *rnode, size_t idx)
     316{
     317        btree_key_t key = lnode->key[lnode->keys - 1];
     318       
     319        if (LEAF_NODE(lnode)) {
     320                void *value = lnode->value[lnode->keys - 1];
     321               
     322                node_remove_key_and_rsubtree(lnode, key);
     323                node_insert_key_and_lsubtree(rnode, key, value, NULL);
     324                lnode->parent->key[idx] = key;
     325        } else {
     326                btree_node_t *rsubtree = lnode->subtree[lnode->keys];
     327               
     328                node_remove_key_and_rsubtree(lnode, key);
     329                node_insert_key_and_lsubtree(rnode, lnode->parent->key[idx], NULL, rsubtree);
     330                lnode->parent->key[idx] = key;
     331               
     332                /* Fix parent link of the reconnected right subtree. */
     333                rsubtree->parent = rnode;
     334        }
     335}
     336
     337/** Rotate one key-value-lsubtree triplet from the right sibling to the left sibling.
     338 *
     339 * The smallest key and its value and left subtree is rotated
     340 * from the right node to the left. If the node is an index node,
     341 * than the parent node key belonging to the right node takes part
     342 * in the rotation.
     343 *
     344 * @param lnode Left sibling.
     345 * @param rnode Right sibling.
     346 * @param idx   Index of the parent node key that is taking part
     347 *              in the rotation.
     348 *
     349 */
     350static void rotate_from_right(btree_node_t *lnode, btree_node_t *rnode, size_t idx)
     351{
     352        btree_key_t key = rnode->key[0];
     353       
     354        if (LEAF_NODE(rnode)) {
     355                void *value = rnode->value[0];
     356               
     357                node_remove_key_and_lsubtree(rnode, key);
     358                node_insert_key_and_rsubtree(lnode, key, value, NULL);
     359                rnode->parent->key[idx] = rnode->key[0];
     360        } else {
     361                btree_node_t *lsubtree = rnode->subtree[0];
     362               
     363                node_remove_key_and_lsubtree(rnode, key);
     364                node_insert_key_and_rsubtree(lnode, rnode->parent->key[idx], NULL, lsubtree);
     365                rnode->parent->key[idx] = key;
     366               
     367                /* Fix parent link of the reconnected left subtree. */
     368                lsubtree->parent = lnode;
     369        }
     370}
     371
     372/** Insert key-value-rsubtree triplet and rotate the node to the left, if this operation can be done.
     373 *
     374 * Left sibling of the node (if it exists) is checked for free space.
     375 * If there is free space, the key is inserted and the smallest key of
     376 * the node is moved there. The index node which is the parent of both
     377 * nodes is fixed.
     378 *
     379 * @param node     B-tree node.
     380 * @param inskey   Key to be inserted.
     381 * @param insvalue Value to be inserted.
     382 * @param rsubtree Right subtree of inskey.
     383 *
     384 * @return True if the rotation was performed, false otherwise.
     385 *
     386 */
     387static bool try_insert_by_rotation_to_left(btree_node_t *node,
     388    btree_key_t inskey, void *insvalue, btree_node_t *rsubtree)
     389{
     390        size_t idx;
     391        btree_node_t *lnode;
     392       
     393        /*
     394         * If this is root node, the rotation can not be done.
     395         */
     396        if (ROOT_NODE(node))
     397                return false;
     398       
     399        idx = find_key_by_subtree(node->parent, node, true);
     400        if ((int) idx == -1) {
     401                /*
     402                 * If this node is the leftmost subtree of its parent,
     403                 * the rotation can not be done.
     404                 */
     405                return false;
     406        }
     407       
     408        lnode = node->parent->subtree[idx];
     409        if (lnode->keys < BTREE_MAX_KEYS) {
     410                /*
     411                 * The rotaion can be done. The left sibling has free space.
     412                 */
     413                node_insert_key_and_rsubtree(node, inskey, insvalue, rsubtree);
     414                rotate_from_right(lnode, node, idx);
     415                return true;
     416        }
     417       
     418        return false;
     419}
     420
     421/** Insert key-value-rsubtree triplet and rotate the node to the right, if this operation can be done.
     422 *
     423 * Right sibling of the node (if it exists) is checked for free space.
     424 * If there is free space, the key is inserted and the biggest key of
     425 * the node is moved there. The index node which is the parent of both
     426 * nodes is fixed.
     427 *
     428 * @param node     B-tree node.
     429 * @param inskey   Key to be inserted.
     430 * @param insvalue Value to be inserted.
     431 * @param rsubtree Right subtree of inskey.
     432 *
     433 * @return True if the rotation was performed, false otherwise.
     434 *
     435 */
     436static bool try_insert_by_rotation_to_right(btree_node_t *node,
     437    btree_key_t inskey, void *insvalue, btree_node_t *rsubtree)
     438{
     439        size_t idx;
     440        btree_node_t *rnode;
     441       
     442        /*
     443         * If this is root node, the rotation can not be done.
     444         */
     445        if (ROOT_NODE(node))
     446                return false;
     447       
     448        idx = find_key_by_subtree(node->parent, node, false);
     449        if (idx == node->parent->keys) {
     450                /*
     451                 * If this node is the rightmost subtree of its parent,
     452                 * the rotation can not be done.
     453                 */
     454                return false;
     455        }
     456       
     457        rnode = node->parent->subtree[idx + 1];
     458        if (rnode->keys < BTREE_MAX_KEYS) {
     459                /*
     460                 * The rotaion can be done. The right sibling has free space.
     461                 */
     462                node_insert_key_and_rsubtree(node, inskey, insvalue, rsubtree);
     463                rotate_from_left(node, rnode, idx);
     464                return true;
     465        }
     466       
     467        return false;
     468}
     469
     470/** Split full B-tree node and insert new key-value-right-subtree triplet.
     471 *
     472 * This function will split a node and return a pointer to a newly created
     473 * node containing keys greater than or equal to the greater of medians
     474 * (or median) of the old keys and the newly added key. It will also write
     475 * the median key to a memory address supplied by the caller.
     476 *
     477 * If the node being split is an index node, the median will not be
     478 * included in the new node. If the node is a leaf node,
     479 * the median will be copied there.
     480 *
     481 * @param node     B-tree node wich is going to be split.
     482 * @param key      The key to be inserted.
     483 * @param value    Pointer to the value to be inserted.
     484 * @param rsubtree Pointer to the right subtree of the key being added.
     485 * @param median   Address in memory, where the median key will be stored.
     486 *
     487 * @return Newly created right sibling of node.
     488 *
     489 */
     490static btree_node_t *node_split(btree_node_t *node, btree_key_t key,
     491    void *value, btree_node_t *rsubtree, btree_key_t *median)
     492{
     493        btree_node_t *rnode;
     494        size_t i;
     495        size_t j;
     496       
     497        ASSERT(median);
     498        ASSERT(node->keys == BTREE_MAX_KEYS);
     499       
     500        /*
     501         * Use the extra space to store the extra node.
     502         */
     503        node_insert_key_and_rsubtree(node, key, value, rsubtree);
     504       
     505        /*
     506         * Compute median of keys.
     507         */
     508        *median = MEDIAN_HIGH(node);
     509       
     510        /*
     511         * Allocate and initialize new right sibling.
     512         */
     513        rnode = (btree_node_t *) slab_alloc(btree_node_slab, 0);
     514        node_initialize(rnode);
     515        rnode->parent = node->parent;
     516        rnode->depth = node->depth;
     517       
     518        /*
     519         * Copy big keys, values and subtree pointers to the new right sibling.
     520         * If this is an index node, do not copy the median.
     521         */
     522        i = (size_t) INDEX_NODE(node);
     523        for (i += MEDIAN_HIGH_INDEX(node), j = 0; i < node->keys; i++, j++) {
     524                rnode->key[j] = node->key[i];
     525                rnode->value[j] = node->value[i];
     526                rnode->subtree[j] = node->subtree[i];
     527               
     528                /*
     529                 * Fix parent links in subtrees.
     530                 */
     531                if (rnode->subtree[j])
     532                        rnode->subtree[j]->parent = rnode;
     533        }
     534       
     535        rnode->subtree[j] = node->subtree[i];
     536        if (rnode->subtree[j])
     537                rnode->subtree[j]->parent = rnode;
     538       
     539        rnode->keys = j;  /* Set number of keys of the new node. */
     540        node->keys /= 2;  /* Shrink the old node. */
     541       
     542        return rnode;
     543}
     544
    151545/** Recursively insert into B-tree.
    152546 *
    153  * @param t B-tree.
    154  * @param key Key to be inserted.
    155  * @param value Value to be inserted.
     547 * @param t        B-tree.
     548 * @param key      Key to be inserted.
     549 * @param value    Value to be inserted.
    156550 * @param rsubtree Right subtree of the inserted key.
    157  * @param node Start inserting into this node.
    158  */
    159 void _btree_insert(btree_t *t, btree_key_t key, void *value, btree_node_t *rsubtree, btree_node_t *node)
     551 * @param node     Start inserting into this node.
     552 *
     553 */
     554static void _btree_insert(btree_t *t, btree_key_t key, void *value,
     555    btree_node_t *rsubtree, btree_node_t *node)
    160556{
    161557        if (node->keys < BTREE_MAX_KEYS) {
     
    183579                 * bigger keys (i.e. the new node) into its parent.
    184580                 */
    185 
     581               
    186582                rnode = node_split(node, key, value, rsubtree, &median);
    187 
     583               
    188584                if (LEAF_NODE(node)) {
    189585                        list_prepend(&rnode->leaf_link, &node->leaf_link);
     
    202598                         * Left-hand side subtree will be the old root (i.e. node).
    203599                         * Right-hand side subtree will be rnode.
    204                          */                     
     600                         */
    205601                        t->root->subtree[0] = node;
    206 
     602                       
    207603                        t->root->depth = node->depth + 1;
    208604                }
    209605                _btree_insert(t, median, NULL, rnode, node->parent);
    210         }       
    211                
    212 }
    213 
    214 /** Remove B-tree node.
    215  *
    216  * @param t B-tree.
    217  * @param key Key to be removed from the B-tree along with its associated value.
    218  * @param leaf_node If not NULL, pointer to the leaf node where the key is found.
    219  */
    220 void btree_remove(btree_t *t, btree_key_t key, btree_node_t *leaf_node)
     606        }
     607}
     608
     609/** Insert key-value pair into B-tree.
     610 *
     611 * @param t         B-tree.
     612 * @param key       Key to be inserted.
     613 * @param value     Value to be inserted.
     614 * @param leaf_node Leaf node where the insertion should begin.
     615 *
     616 */
     617void btree_insert(btree_t *t, btree_key_t key, void *value,
     618    btree_node_t *leaf_node)
    221619{
    222620        btree_node_t *lnode;
     621       
     622        ASSERT(value);
    223623       
    224624        lnode = leaf_node;
    225625        if (!lnode) {
    226                 if (!btree_search(t, key, &lnode)) {
    227                         panic("B-tree %p does not contain key %" PRIu64 ".", t, key);
    228                 }
    229         }
    230        
    231         _btree_remove(t, key, lnode);
     626                if (btree_search(t, key, &lnode))
     627                        panic("B-tree %p already contains key %" PRIu64 ".", t, key);
     628        }
     629       
     630        _btree_insert(t, key, value, NULL, lnode);
     631}
     632
     633/** Rotate in a key from the left sibling or from the index node, if this operation can be done.
     634 *
     635 * @param rnode Node into which to add key from its left sibling
     636 *              or from the index node.
     637 *
     638 * @return True if the rotation was performed, false otherwise.
     639 *
     640 */
     641static bool try_rotation_from_left(btree_node_t *rnode)
     642{
     643        size_t idx;
     644        btree_node_t *lnode;
     645       
     646        /*
     647         * If this is root node, the rotation can not be done.
     648         */
     649        if (ROOT_NODE(rnode))
     650                return false;
     651       
     652        idx = find_key_by_subtree(rnode->parent, rnode, true);
     653        if ((int) idx == -1) {
     654                /*
     655                 * If this node is the leftmost subtree of its parent,
     656                 * the rotation can not be done.
     657                 */
     658                return false;
     659        }
     660       
     661        lnode = rnode->parent->subtree[idx];
     662        if (lnode->keys > FILL_FACTOR) {
     663                rotate_from_left(lnode, rnode, idx);
     664                return true;
     665        }
     666       
     667        return false;
     668}
     669
     670/** Rotate in a key from the right sibling or from the index node, if this operation can be done.
     671 *
     672 * @param lnode Node into which to add key from its right sibling
     673 *              or from the index node.
     674 *
     675 * @return True if the rotation was performed, false otherwise.
     676 *
     677 */
     678static bool try_rotation_from_right(btree_node_t *lnode)
     679{
     680        size_t idx;
     681        btree_node_t *rnode;
     682       
     683        /*
     684         * If this is root node, the rotation can not be done.
     685         */
     686        if (ROOT_NODE(lnode))
     687                return false;
     688       
     689        idx = find_key_by_subtree(lnode->parent, lnode, false);
     690        if (idx == lnode->parent->keys) {
     691                /*
     692                 * If this node is the rightmost subtree of its parent,
     693                 * the rotation can not be done.
     694                 */
     695                return false;
     696        }
     697       
     698        rnode = lnode->parent->subtree[idx + 1];
     699        if (rnode->keys > FILL_FACTOR) {
     700                rotate_from_right(lnode, rnode, idx);
     701                return true;
     702        }
     703       
     704        return false;
     705}
     706
     707/** Combine node with any of its siblings.
     708 *
     709 * The siblings are required to be below the fill factor.
     710 *
     711 * @param node Node to combine with one of its siblings.
     712 *
     713 * @return Pointer to the rightmost of the two nodes.
     714 *
     715 */
     716static btree_node_t *node_combine(btree_node_t *node)
     717{
     718        size_t idx;
     719        btree_node_t *rnode;
     720        size_t i;
     721       
     722        ASSERT(!ROOT_NODE(node));
     723       
     724        idx = find_key_by_subtree(node->parent, node, false);
     725        if (idx == node->parent->keys) {
     726                /*
     727                 * Rightmost subtree of its parent, combine with the left sibling.
     728                 */
     729                idx--;
     730                rnode = node;
     731                node = node->parent->subtree[idx];
     732        } else
     733                rnode = node->parent->subtree[idx + 1];
     734       
     735        /* Index nodes need to insert parent node key in between left and right node. */
     736        if (INDEX_NODE(node))
     737                node->key[node->keys++] = node->parent->key[idx];
     738       
     739        /* Copy the key-value-subtree triplets from the right node. */
     740        for (i = 0; i < rnode->keys; i++) {
     741                node->key[node->keys + i] = rnode->key[i];
     742                node->value[node->keys + i] = rnode->value[i];
     743               
     744                if (INDEX_NODE(node)) {
     745                        node->subtree[node->keys + i] = rnode->subtree[i];
     746                        rnode->subtree[i]->parent = node;
     747                }
     748        }
     749       
     750        if (INDEX_NODE(node)) {
     751                node->subtree[node->keys + i] = rnode->subtree[i];
     752                rnode->subtree[i]->parent = node;
     753        }
     754       
     755        node->keys += rnode->keys;
     756        return rnode;
    232757}
    233758
    234759/** Recursively remove B-tree node.
    235760 *
    236  * @param t B-tree.
    237  * @param key Key to be removed from the B-tree along with its associated value.
     761 * @param t    B-tree.
     762 * @param key  Key to be removed from the B-tree along with its associated value.
    238763 * @param node Node where the key being removed resides.
    239  */
    240 void _btree_remove(btree_t *t, btree_key_t key, btree_node_t *node)
     764 *
     765 */
     766static void _btree_remove(btree_t *t, btree_key_t key, btree_node_t *node)
    241767{
    242768        if (ROOT_NODE(node)) {
    243                 if (node->keys == 1 && node->subtree[0]) {
     769                if ((node->keys == 1) && (node->subtree[0])) {
    244770                        /*
    245771                         * Free the current root and set new root.
     
    257783                        node_remove_key_and_rsubtree(node, key);
    258784                }
     785               
    259786                return;
    260787        }
     
    271798        if (node->keys > FILL_FACTOR) {
    272799                size_t i;
    273 
     800               
    274801                /*
    275802                 * The key can be immediatelly removed.
     
    280807                 */
    281808                node_remove_key_and_rsubtree(node, key);
     809               
    282810                for (i = 0; i < node->parent->keys; i++) {
    283811                        if (node->parent->key[i] == key)
    284812                                node->parent->key[i] = node->key[0];
    285813                }
    286                
    287814        } else {
    288815                size_t idx;
    289                 btree_node_t *rnode, *parent;
    290 
     816                btree_node_t *rnode;
     817                btree_node_t *parent;
     818               
    291819                /*
    292820                 * The node is below the fill factor as well as its left and right sibling.
     
    298826                node_remove_key_and_rsubtree(node, key);
    299827                rnode = node_combine(node);
     828               
    300829                if (LEAF_NODE(rnode))
    301830                        list_remove(&rnode->leaf_link);
     831               
    302832                idx = find_key_by_subtree(parent, rnode, true);
    303833                ASSERT((int) idx != -1);
     
    307837}
    308838
     839/** Remove B-tree node.
     840 *
     841 * @param t         B-tree.
     842 * @param key       Key to be removed from the B-tree along
     843 *                  with its associated value.
     844 * @param leaf_node If not NULL, pointer to the leaf node where
     845 *                  the key is found.
     846 *
     847 */
     848void btree_remove(btree_t *t, btree_key_t key, btree_node_t *leaf_node)
     849{
     850        btree_node_t *lnode;
     851       
     852        lnode = leaf_node;
     853        if (!lnode) {
     854                if (!btree_search(t, key, &lnode))
     855                        panic("B-tree %p does not contain key %" PRIu64 ".", t, key);
     856        }
     857       
     858        _btree_remove(t, key, lnode);
     859}
     860
    309861/** Search key in a B-tree.
    310862 *
    311  * @param t B-tree.
    312  * @param key Key to be searched.
     863 * @param t         B-tree.
     864 * @param key       Key to be searched.
    313865 * @param leaf_node Address where to put pointer to visited leaf node.
    314866 *
    315867 * @return Pointer to value or NULL if there is no such key.
     868 *
    316869 */
    317870void *btree_search(btree_t *t, btree_key_t key, btree_node_t **leaf_node)
     
    323876         */
    324877        for (cur = t->root; cur; cur = next) {
    325 
    326                 /* Last iteration will set this with proper leaf node address. */
     878                /*
     879                 * Last iteration will set this with proper
     880                 * leaf node address.
     881                 */
    327882                *leaf_node = cur;
    328883               
     
    337892                        void *val;
    338893                        size_t i;
    339                
     894                       
    340895                        /*
    341896                         * Now if the key is smaller than cur->key[i]
     
    347902                                        next = cur->subtree[i];
    348903                                        val = cur->value[i - 1];
    349 
     904                                       
    350905                                        if (LEAF_NODE(cur))
    351906                                                return key == cur->key[i - 1] ? val : NULL;
    352 
     907                                       
    353908                                        goto descend;
    354                                 } 
     909                                }
    355910                        }
    356911                       
    357912                        /*
    358                          * Last possibility is that the key is in the rightmost subtree.
     913                         * Last possibility is that the key is
     914                         * in the rightmost subtree.
    359915                         */
    360916                        next = cur->subtree[i];
    361917                        val = cur->value[i - 1];
     918                       
    362919                        if (LEAF_NODE(cur))
    363920                                return key == cur->key[i - 1] ? val : NULL;
    364921                }
    365922                descend:
    366                         ;
    367         }
    368 
     923                ;
     924        }
     925       
    369926        /*
    370          * The key was not found in the *leaf_node and is smaller than any of its keys.
     927         * The key was not found in the *leaf_node and
     928         * is smaller than any of its keys.
    371929         */
    372930        return NULL;
     
    375933/** Return pointer to B-tree leaf node's left neighbour.
    376934 *
    377  * @param t B-tree.
     935 * @param t    B-tree.
    378936 * @param node Node whose left neighbour will be returned.
    379937 *
    380  * @return Left neighbour of the node or NULL if the node does not have the left neighbour.
     938 * @return Left neighbour of the node or NULL if the node
     939 *         does not have the left neighbour.
     940 *
    381941 */
    382942btree_node_t *btree_leaf_node_left_neighbour(btree_t *t, btree_node_t *node)
    383943{
    384944        ASSERT(LEAF_NODE(node));
     945       
    385946        if (node->leaf_link.prev != &t->leaf_head)
    386947                return list_get_instance(node->leaf_link.prev, btree_node_t, leaf_link);
     
    391952/** Return pointer to B-tree leaf node's right neighbour.
    392953 *
    393  * @param t B-tree.
     954 * @param t    B-tree.
    394955 * @param node Node whose right neighbour will be returned.
    395956 *
    396  * @return Right neighbour of the node or NULL if the node does not have the right neighbour.
     957 * @return Right neighbour of the node or NULL if the node
     958 *         does not have the right neighbour.
     959 *
    397960 */
    398961btree_node_t *btree_leaf_node_right_neighbour(btree_t *t, btree_node_t *node)
    399962{
    400963        ASSERT(LEAF_NODE(node));
     964       
    401965        if (node->leaf_link.next != &t->leaf_head)
    402966                return list_get_instance(node->leaf_link.next, btree_node_t, leaf_link);
     
    405969}
    406970
    407 /** Initialize B-tree node.
    408  *
    409  * @param node B-tree node.
    410  */
    411 void node_initialize(btree_node_t *node)
    412 {
    413         int i;
    414 
    415         node->keys = 0;
    416        
    417         /* Clean also space for the extra key. */
    418         for (i = 0; i < BTREE_MAX_KEYS + 1; i++) {
    419                 node->key[i] = 0;
    420                 node->value[i] = NULL;
    421                 node->subtree[i] = NULL;
    422         }
    423         node->subtree[i] = NULL;
    424        
    425         node->parent = NULL;
    426        
    427         link_initialize(&node->leaf_link);
    428 
    429         link_initialize(&node->bfs_link);
    430         node->depth = 0;
    431 }
    432 
    433 /** Insert key-value-lsubtree triplet into B-tree node.
    434  *
    435  * It is actually possible to have more keys than BTREE_MAX_KEYS.
    436  * This feature is used during insert by right rotation.
    437  *
    438  * @param node B-tree node into wich the new key is to be inserted.
    439  * @param key The key to be inserted.
    440  * @param value Pointer to value to be inserted.
    441  * @param lsubtree Pointer to the left subtree.
    442  */
    443 void node_insert_key_and_lsubtree(btree_node_t *node, btree_key_t key, void *value, btree_node_t *lsubtree)
    444 {
    445         size_t i;
    446 
    447         for (i = 0; i < node->keys; i++) {
    448                 if (key < node->key[i]) {
    449                         size_t j;
    450                
    451                         for (j = node->keys; j > i; j--) {
    452                                 node->key[j] = node->key[j - 1];
    453                                 node->value[j] = node->value[j - 1];
    454                                 node->subtree[j + 1] = node->subtree[j];
    455                         }
    456                         node->subtree[j + 1] = node->subtree[j];
    457                         break; 
    458                 }
    459         }
    460         node->key[i] = key;
    461         node->value[i] = value;
    462         node->subtree[i] = lsubtree;
    463                        
    464         node->keys++;
    465 }
    466 
    467 /** Insert key-value-rsubtree triplet into B-tree node.
    468  *
    469  * It is actually possible to have more keys than BTREE_MAX_KEYS.
    470  * This feature is used during splitting the node when the
    471  * number of keys is BTREE_MAX_KEYS + 1. Insert by left rotation
    472  * also makes use of this feature.
    473  *
    474  * @param node B-tree node into wich the new key is to be inserted.
    475  * @param key The key to be inserted.
    476  * @param value Pointer to value to be inserted.
    477  * @param rsubtree Pointer to the right subtree.
    478  */
    479 void node_insert_key_and_rsubtree(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree)
    480 {
    481         size_t i;
    482 
    483         for (i = 0; i < node->keys; i++) {
    484                 if (key < node->key[i]) {
    485                         size_t j;
    486                
    487                         for (j = node->keys; j > i; j--) {
    488                                 node->key[j] = node->key[j - 1];
    489                                 node->value[j] = node->value[j - 1];
    490                                 node->subtree[j + 1] = node->subtree[j];
    491                         }
    492                         break; 
    493                 }
    494         }
    495         node->key[i] = key;
    496         node->value[i] = value;
    497         node->subtree[i + 1] = rsubtree;
    498                        
    499         node->keys++;
    500 }
    501 
    502 /** Remove key and its left subtree pointer from B-tree node.
    503  *
    504  * Remove the key and eliminate gaps in node->key array.
    505  * Note that the value pointer and the left subtree pointer
    506  * is removed from the node as well.
    507  *
    508  * @param node B-tree node.
    509  * @param key Key to be removed.
    510  */
    511 void node_remove_key_and_lsubtree(btree_node_t *node, btree_key_t key)
    512 {
    513         size_t i, j;
    514        
    515         for (i = 0; i < node->keys; i++) {
    516                 if (key == node->key[i]) {
    517                         for (j = i + 1; j < node->keys; j++) {
    518                                 node->key[j - 1] = node->key[j];
    519                                 node->value[j - 1] = node->value[j];
    520                                 node->subtree[j - 1] = node->subtree[j];
    521                         }
    522                         node->subtree[j - 1] = node->subtree[j];
    523                         node->keys--;
    524                         return;
    525                 }
    526         }
    527         panic("Node %p does not contain key %" PRIu64 ".", node, key);
    528 }
    529 
    530 /** Remove key and its right subtree pointer from B-tree node.
    531  *
    532  * Remove the key and eliminate gaps in node->key array.
    533  * Note that the value pointer and the right subtree pointer
    534  * is removed from the node as well.
    535  *
    536  * @param node B-tree node.
    537  * @param key Key to be removed.
    538  */
    539 void node_remove_key_and_rsubtree(btree_node_t *node, btree_key_t key)
    540 {
    541         size_t i, j;
    542        
    543         for (i = 0; i < node->keys; i++) {
    544                 if (key == node->key[i]) {
    545                         for (j = i + 1; j < node->keys; j++) {
    546                                 node->key[j - 1] = node->key[j];
    547                                 node->value[j - 1] = node->value[j];
    548                                 node->subtree[j] = node->subtree[j + 1];
    549                         }
    550                         node->keys--;
    551                         return;
    552                 }
    553         }
    554         panic("Node %p does not contain key %" PRIu64 ".", node, key);
    555 }
    556 
    557 /** Split full B-tree node and insert new key-value-right-subtree triplet.
    558  *
    559  * This function will split a node and return a pointer to a newly created
    560  * node containing keys greater than or equal to the greater of medians
    561  * (or median) of the old keys and the newly added key. It will also write
    562  * the median key to a memory address supplied by the caller.
    563  *
    564  * If the node being split is an index node, the median will not be
    565  * included in the new node. If the node is a leaf node,
    566  * the median will be copied there.
    567  *
    568  * @param node B-tree node wich is going to be split.
    569  * @param key The key to be inserted.
    570  * @param value Pointer to the value to be inserted.
    571  * @param rsubtree Pointer to the right subtree of the key being added.
    572  * @param median Address in memory, where the median key will be stored.
    573  *
    574  * @return Newly created right sibling of node.
    575  */
    576 btree_node_t *node_split(btree_node_t *node, btree_key_t key, void *value, btree_node_t *rsubtree, btree_key_t *median)
    577 {
    578         btree_node_t *rnode;
    579         size_t i, j;
    580 
    581         ASSERT(median);
    582         ASSERT(node->keys == BTREE_MAX_KEYS);
    583 
    584         /*
    585          * Use the extra space to store the extra node.
    586          */
    587         node_insert_key_and_rsubtree(node, key, value, rsubtree);
    588 
    589         /*
    590          * Compute median of keys.
    591          */
    592         *median = MEDIAN_HIGH(node);
    593                
    594         /*
    595          * Allocate and initialize new right sibling.
    596          */
    597         rnode = (btree_node_t *) slab_alloc(btree_node_slab, 0);
    598         node_initialize(rnode);
    599         rnode->parent = node->parent;
    600         rnode->depth = node->depth;
    601        
    602         /*
    603          * Copy big keys, values and subtree pointers to the new right sibling.
    604          * If this is an index node, do not copy the median.
    605          */
    606         i = (size_t) INDEX_NODE(node);
    607         for (i += MEDIAN_HIGH_INDEX(node), j = 0; i < node->keys; i++, j++) {
    608                 rnode->key[j] = node->key[i];
    609                 rnode->value[j] = node->value[i];
    610                 rnode->subtree[j] = node->subtree[i];
    611                
    612                 /*
    613                  * Fix parent links in subtrees.
    614                  */
    615                 if (rnode->subtree[j])
    616                         rnode->subtree[j]->parent = rnode;
    617                        
    618         }
    619         rnode->subtree[j] = node->subtree[i];
    620         if (rnode->subtree[j])
    621                 rnode->subtree[j]->parent = rnode;
    622 
    623         rnode->keys = j;        /* Set number of keys of the new node. */
    624         node->keys /= 2;        /* Shrink the old node. */
    625                
    626         return rnode;
    627 }
    628 
    629 /** Combine node with any of its siblings.
    630  *
    631  * The siblings are required to be below the fill factor.
    632  *
    633  * @param node Node to combine with one of its siblings.
    634  *
    635  * @return Pointer to the rightmost of the two nodes.
    636  */
    637 btree_node_t *node_combine(btree_node_t *node)
    638 {
    639         size_t idx;
    640         btree_node_t *rnode;
    641         size_t i;
    642 
    643         ASSERT(!ROOT_NODE(node));
    644        
    645         idx = find_key_by_subtree(node->parent, node, false);
    646         if (idx == node->parent->keys) {
    647                 /*
    648                  * Rightmost subtree of its parent, combine with the left sibling.
    649                  */
    650                 idx--;
    651                 rnode = node;
    652                 node = node->parent->subtree[idx];
    653         } else {
    654                 rnode = node->parent->subtree[idx + 1];
    655         }
    656 
    657         /* Index nodes need to insert parent node key in between left and right node. */
    658         if (INDEX_NODE(node))
    659                 node->key[node->keys++] = node->parent->key[idx];
    660        
    661         /* Copy the key-value-subtree triplets from the right node. */
    662         for (i = 0; i < rnode->keys; i++) {
    663                 node->key[node->keys + i] = rnode->key[i];
    664                 node->value[node->keys + i] = rnode->value[i];
    665                 if (INDEX_NODE(node)) {
    666                         node->subtree[node->keys + i] = rnode->subtree[i];
    667                         rnode->subtree[i]->parent = node;
    668                 }
    669         }
    670         if (INDEX_NODE(node)) {
    671                 node->subtree[node->keys + i] = rnode->subtree[i];
    672                 rnode->subtree[i]->parent = node;
    673         }
    674 
    675         node->keys += rnode->keys;
    676 
    677         return rnode;
    678 }
    679 
    680 /** Find key by its left or right subtree.
    681  *
    682  * @param node B-tree node.
    683  * @param subtree Left or right subtree of a key found in node.
    684  * @param right If true, subtree is a right subtree. If false, subtree is a left subtree.
    685  *
    686  * @return Index of the key associated with the subtree.
    687  */
    688 size_t find_key_by_subtree(btree_node_t *node, btree_node_t *subtree, bool right)
    689 {
    690         size_t i;
    691        
    692         for (i = 0; i < node->keys + 1; i++) {
    693                 if (subtree == node->subtree[i])
    694                         return i - (int) (right != false);
    695         }
    696         panic("Node %p does not contain subtree %p.", node, subtree);
    697 }
    698 
    699 /** Rotate one key-value-rsubtree triplet from the left sibling to the right sibling.
    700  *
    701  * The biggest key and its value and right subtree is rotated from the left node
    702  * to the right. If the node is an index node, than the parent node key belonging to
    703  * the left node takes part in the rotation.
    704  *
    705  * @param lnode Left sibling.
    706  * @param rnode Right sibling.
    707  * @param idx Index of the parent node key that is taking part in the rotation.
    708  */
    709 void rotate_from_left(btree_node_t *lnode, btree_node_t *rnode, size_t idx)
    710 {
    711         btree_key_t key;
    712 
    713         key = lnode->key[lnode->keys - 1];
    714                
    715         if (LEAF_NODE(lnode)) {
    716                 void *value;
    717 
    718                 value = lnode->value[lnode->keys - 1];
    719                 node_remove_key_and_rsubtree(lnode, key);
    720                 node_insert_key_and_lsubtree(rnode, key, value, NULL);
    721                 lnode->parent->key[idx] = key;
    722         } else {
    723                 btree_node_t *rsubtree;
    724 
    725                 rsubtree = lnode->subtree[lnode->keys];
    726                 node_remove_key_and_rsubtree(lnode, key);
    727                 node_insert_key_and_lsubtree(rnode, lnode->parent->key[idx], NULL, rsubtree);
    728                 lnode->parent->key[idx] = key;
    729 
    730                 /* Fix parent link of the reconnected right subtree. */
    731                 rsubtree->parent = rnode;
    732         }
    733 
    734 }
    735 
    736 /** Rotate one key-value-lsubtree triplet from the right sibling to the left sibling.
    737  *
    738  * The smallest key and its value and left subtree is rotated from the right node
    739  * to the left. If the node is an index node, than the parent node key belonging to
    740  * the right node takes part in the rotation.
    741  *
    742  * @param lnode Left sibling.
    743  * @param rnode Right sibling.
    744  * @param idx Index of the parent node key that is taking part in the rotation.
    745  */
    746 void rotate_from_right(btree_node_t *lnode, btree_node_t *rnode, size_t idx)
    747 {
    748         btree_key_t key;
    749 
    750         key = rnode->key[0];
    751                
    752         if (LEAF_NODE(rnode)) {
    753                 void *value;
    754 
    755                 value = rnode->value[0];
    756                 node_remove_key_and_lsubtree(rnode, key);
    757                 node_insert_key_and_rsubtree(lnode, key, value, NULL);
    758                 rnode->parent->key[idx] = rnode->key[0];
    759         } else {
    760                 btree_node_t *lsubtree;
    761 
    762                 lsubtree = rnode->subtree[0];
    763                 node_remove_key_and_lsubtree(rnode, key);
    764                 node_insert_key_and_rsubtree(lnode, rnode->parent->key[idx], NULL, lsubtree);
    765                 rnode->parent->key[idx] = key;
    766 
    767                 /* Fix parent link of the reconnected left subtree. */
    768                 lsubtree->parent = lnode;
    769         }
    770 
    771 }
    772 
    773 /** Insert key-value-rsubtree triplet and rotate the node to the left, if this operation can be done.
    774  *
    775  * Left sibling of the node (if it exists) is checked for free space.
    776  * If there is free space, the key is inserted and the smallest key of
    777  * the node is moved there. The index node which is the parent of both
    778  * nodes is fixed.
    779  *
    780  * @param node B-tree node.
    781  * @param inskey Key to be inserted.
    782  * @param insvalue Value to be inserted.
    783  * @param rsubtree Right subtree of inskey.
    784  *
    785  * @return True if the rotation was performed, false otherwise.
    786  */
    787 bool try_insert_by_rotation_to_left(btree_node_t *node, btree_key_t inskey, void *insvalue, btree_node_t *rsubtree)
    788 {
    789         size_t idx;
    790         btree_node_t *lnode;
    791 
    792         /*
    793          * If this is root node, the rotation can not be done.
    794          */
    795         if (ROOT_NODE(node))
    796                 return false;
    797        
    798         idx = find_key_by_subtree(node->parent, node, true);
    799         if ((int) idx == -1) {
    800                 /*
    801                  * If this node is the leftmost subtree of its parent,
    802                  * the rotation can not be done.
    803                  */
    804                 return false;
    805         }
    806                
    807         lnode = node->parent->subtree[idx];
    808         if (lnode->keys < BTREE_MAX_KEYS) {
    809                 /*
    810                  * The rotaion can be done. The left sibling has free space.
    811                  */
    812                 node_insert_key_and_rsubtree(node, inskey, insvalue, rsubtree);
    813                 rotate_from_right(lnode, node, idx);
    814                 return true;
    815         }
    816 
    817         return false;
    818 }
    819 
    820 /** Insert key-value-rsubtree triplet and rotate the node to the right, if this operation can be done.
    821  *
    822  * Right sibling of the node (if it exists) is checked for free space.
    823  * If there is free space, the key is inserted and the biggest key of
    824  * the node is moved there. The index node which is the parent of both
    825  * nodes is fixed.
    826  *
    827  * @param node B-tree node.
    828  * @param inskey Key to be inserted.
    829  * @param insvalue Value to be inserted.
    830  * @param rsubtree Right subtree of inskey.
    831  *
    832  * @return True if the rotation was performed, false otherwise.
    833  */
    834 bool try_insert_by_rotation_to_right(btree_node_t *node, btree_key_t inskey, void *insvalue, btree_node_t *rsubtree)
    835 {
    836         size_t idx;
    837         btree_node_t *rnode;
    838 
    839         /*
    840          * If this is root node, the rotation can not be done.
    841          */
    842         if (ROOT_NODE(node))
    843                 return false;
    844        
    845         idx = find_key_by_subtree(node->parent, node, false);
    846         if (idx == node->parent->keys) {
    847                 /*
    848                  * If this node is the rightmost subtree of its parent,
    849                  * the rotation can not be done.
    850                  */
    851                 return false;
    852         }
    853                
    854         rnode = node->parent->subtree[idx + 1];
    855         if (rnode->keys < BTREE_MAX_KEYS) {
    856                 /*
    857                  * The rotaion can be done. The right sibling has free space.
    858                  */
    859                 node_insert_key_and_rsubtree(node, inskey, insvalue, rsubtree);
    860                 rotate_from_left(node, rnode, idx);
    861                 return true;
    862         }
    863 
    864         return false;
    865 }
    866 
    867 /** Rotate in a key from the left sibling or from the index node, if this operation can be done.
    868  *
    869  * @param rnode Node into which to add key from its left sibling or from the index node.
    870  *
    871  * @return True if the rotation was performed, false otherwise.
    872  */
    873 bool try_rotation_from_left(btree_node_t *rnode)
    874 {
    875         size_t idx;
    876         btree_node_t *lnode;
    877 
    878         /*
    879          * If this is root node, the rotation can not be done.
    880          */
    881         if (ROOT_NODE(rnode))
    882                 return false;
    883        
    884         idx = find_key_by_subtree(rnode->parent, rnode, true);
    885         if ((int) idx == -1) {
    886                 /*
    887                  * If this node is the leftmost subtree of its parent,
    888                  * the rotation can not be done.
    889                  */
    890                 return false;
    891         }
    892                
    893         lnode = rnode->parent->subtree[idx];
    894         if (lnode->keys > FILL_FACTOR) {
    895                 rotate_from_left(lnode, rnode, idx);
    896                 return true;
    897         }
    898        
    899         return false;
    900 }
    901 
    902 /** Rotate in a key from the right sibling or from the index node, if this operation can be done.
    903  *
    904  * @param lnode Node into which to add key from its right sibling or from the index node.
    905  *
    906  * @return True if the rotation was performed, false otherwise.
    907  */
    908 bool try_rotation_from_right(btree_node_t *lnode)
    909 {
    910         size_t idx;
    911         btree_node_t *rnode;
    912 
    913         /*
    914          * If this is root node, the rotation can not be done.
    915          */
    916         if (ROOT_NODE(lnode))
    917                 return false;
    918        
    919         idx = find_key_by_subtree(lnode->parent, lnode, false);
    920         if (idx == lnode->parent->keys) {
    921                 /*
    922                  * If this node is the rightmost subtree of its parent,
    923                  * the rotation can not be done.
    924                  */
    925                 return false;
    926         }
    927                
    928         rnode = lnode->parent->subtree[idx + 1];
    929         if (rnode->keys > FILL_FACTOR) {
    930                 rotate_from_right(lnode, rnode, idx);
    931                 return true;
    932         }       
    933 
    934         return false;
    935 }
    936 
    937971/** Print B-tree.
    938972 *
    939<