(19) United States
`(12) Patent Application Publication (10) Pub. No.: US 2005/0246705 A1
`Etels0n et al.
`(43) Pub. Date:
`Nov. 3, 2005
`
`US 2005O246705A1
`
`(54) METHOD FOR DYNAMICALLY
`ALLOCATING AND MANAGING
`RESOURCES IN A COMPUTERIZED
`SYSTEM HAVING MULTIPLE CONSUMERS
`(75) Inventors: Garik Etelson, Kiryat Ono (IL);
`Gregory Bondar, Rishon LeZion (IL);
`Michael Stoler, Yahud (IL)
`Correspondence Address:
`FLEIT KAIN GIBBONS GUTMAN BONGINI
`& BIANCO
`21355 EAST DIXIE HIGHWAY
`SUTE 115
`MIAMI, FL 33180 (US)
`(73) Assignee: SPHERA CORPORATION, NEW
`TON, MA
`(21) Appl. No.:
`11/042,478
`(22) Filed:
`Jan. 25, 2005
`Related U.S. Application Data
`(63) Continuation of application No. PCT/IL03/00619,
`filed on Jul. 25, 2003.
`
`(30)
`
`Foreign Application Priority Data
`
`Jul. 25, 2002 (IL)................................................. 150911
`
`Publication Classification
`
`(51) Int. Cl. ................................................... G06F 9/46
`(52) U.S. Cl. .............................................................. 718/100
`
`(57)
`
`ABSTRACT
`
`Method for dynamically allocating and managing resources
`in a computerized System managed by an operating System
`(OS) and having multiple accounts of consumers. Portions
`of the Virtual memory address Space are allocated, whenever
`desired, in a Swap file, for each account associated with a
`consumer. The memory address Space is limited for each
`account. The CPU usage is divided between the tasks
`requested from each account, and Segments in the original
`code of the OS are changed by locating one or more specific
`procedures in the original code, and modifying the Specific
`procedures to operate according to the allocation and/or the
`limitation of the memory address Space and/or the limitation
`of the number of processes and/or the divided CPU usage.
`
`Copied code
`Original commands
`
`
`
`
`
`Jump to Continue of
`Code
`
`22
`
`2O
`Original code /
`
`Original COde .
`
`New Code
`Pre-check
`Caloriginal Code
`Post-check
`
`21
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1031, p. 1
`
`

`

`Patent Application Publication Nov. 3, 2005 Sheet 1 of 3
`
`US 2005/0246705 A1
`
`so
`
`SN
`
`y
`
`o
`
`so
`
`9
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1031, p. 2
`
`

`

`Patent Application Publication Nov. 3, 2005 Sheet 2 of 3
`
`US 2005/0246705 A1
`
`20
`Original code /
`
`Original Code .
`
`Copied code
`Original Commands
`
`
`
`Jump to Continue of
`Code
`
`22
`
`
`
`New Code .
`Pre-check
`Call original Code
`Post-check
`
`21
`
`Fig. 2
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1031, p. 3
`
`

`

`Patent Application Publication Nov. 3, 2005 Sheet 3 of 3
`
`US 2005/0246705 A1
`
`31
`
`32
`
`Fig. 3
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1031, p. 4
`
`

`

`US 2005/0246705 A1
`
`Nov. 3, 2005
`
`METHOD FOR DYNAMICALLY ALLOCATING
`AND MANAGING RESOURCES IN A
`COMPUTERIZED SYSTEM HAVING MULTIPLE
`CONSUMERS
`
`RELATED APPLICATION
`0001. This application is a continuation of International
`Patent Application Serial number PCT/IL2003/000619 filed
`Jul. 25, 2003, the contents of which are here incorporated by
`reference in their entirety. The benefit of 35 USC Section
`120 is here claimed.
`
`BACKGROUND OF THE INVENTION
`0002) 1. Field of the Invention
`0003. The present invention relates to the field of man
`aging a computerized System. More particularly, the inven
`tion relates to a method for limiting the resources that are
`used by consumers, Systems and Web Services of a given
`computerized System.
`0004 2. Prior Art
`0005 Hosting a Website locally is relatively expensive,
`as it requires allocating Sufficient bandwidth for Internet
`traffic to the Site, as well as allocating resources for keeping
`the site available all the time (both in terms of software and
`hardware) and handling Security aspects, Such as a firewall.
`0006 Web Hosting Providers (WHP), which are the
`consumers of a computerized system, use a variety of
`Service models to address different types of customers,
`depending on the required class of service. The Web sites of
`Small and medium-sized businesses normally do not pre
`empt the resources afforded by a dedicated Server, and
`therefore might settle for a shared server model. However, as
`the requirements of the WHP change and their sites conduct
`more and more activity, they become more resource-con
`suming. When WHPs become more resource consuming,
`they usually, hire more resources, or keep the same resources
`with decreased performance. AS the demand for the site's
`Services is not constant over a time period, the customer
`might prefer to keep the same resources rather than hiring
`more resources, assuming that a relatively high demand for
`resources might occur for only a relatively short duration.
`0007 Typically, each dedicated server runs an instance of
`the OS (Operation System). However, running an instance of
`the OS for each dedicated Server comparatively requires a
`large amount of resources, which is required for each
`instance of the OS.
`0008 Hereinafter, the term “computerized system” refers
`to a server that hosts a plurality of Virtual dedicated Servers
`that execute a plurality of Services, wherein each Virtual
`dedicated Server utilizes a Substantial portion of the com
`puter resources.
`0009. A virtual dedicated server in such a computerized
`System is actually an emulation of a computer System's
`interface in which a remote client can acceSS its System
`utilities and programs, and it will be called hereinafter a
`Virtual Dedicated Server (VDS). A plurality of VDS
`instances can be executed Simultaneously on a single hosting
`computerized System.
`0.010 The term “account” refers to a certain part of the
`machine's resources that is allocated to a specific user. An
`
`account might share its allocated resource with other
`accounts, but together they can not utilize more than their
`allocated share. An “account' can be allocated to a user, a
`domain, a VDS, a Service, a Specific processes or process
`groups or to any other Suitable user of the machine's
`CSOUCCS.
`0011. One of the existing solutions for limiting the
`resources consumption of an account is to use a Static
`division of the computer resources. The hosting computer
`resources are divided in a Static manner between the Virtual
`computers. The result is that if, for example, the real
`computer is split into 10 identical virtual computers, then
`10% of the system resources are allocated to each virtual
`computer, even if only one virtual computer is being oper
`ated. A dynamic resource allocation would result in a better
`performance per virtual computer (if not all the VDSs are
`activated at the same time), with an appropriate allocation to
`each VDS (according to predefined parameters) in the case
`that a plurality of VDSS are activated at the same time.
`Therefore, the dynamic resource allocation results in a better
`performance from the user's point of view. The dynamic
`resource allocation can be used by any consumer of the
`computer resources, Such as different Services, different
`uSerS, etc.
`0012 Resources of a computerized system are limited
`due to Several factorS Such as budget, Spatial restrictions, etc.
`ReSources of a computerized System comprise, among oth
`ers, the usage of a Central Processing Unit (CPU), the size
`of a memory address Space, Storage capabilities of data, etc.
`A computerized System used by multiple consumers,
`whether they are WHP or regular consumers, needs to
`provide to each of its consumers, at least, a predefined
`percentage of its resources according to predefined terms or
`agreements between each consumer and the corresponding
`resources owner in the computerized system. a WHP may
`offer more than the actual available resources, based on the
`low probability that all consumers will concurrently demand
`maximum resources. Therefore, in order to enable different
`consumers to have their predefined share of resources, there
`is a need to limit the resources available to a specific
`consumer according to those predefined for him. Additional
`reasons for limiting the resources consumption for each
`consumer in a multiple consumer computerized System may
`be as follows:
`0013 If the resources are not of a preempt kind (i.e.,
`non-preemptable), then a Suitable process in the computer
`ized System should free those resources by itself, upon
`receipt of Such a resource. For example, the memory or a
`Suitable Storage disk of a computerized System is usually
`non-preemptable. Granting a higher number of resources
`might prevent a process, before the previous resources were
`freed, from getting its share. Unfortunately, it is relatively
`complicated to remove the resources, once granted.
`0014) If the resources are of a preempt kind (i.e., pre
`emptable), then in every time-slice they are divided between
`the requesting processes. For example, a CPU is usually a
`preemptable resource. When dealing with preemptable
`resources, there are two possibilities to deal with the unused
`resources, as the allocation is performed on every time-slice
`from Scratch. The first, granting the process more than his
`allocated Share will make the user treat Such performance as
`his base line. However, when additional consumers connect
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1031, p. 5
`
`

`

`US 2005/0246705 A1
`
`Nov. 3, 2005
`
`to the computerized System and Start to utilize their share of
`resources, then the previous consumers connected to Such a
`system will suffer from a reduction in their total perfor
`mance. The Second, limiting the resources from the begin
`ning, might prevent Such a situation, but is less desirable
`from the end-user's point of view.
`0.015
`If the resources are preemptable and an owner of a
`computerized System wishes to charge each of his consum
`erS differently, according to the guaranteed resources of
`each, the owner will accordingly wish to confine the con
`Sumer to his allocated share of resources.
`0016. There are several companies, such as “Ensim Cor
`poration', that create “static virtual computers” within the
`computer. Each “static virtual computer is allocated a
`certain amount of CPU, memory etc. However, the comput
`er's owner is not able to allow the Static virtual computer to
`use more than its allocated share, in case other users do not
`use their allocated share, and therefore there are available
`CSOUCCS.
`0.017. Furthermore, in a static virtual computer, for
`example, if the WHPs want to allocate the computer
`resources to 2 different resellers (i.e., 50% for each reseller),
`and one of the resellers wants to Supply his allocated part to
`2 additional users, guaranteeing 75% (of his allocated part)
`for each, Such hierarchical allocation can not be done. This
`is because 25% from the allocated resources for each user is
`less than the guaranteed resources, and 37.5% is too much
`to allow the consumers to use, as other users of the other
`reseller might be influenced.
`0.018. In the prior art, a common method of allocating
`resources of a computerized System is to provide a prede
`termined amount of resources to each consumer. However,
`Such a method has Several drawbacks, Such as in a comput
`erized System with a relatively high number of consumers,
`adding a new consumer to Such a System requires re
`allocating the resources for all the other consumers. For
`example, if the owner of a computerized System wants to
`share its System resources "evenly’ between its consumers,
`then, for example in the case of 10 consumers-he grants
`10% of the system's resources to each (i.e., 100% of the
`System resources is allocated to all consumers). If, however,
`the owner wants to add an additional consumer to that
`System, he must update the allocated resources to each of the
`existing 10 consumers, in Such a way that there will be
`available resources to the new added consumer. If there are
`numerous clients (e.g., 100, 1000 or more), this task will
`involve considerable time and/or might be prone to user
`errors while allocating all the resources for all the consumers
`each time there is a change of Status in the System. The task
`of re-allocating resources increases in complexity where one
`or more consumers are granted more resources than the
`others. More complexity occurs if the owner of the com
`puterized System has “resellers” (i.e., consumers entitled to
`share resources with their own consumers). Typically, a
`comparison is made between what the account consumes
`and its allocated quota. However, the Software re-calculates
`the System resources on each operation that might utilize
`resources. For example, if the resource that is checked for
`the comparison is memory, the comparison should be per
`formed only before memory allocations, however this is
`inefficient for Suitable allocation due to the fact that it is only
`done before.
`
`0019 All the methods described above have not yet
`provided satisfactory solutions to the problem of efficiently
`allocating and managing resources of a computerized System
`with multiple consumers.
`
`SUMMARY OF THE INVENTION
`0020. It is an object of the present invention to provide a
`method for individually limiting the resources consumption
`of each consumer, whether it is a Service or a user.
`0021. It is an object of the present invention to provide a
`method for better allocating the resources between the
`COSUCS.
`0022. It is still another object of the present invention to
`provide a method for allocating resources with a desired
`hierarchy.
`0023. It is a further object of the present invention to
`provide a method and System for calculating the allocated
`resources, dynamically and on demand.
`0024.
`It is yet an object of the present invention to
`provide a method and System for allowing a consumer to
`observe the current resource allocation.
`0025. Other objects and advantages of the invention will
`become apparent as the description proceeds.
`0026. The present invention is directed to a method for
`dynamically allocating and managing resources in a com
`puterized System managed by an operating System (OS) and
`having multiple accounts of consumerS. Portions of the
`Virtual memory address Space are allocated, whenever
`desired, in a Swap file, for each account associated with a
`consumer. The memory address Space is limited for each
`account. The CPU usage is divided between the tasks
`requested from each account, and Segments in the original
`code of the OS are changed by locating one or more specific
`procedures in the original code, and modifying the Specific
`procedures to operate according to the allocation and/or the
`limitation of the memory address Space and/or the limitation
`of the number of processes and/or the divided CPU usage.
`0027 Preferably, the specific procedures are dynamically
`modifying to operate in response to varying allocation
`and/or limitation of the memory address Space and/or the
`divided CPU usage. The location of the required procedure
`is allowed by obtaining the name of the required procedure
`that is Stored in a Symbol table, or by identifying a sequence
`of bytes of the required procedure.
`0028. In order to modify a specific procedure, the allo
`cated memory address Space is obtained and creating an
`executable code in the allocated memory address Space.
`Code Segments from the original code are copied, the
`commands line at the beginning of the copied code are Saved
`and further commands are skipping until beginning of the
`next command in the original code. The commands line at
`the beginning of the original code is replaced by Skipping to
`the beginning of the created application, and adding non
`operational bytes to the unused bytes of the created appli
`cation. The blank bytes may be No Operations (NOPs) data.
`0029. The limitation of the memory address space is
`implemented by calling the original code whenever the call
`for consuming resources is not by an account of a specific
`consumer, and identifying the account by its related param
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1031, p. 6
`
`

`

`US 2005/0246705 A1
`
`Nov. 3, 2005
`
`eters. It is verified that the account will not exceed its quota,
`or the quota of the level above it according to the allocated
`memory address Space, whenever resource consumption is
`required by an account. The result of an operation related to
`the account, whenever it Succeeds is checked and the con
`Sumption data of the account and/or of the levels above the
`account is updated. The identifying parameters may be a
`user ID, group ID or program name.
`0.030. When limiting the number of processes it is veri
`fied that the account will not exceed its quota, or the quota
`of the level above it, according to the allocated number of
`processes, whenever resource consumption is required by an
`account. The result of an operation related to the account,
`whenever it Succeeds, is checked and the consumption data
`of the account and/or of the levels above the account is
`updated. The identifying parameters may be a userID, group
`ID or program name.
`0.031 CPU resources that are not demanded by accounts
`according to their resource allocation policy are dynamically
`allocated to other demanding accounts and the available
`CPU resources are divided between all the tasks according
`to an optimal share allocation per each account. Division of
`the CPU usage between the tasks may be obtained by
`modifying the calculation of the “counter of the tasks that
`are candidates for being executed, So that each task is limited
`by the quota of the account that is associated with the taskS.
`0.032 The modification of the counter calculation is per
`formed by intercepting the function that performs the cal
`culation of the “counters”. Then, the desired “counter value
`is calculated for each task, based on the guaranteed value to
`the user account and holding the correct value of the counter
`according to the quotas when its value is calculated when
`ever there are Several tasks that belong to the same account.
`The “counter value of the tasks is Summed according to the
`account, while their internal allocation is currently per
`formed according to their usage. Information regarding the
`“behavior” of each process is kept and the amount of CPU
`resource that the account received during the last time is
`calculated on every "tick', and the calculated amount is
`added to the levels above the account. Whenever the account
`or a level above the account receives more than its allocated
`share, the “counter of the task is decreased to Zero, until the
`next CPU allocation is done. Whenever a decision is made
`about the next task to be executed, it is confirmed that the
`Selection of the next task to be executed is valid.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`0033. The above and other characteristics and advantages
`of the invention will be better understood through the
`following illustrative and non-limitative detailed description
`of preferred embodiments thereof, with reference to the
`appended drawings, wherein:
`0034 FIG. 1 schematically illustrates hierarchical allo
`cation of resources in a computerized System with multiple
`consumers, according to a preferred embodiment of the
`invention;
`0.035
`FIG. 2 schematically illustrates a modification of a
`required procedure as part of changing the OS behavior,
`according to a preferred embodiment of the invention; and
`0036 FIG. 3 schematically illustrates the CPU usage by
`a Specific account.
`
`DETAILED DESCRIPTION OF PREFERRED
`EMBODIMENTS
`0037. In order to prevent consumers from exceeding the
`allocated resources in a computerized System, there is a need
`to limit the resources, Such as the memory, number of
`processes and the CPU usage available to each consumer
`from Such a System.
`0038. The embodiments described hereinafter will be
`more apparent after clarifying the following terms:
`0039) Program-An executable file that the kernel
`can read to memory and execute.
`0040 Process-An executing instance of a pro
`gram. Every process in Unix is guaranteed to have a
`unique numeric identifier called Process ID (PID).
`0041. A thread is a single sequential flow of control
`within a process. A process can thus have multiple concur
`rently executing threads. In Linux, each thread has its own
`PID.
`0042. In Linux OS, the function that creates processes is
`do fork. The functions that handle process termination are
`the exit family. A simple implementation could be to keep a
`counter per user that the System increases/decreases accord
`ing to initiation/termination of processes per account, except
`for processes owned by “root” (UID 0). When an account
`tries to initiate new process that causes it to exceed its quota,
`the system will fail performing the “fork” (or “vfork”,
`"thread create”) function. Hierarchy semantics is the same
`as of the memory management.
`0043. The following describes a mechanism for limiting
`the memory consumption of a Specific account in the com
`puterized System. But first, for the Sake of clarity, the method
`for allocating memory in an Operation System Such as Unix,
`Linux, etc. will be described.
`0044. Each executed application obtains a portion of
`memory area, from which it runs or operates. A memory
`area, referred to hereinafter as “memory address Space',
`comprises relevant data of Specific executed applications.
`The memory address Space is only a portion of a virtual
`memory Specific to each application. Each application has
`its own range of Virtual memory, usually unrelated to the
`address Space of other applications, or to the size of the
`physical computer on which the application is executed.
`0045 Typically, the memory is divided into “pages”,
`which is the basic unit handled by a memory management
`application. A memory manager can Store the "pages in the
`physical memory of the computer, or on the hard disk (in a
`So-called “Swap’ Section). The “Swap” acts as a storage
`memory and temporarily Stores data portions of the appli
`cation on the hard disk, typically, when there is not enough
`physical memory Space for all the programs. The Swap can
`be a set of files, Special disk partitions, or both. Information
`can be stored on the hard disk (either in the “swap” or in real
`files) for the following reasons:
`0046) The memory manager transfers a relatively less
`relevant "page' to the “Swap”, to free Storage Space in the
`(faster) physical memory, for other pages that are currently
`required. The memory manager transferS only pages that
`might be changed by an application, the other pages being
`restored from their initial address (as will be described
`hereinafter).
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1031, p. 7
`
`

`

`US 2005/0246705 A1
`
`Nov. 3, 2005
`
`0047 The page is part of the writeable area of the
`program, but the program does not change it. In this case, the
`page can be loaded from the disk when next needed.
`0048. The page is part of the application “code” (i.e., the
`command line that the application executes, and not the data
`part of the application). The application code cannot be
`changed by the application itself, and therefore, if a page is
`removed from the memory, the memory manager can,
`retrieve it from the application file again.
`0049. The page is part of the application “read only” data.
`The “read only data cannot be changed by the application
`itself, and therefore, if a page is removed from the memory,
`the memory manager can again retrieve it from the appli
`cation file.
`0050. The page is part of a file of an operation system
`such as the “mmap'ed file in Unix. The “mmap' function
`maps “length” bytes starting at the offset from the file (or
`other object) specified by a variable that is passed to
`“mmap”, such as the variable file descriptor (fd), into the
`memory, preferably at the address of the parameter that is
`passed to “mmap’, such as the parameter “start).
`0051. After the mapping, the program can access the file
`just like any part of its memory, without the need to actually
`read the information into buffers that it allocates. In that
`case, a file is mapped to part of the memory of an application
`and there is no need to keep the pages in the Swap file, as
`they can be read from the hard disk.
`0.052 According to a preferred embodiment of the inven
`tion, in order to avoid exceeding the allocated memory of a
`consumer's account, the allocated memory address Space on
`the Swap file of that account is limited. In contrast, the
`physical memory used by an application is not limited, and
`thus this eliminates interference with the way in which the
`operating System works and decides what pages to Swap. In
`the operating systems, such as LinuxTM and UnixTM, the
`amount of memory that a program utilizes can be influenced
`by one or more of the following methods:
`Initial allocation of memory, when the proceSS is
`0053)
`created;
`Enlargement of memory, due to one or more
`0.054
`requests that utilized all the memory available (e.g., the
`function “malloc' in Unix, which requests the OS to allocate
`more memory to the process. The OS might prefer to
`allocate more than the program requests, to handle the case
`where the program might request more pages later on. This
`is part of the memory management of the OS. The function
`“malloc' is standard in C and C++, and is available on
`WindowsTM as well.)
`0055 Mapping to a file (e.g., using the “mmap' func
`tion), that maps a file to a specific memory address space.
`0056 Creating a shared memory region (e.g., using the
`function “shmget', wherein “shmget enables a program to
`request a certain amount of memory from the OS, and in turn
`it associates an identifier with that program. Other programs
`might use this memory as well, by using the related iden
`tifier. The function “shmget' is a mechanism for Sharing
`information between processes.).
`0057. As will be explained hereinafter, all the above
`methods and other possible methods are mapped to a rela
`tively small set of functions in the kernel of the operation
`System.
`
`0058 For example, in Linux with version of kernel 2.2 all
`the operations are mapped to a function in the kernel, named
`“do mimap’. The “do mimap' function gets the following
`parameters:
`0059) Access mode-Read/Write (RW) or Read Only
`(RO). If it is RO, then the memory can be accessed for read
`only, and in that case, no Swap Space is allocated, as the
`information can be retrieved from its place of origin. In this
`case, the method of the present invention does nothing.
`0060 Mapping private or shared in the case of RW. If
`it is shared, only the creator of the shared Storage should be
`charged for this memory. The term private refers to a
`memory that only a specific program can access, Such as
`memory that was allocated when the Specific program
`started running, or that was “malloc'ed. The term Shared
`refers to one that is shared between processes, for example,
`while loading a shared object (e.g., a Dynamic Link Library
`(DLL, which is a collection of Small programs, each of
`which can be called when needed by a larger program that
`is running in the computer, in Windows2000 environment.
`0061 Of course, the “do mimap' function is only one
`example of a Linux implementation, and Such operation is
`Suitable to other functions as well.
`0062) Therefore, the only situation that involves allocat
`ing Swap Space is when the application asks for a private
`memory for RW.
`0.063. It is important to note that a function such as
`“do mimap’ returns the relevant memory addresses, but the
`pages are not allocated in the physical (and thus not in the
`Swap) memory, until they are actually used. The allocation
`is on a page basis, So a program can allocate one hundred
`pages, and access only two of them (at the beginning and end
`of the memory, for example). In that case, only two pages are
`allocated in the memory, and thus can be moved into the
`'Swap.
`0064. According to a preferred embodiment of the inven
`tion, it is assumed that all the pages are used and the
`calculation of memory usage is performed when the page is
`allocated. According to another preferred embodiment of the
`invention, the actual consumption is checked whenever a
`page is used for the first time. However, this might cause a
`program to Stop working while accessing a valid address,
`which does not comply with the behavior of the OS. In order
`to allow the program to behave normally, without being
`aware that it is controlled by the embodiment of the inven
`tion, the present invention complies with the OS behavior.
`Interfering with the OS
`0065
`0066. In the prior art, there are several known methods
`for changing the behavior of an operating System, Such as:
`0067 Changing the source code of the operating system.
`This Solution is problematic, as the Source code is not always
`available. If it is available, it must usually be maintained,
`and therefore, the Solution of modifying the code would
`require updating every new version of the code that might be
`distributed.
`0068. Use “hooks” in a code. Typically, an OS has
`“hooks” that may be used. These hooks are places that the
`OS activates Specific modules that are defined by a user,
`wherein the OS performs specific operations. However,
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1031, p. 8
`
`

`

`US 2005/0246705 A1
`
`Nov. 3, 2005
`
`“hooks' must be implemented as part of the OS, and
`therefore can be used only where the OS writers locate it.
`0069. According to a preferred embodiment of the inven
`tion, no code change is made. Instead, it locates a required
`procedure in the code of the kernel, and then modifies it into
`a Suitable code, as will be described hereinafter.
`0070 Locating the Required Procedure
`0071. The required procedure exists in the kernel's code,
`and therefore locating it in the kernel can be obtained, for
`example, by using the name of the required procedure that
`is Stored in a Suitable Symbol table. Of course, the required
`procedure can be located in other ways, Such as, if, for
`example, the function is not exported, there could be a
`mechanism used for locating a Specific Sequence of bytes of
`that function, etc.
`0072 Modifying the Required Procedure
`0.073
`FIG. 2 schematically illustrates a modification of a
`required procedure, according to a preferred embodiment of
`the invention. Modifying the required procedure (i.e., chang
`ing an original code) is done in the following way:
`0.074
`Loading all the functions as will be mentioned later
`on, using, for example, the “insmod” program in Kernel 2.2
`of Linux.
`0075 Allocating a required range of memory address
`space to be used by a New code 21.
`0.076. In this allocated range, creating a code, which are
`a Series of commands (i.e., New code 21), that performs the
`logic mentioned later.
`0.077
`Keeping the commands lines at the beginning of
`the copied code 22, and then performing a “jump” to the
`beginning of the next command in the Original code 20.
`0078 Replacing the commands line at the beginning of
`the Original code 20 with a “jump” to the beginning of the
`New code 21, and adding bytes with that perform no
`operation, such as No Operations (NOPs), until the end of
`the relevant command. For example, if the function Starts
`with three commands comprising four bytes each, and the
`“jump” comprises six bytes, then two NOPs are added, so
`that jumping to the place after the "jump” will not result in
`performing an unintended code.
`0079. In the new code 21, one can call the original code
`20 by calling the code in the copied code 22. Original code
`20 performs the actual operation, which is the service of the
`relevant System module, Such as memory allocation, CPU
`allocation or other Suitable logic allocation by changing the
`program's information, parameters in the kernel, and any
`other activity that is required for performing the allocation.
`According to the preferred embodiment of the invention,
`original code 20 is executed Separately from new code 21.
`The execution of original code 20 is obtained by calling
`copied code 22 from new code 21. Copied code 22 calls the
`original code 20 to perform the actual logic allocation (e.g.,
`memory allocation and/or CPU allocation). Copied code 22
`only calls original code 20 and it does not contain a copy of
`original code 20. This is required in order to avoid storing
`the original code 20, twice because this might be compara
`tively large. After calling original code 20, copied code 22
`returns to new code 21. At that point, new code 21 verifies
`that the result of the performed allocation and its related
`
`activities were Successful. After new code 21 comple