April 19, 2010

Mapped File, Paging and Memory Protection – C Programming

This program shows use of a number of system calls such as how to map a disk file in the virtual memory of a process space, divide it into pages, set access protection code such as read_only, write_only, etc to individual pages, read/write individual pages, and copy the file back to disk page by page.

#include <stdio.h>
#include <stdlib.h>
#include <sys/mman.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <errno.h>
#include <string.h>
#include <unistd.h>
extern int errno;
 
main()
{
int fid1, fid2;
void *address1, *address2;
char buf[10], data[10]="edwin c";
char *ptr, *base, data1[10]="baldelomar";
int i, n, pagesize;
struct stat statbuf;
int inFileSize, outFileSize;
 
if ((fid1 = open("alice29.txt", O_RDWR,  0600)) < 0)
 {perror("alice open failed");
  printf (" errno=%d \n", errno); 
 }
 
if (fstat(fid1, &statbuf)<0) perror("fstat error");
inFileSize = statbuf.st_size;
printf("Temp1 file size=%d\n", inFileSize);
 
if ((fid2 = open("temp2", O_RDWR | O_CREAT | O_TRUNC,  0600)) < 0)
 perror("temp2 open failed"); 
 
/* temp2 is empty file. It has no space. Let us make it 20000 bytes
long by setting pointer to 9999 and then writeing a byte. */
if ((lseek(fid2, 19999, SEEK_SET)) < 0) perror ("lseek error");
if (write(fid2, "X", 1) != 1) //write 'X' at end
  {perror("write error"); exit(-1);}
 
 
if (fstat(fid2, &statbuf)<0) perror("fstat error");
outFileSize = statbuf.st_size;
printf("Temp2 file size=%d\n", outFileSize);/*prints size=20000*/
 
/*----------------------------------------------------*/
if ((pagesize=sysconf(_SC_PAGESIZE))<0) perror("sysconf failed");
printf("page size =%d\n", pagesize);
 
/* map source file entirely in memory for reading by possibly
multiple processed, who may share all changes. */
 
if ((address1 = mmap((caddr_t) 0, inFileSize, PROT_READ, MAP_SHARED, fid1, 0))==MAP_FAILED) 
{perror("mmap failed"); printf("errno=%d\n", errno);}
printf("actual mapped address1=0x%x\n", address1);
 
base = ptr = (char *) (address1+500);
for (i=0; i< 8; i++) buf[i] = *ptr++; buf[8]='\0';
printf ("Reading Source: %s\n", buf);
 
/* Following attempt to write to source file should cause segmentation
error, because of read_prot, although the file is onped RDWR.*/
 
/*
ptr = base;
for(i=0; i<8; i++) *ptr++ = data[i]; 
fprintf(stderr, "Writing to source: %s\n", base);
*/
/*----------------------------------------------------*/
if ((address2 = mmap((caddr_t) address1, 10000, (PROT_READ | PROT_WRITE),  MAP_SHARED, fid2, 0))==MAP_FAILED) 
{perror("mmap failed"); printf("errno=%d\n", errno);}
printf("actual address2=0x%x\n", address2);
 
/* Make first page write only */
if ((mprotect(address2, pagesize, PROT_WRITE))<0) printf("protect write error=%d\n", errno);
/* make second page read only. */
if ((mprotect(address2+pagesize, pagesize, PROT_READ))<0) printf("protect read  error=%d\n", errno);
 
 
/* Dump one page of memory space to output file */
if ((msync(address2, pagesize, MS_SYNC))<0) printf("m-sync error=%d\n", errno);
munmap(address1, inFileSize);//remove memory space
munmap(address2, outFileSize);
 
 
/* I/O is possible using file descriptor, but not through alloacted space now. */
close(fid1);
close(fid2);
}

April 2, 2010

Using A* Algorithm for solving 8-puzzle in C++

I recently had to do a project for my AI class that could solve an 8 puzzle using an A* search in C++. I have to admit that I wish I could have spent more time cleaning up my code. What’s good is my linked list structure. What’s a little sloppy are my computational methods. Regardless, I thought that this code could still be useful for people who are new or rusty on how to use classes and setting up a search tree.

This is an empty console project, with one source file (main.cpp), one input file (in.txt), and one output file (out.txt). This code has been tested, compiled, and executed under Visual Studio 2008 Professional Edition.

My Algorithm

I created a tree class that could handle linked lists. Every linked node could have up to 4 children. I would simply build the tree structure out. Using the first heuristic, I would build the tree according to which node had the lowest distance from the root node. This is pretty much creating a tree by a breadth depth search. My second heuristic added in a cost for how similar the current node’s state was to the goal state. This allowed the tree to be built smartly and not continue to expand down bad branches.

I also added a constraint that wouldn’t allow a node to be created if it was trying to make a bad move. A bad move is when the puzzle is backtracking. Backtracking is a sure sign that that branch is not an optimal solution.

My Results

I ran my program using two different heuristics. One was many times more efficient than the other. My first heuristic was simply just using the distance from the root node. It took 6.63 minutes to complete.

/**************OUTPUT******************/
Success!
n = 12
time: 663801 msecs
Press any key to continue . . .
/**************************************/

My second heuristic was adding a cost to the distance for how many numbers in the current state were in the same position as the numbers in the goal state. The output was significantly faster. It computed the the same path in under 1 second.

/**************OUTPUT******************/
Success!
n = 12
time: 858 msecs
Press any key to continue . . .
/**************************************/

Using this Code

If you are working on a similar assignment, feel free to use this code and expand on it. I would really appreciate it if someone could polish the code for me and send me an updated copy. It could use a better class structure, better name conventions, prettier computational methods, and some relevant comments. I simply didn’t have time. Feel free to leave a comment if you have any questions trying to get this to work on your computer. I hope this helps!